Home > Mobile >  should the intelligent pointer be used in basic data structure, e.g. doubly linked list, binary tree
should the intelligent pointer be used in basic data structure, e.g. doubly linked list, binary tree

Time:10-12

For the basic data structures, for instance,
Doubly linked list has something like Node * next, Node * prev;
Binary Tree has something like Node * left, Node * right;
What are the pros. and cons. by using unique_ptr or shared_ptr to replace above Node *?
Are there any well-known open source projects in this way?

CodePudding user response:

Let me answer part of my own question by myself.
Doubly-Linked List can be implemented by treating next as unique_ptr and prev as raw pointer. The last node's next should not point to head node but should be unique_ptr<T>().

  1. One pros. is, we don't need to worry about when the List will be destructed. It will manage itself when the life cycle of head node is done. When that happens, the whole List will be destructed one node afte another from the head node. It's automated.
  2. One cons. is, the code is more complex.
  3. Another cons. is, if there are too many nodes in the List, the destructing of the List will cause segment fault, as there are too many layers of recursive destructor of the unique_ptr. My own experience is, when there are about 65400 nodes, the core dump will happen.

About using shared_ptr, I guess the cons. could be easy to encounter circular reference. I did not implement it yet.

About binary tree, um..., just feel that's not a good idea to use intelligent pointer to replace Node * left and/or Node * right.

So, personally, the conclusion is, it could be better to not using intelligent pointer in basic data structure. Welcome any comments.

CodePudding user response:

It's not the answer, it's more a question. (I don't have enough "karma" to leave comments, sorry). I've heard that new keyword will be removed in C 23, and it's already deprecated for the C 20, so how we will implement a double-linked list, as usage of smart pointer not fully fit here (based on @Finix answer) and new will be deprecated?

  • Related