Implement containers using smart pointers

Question

Well, so everyone knows that raw pointers should be avoided like the plague, and smart pointers should be preferred, but is this advice applicable when implementing a container? This is what I am trying to accomplish:

template<typename T> class AVLTreeNode { public: T data; unique_ptr<AVLTreeNode<T>> left, right; int height; } 

Unique_ptr can make container functions more cumbersome to write because I cannot have multiple raw pointers temporarily pointing to the same object in such an elegant way. For example:

 unique_ptr<AVLTreeNode<T>> rotate_right(unique_ptr<AVLTreeNode<T>> n1) { unique_ptr<AVLTreeNode<T>> n2 = n1->left; n1->left = n2->right; n2->right = n1; // n1 must now be referenced through the longer name n2->right from now on n2->right->recalculate_height(); n2->recalculate_height(); return n2; } 

(This is not very important in this example, but I can imagine how this can become a problem). Should I take such problems as a strong hint that containers should be implemented using the old old new , delete and raw pointers? It seems like a lot of trouble to avoid writing a destructor.

Answer 1

I usually don’t use smart pointers when implementing containers, as you show. Raw pointers (imho) are not things that should be avoided like the plague. Use the smart pointer if you want to ensure memory ownership. But usually in a container, the container has memory, which is indicated by pointers that make up the data structure.

If in your design AVLTreeNode uniquely owns its left and right children, and you want to express it with unique_ptr , that's fine. But if you prefer AVLTree have all AVLTreeNode s, and do it using raw pointers, this is also true (and I usually code it).

Believe me, I'm not an anti-smart pointer. I am the one who came up with unique_ptr . But unique_ptr is another tool in the toolbox. Having good smart pointers in the tool box is not a cure, and using them blindly for everything does not replace a meticulous design.

Refresh to reply to comment (comment field was too small):

I often use raw pointers (which are rarely owned). A good sample of my coding style exists in the open source libC ++ project. You can view the source in the View SVN section.

I prefer that each allocation of a resource be freed in the destructor somewhere due to security issues, even if the usual release occurs outside the destructor. When a distribution belongs to one pointer, a smart pointer is usually the most convenient tool in a tool box. When a distribution belongs to something larger than a pointer (such as a container or Employee class), raw pointers are often a convenient part of the data structure that makes up a larger object.

Most importantly, I never allocate any resource without knowing which object belongs to this resource, be it a smart pointer, a container or something else.

Answer 2

The code you submitted compiles without problems

 #include <memory> template<typename T> class AVLTreeNode { public: T data; std::unique_ptr<AVLTreeNode<T>> left, right; int height; }; int main() { AVLTreeNode<int> node; } 

test compilation: https://ideone.com/aUAHs

Personally, I used smart pointers for trees, even when the only thing we had was std::auto_ptr

As for rotate_right, it can be implemented with a pair of unique_ptr::swap calls

Answer 3

A small correction: raw pointers should not be avoided like a plague (oops, not everyone knows the fact), but manual memory management should be avoided whenever possible (using containers instead of a dynamic array or smart pointers), so in your function, just do get ( ) to its unique_ptr for temporary storage.

Answer 4

std::shared_ptr does not have these limitations. In particular, several shared_ptr constants can refer to the same object.

Answer 5

Herb Shutter has a very clear tip about not using shared_ptr as parameters in his GoTW series :

Guideline: Do not pass the smart pointer as a parameter to the function if you want to use or manipulate the smart pointer itself, such as a share or transfer of ownership.

and this...

Guideline: prefer to pass objects by value, * or or, rather than by smart pointer.