How to use smart pointers to maintain a nested hierarchy of objects?

[kitfox]

I'm trying to figure out the right way to use smart pointers to implement a basic tree like structure. Below is code that shows a basic parent-object-with-many-child-objects relationship. If I were to convert this to use smart pointers, I have several questions such as:

- should Kennel::_dogs use std::unique_ptr<Dog>? If so, what would Kennel::getDog() return?
- should Dog::_kennel be a std::shared_ptr<Kennel>?
- Should I be trying to minimize the number of std::shared_ptr I use?
- I would like my child nodes to have some way to determine what their parent node is. Does having a std::shared_ptr the right way to do this? Or does this violate the idea of 'ownership'?
- Do I need to take precautions to handle the classes that derive from Dog?

#include <vector>
#include <string>

class Dog;

class Kennel
{
    std::vector<Dog*> _dogs;
    
public:
    void addDog(Dog* dog)
    {
        _dogs.push_back(dog);
    }

    Dog* getDog(int index) { return _dogs[index]; }
};

class Dog
{
    Kennel* _kennel;
    std::string _name;
public:
    Dog() {}

    std::string name() const { return _name; }
    void setName(const std::string name) { _name = name; }

    Kennel* kennel() const { return _kennel; }
    void setKennel(Kennel* kennel) { _kennel = kennel; }
    
    virtual std::string breed() const { return "unknown"; }
};

class Doberman : public Dog
{
public:
    std::string breed() const override { return "doberman"; }
};

class Collie : public Dog
{
public:
    std::string breed() const override { return "collie"; }
};


int main()
{
    Kennel* kennel = new Kennel();
    
    Doberman* dobie = new Doberman();
    dobie->setName("Bowie");
    dobie->setKennel(kennel);
    kennel->addDog(dobie);
    
    Collie* collie = new Collie();
    collie->setName("Cher");
    collie->setKennel(kennel);
    kennel->addDog(collie);
    
    Dog* firstDog = kennel->getDog(0);
}

[TheToaster]

Right now, your program has memory leaks because you are not freeing the memory you allocated in lines 47, 49 and 54. The purpose of smart pointers like std::unique_ptr and std::shared_ptr is to allow you to use dynamic memory without having to worry about freeing the memory after you use it, since RAII handles that internally. It is essentially a very rudimentary form of garbage collection. In this case, since _dogs does not need a smart pointer for dynamic memory, there is no need to store pointers.

You could simply implement _dogs as std::vector<Dog> _dogs;

You could then have addDog take a Dog const& dog as a parameter and push that into the vector (perhaps even with std::move() if you don't need the original object to exist after you add it to the kennel).

For the kennel pointer inside of Dog, this could be implemented as a shared_ptr if your wish. This would take care of the dynamic memory allocated by line 47. The only time to use a shared_ptr over unique_ptr is if you need reference counting (i.e. there are multiple owners of a resource).

Thus, Dog::kennel() would return an std::shared_ptr<Kennel> and Dog::setKennel would take a std::shared_ptr<Kennel> as its argument.

[kitfox]

Yes, the program does have memory leaks - I was posting this more to suggest the design and figure out the best way to rewrite it using smart pointers. But I should have addressed that.

I don't think I'd be able to use std::vector<Dog> since I need to be able to add derived types to the array (ie, Doberman and Collie).

[TheToaster]

Ah yeah, I didn't see that you had derived classes in your code. My bad.
In that case, you can do this:

std::vector<std::reference_wrapper<Dog>> _dogs

And then in addDog you can push back like so:

_dogs.push_back(std::ref(dog));

std::reference_wrapper is defined in <functional>

Of course, std::unique_ptr's can also work here, if you wish (it would probably be better):

_dogs.push_back(std::make_unique<Dog>());

and

std::vector<std::unique_ptr<Dog>> _dogs;

[kitfox]

I've not used std::reference_wrapper before. Am I right in thinking that it just stores a reference and depends on that object not going out of scope? For example, would this work:

class Kennel
{
    std::vector<std::reference_wrapper<Dog>> _dogs;
    
public:
    void addDog(const Dog& dog)
    {
        _dogs.push_back(std::ref(dog));
    }
};

void nextDog(Kennel& kennel)
{
    Collie collie;
    kennel.addDog(collie);
}

int main()
{
    Kennel kennel;
    nextDog(kennel);
    cout << kennel.getDog(0).name();
}

[TheToaster]

Reference_wrapper is basically a standard type that defines a class to store references. You cannot have a vector of real references, because std::vector operates on value/copy semantics, but you can copy a std::reference_wrapper. You can get a "reference" to your dog object using std::ref and a const reference using std::cref.

However, your example is not valid. Notice that the collie object's lifetime ends at the end of the function nextDog. In that case, the vector will be storing an invalid reference to an object whose lifetime has expired. Furthermore, you cannot have addDog take a const reference if you push it back into the vector using std::ref. Also line 22 will fail to compile because the reference_wrapper will not implicitly cast to its internal object when using the (.) operator. You have to call get() directly on it (like kennel.getDog(0).get().name(), but this will still access an invalid reference in your case).

Because of the way you are using your class, I would suggest you just implement it using std::unique_ptrs as you originally stated. That would guarantee that the std::vector has ownership over the object's lifetime.

[kitfox]

Another question; if I have the following, does it basically imply that no object outside Beta can access Beta::_alpha directly until Beta::alpha() is called, at which point Beta loses the pointer in Beta::_alpha?

class Alpha 
{
};

class Beta
{
    std::unique_ptr<Alpha> _alpha;
public:
    std::unique_ptr<Alpha> alpha() { return _alpha; }
    void setAlpha(std::unique_ptr<Alpha> alpha) { _alpha = alpha; }
};

[TheToaster]

Your code will fail to compile because you are returning alpha and assigning to it using lvalues. unique_ptr has a deleted copy constructor and a deleted copy assignment operator. You can only use move semantics on it. Take the following code for instance:

#include <vector>
#include <string>
#include <iostream>
#include <functional>
#include <memory>
struct Alpha 
{
    std::string a = "HELLO";
};

class Beta
{
public:
    std::unique_ptr<Alpha> _alpha;
    std::unique_ptr<Alpha> alpha() { return std::move(_alpha); }
    void setAlpha(std::unique_ptr<Alpha> alpha) { _alpha = std::move(alpha); }
};
int main()
{
    Beta beta;
    beta.setAlpha(std::make_unique<Alpha>());
    auto t = beta.alpha();
    std::cout << t->a;  //Prints "HELLO"
    std::cout << (beta._alpha)->a; //ERROR: SEGMENTATION FAULT
    
}

Once Beta::alpha() is called, the resource is no longer owned and the original object will not be able to access it since it does not have a copy.

[TheToaster]

Another thing I noticed in your original code. Instead of the following code:
void setName(const std::string name) { _name = name; }

You should probably take name by const&:

void setName(const std::string& name) { _name = name; }

Or better yet use std::string_view from C++17 in <string_view>

void setName(std::string_view name) { _name = name; }

You should probably also create a constructor for Dog that calls setName to set its name.

[kitfox]

Thanks for your help. Never came across std::string_view before. Would you know of any good place that discusses smart pointers and related issues more in depth? Most of the info I find online just discusses the bare mechanics and very simple use cases.

[George P]

A meta-search for "std::string_view examples":
https://duckduckgo.com/?q=std%3A%3Astring_view+examples&t=ffsb&ia=web

Meta-search for "C++ using smart pointers"
https://duckduckgo.com/?q=c%2B%2B+using+smart+pointers&t=ffsb&ia=web

[TheToaster]

Basically, for std::string_view, any time you see a "const std::string&", you can mostly replace it with "std::string_view" for a read-only view of a string.

For smart pointers, this video provides a thorough introduction to the topic:
https://www.youtube.com/watch?v=UOB7-B2MfwA

[thmm]

About string_view
https://www.youtube.com/watch?v=fj_CF8xK760
https://www.youtube.com/watch?v=H9gAaNRoon4

[mbozzi]

std::string_view is my favorite feature of C++17.

Here's an in-depth talk from 2016 about smart pointers by Herb Sutter
https://www.youtube.com/watch?v=JfmTagWcqoE

Actually, while the focus is mostly on how & when to use C++11's smart pointers, the talk addresses resource ownership in general, including how to manage the resources stored inside complex data structures. It also covers a number of important pitfalls that are commonly associated with their use, namely resource leaks thanks to cyclical ownership & stack overflow thanks to over-long ownership chains.

[kitfox]

Thanks for the link. That talk cleared up a few questions. I was kind of surprised his graph structure was using raw pointers to refer to parents and peer nodes that were owned by the parent.

However, I still have a questions when it comes to using smart pointers to build large, nested data structures. I want to potentially be able to grab any branch of a complex document model and pass it to methods to work on. I also want to be able to inspect the model, which means that I ought to be able to traverse both up and down the tree from any given branch (which requires parent pointers).

For example, is the below a good way to implement this? Should I use a std::shared_ptr for everything?

#include <memory>
#include <vector>

class Environment;
class Document;

class Text
{
    friend Document;
    Document* _parent;
    std::string _text;
    
    //Should be okay since Text is owned by Document
    void setParent(Document* p) { _parent = p; }
    
public:
    std::string getText() const { return _text; }
    void setText(std::string_view text} { _text = text; }

    //What do I do here?  I want external objects to be able to get a 
    // reference to the parent, but this seems unsafe
    Document* getParent() { return _parent; }
};

class Document
{
    friend Environment;
    Environment* _parent;
    
    std::shared_ptr<Text> _text;
    
    //Should be okay since Document is owned by Environment
    void setParent(Environment* p) { _parent = p; }
    
public:

    //What do I do here?  I want external objects to be able to get a 
    // reference to the parent, but this seems unsafe
    Environment* getParent() { return _parent; }
    
    //I want outside processes to be able to access _text so that they can read or
    // modify it, but Document should still 'own' it.  Is this the right 
    // thing to return?
    std::shared_ptr<Text> getText() { return _text; }
    
    //I want an outside method to be able to create a text object and give it to us
    void setText(std::shared_ptr<Text> text) 
    {
        _text = text; 
        _text->setParent(this);
    }
    
};

class Environment
{
    std::vector<std::shared_ptr<Document>> _docs;
public:

    //I want external objects to be able to get a reference to document so they can
    // use them, but not own them.  Is this the right thing to return?
    std::shared_ptr<Document> getDocument(int index) { return _docs[index]; }

    void createDocument() 
    { 
        std::shared_ptr<Document> doc = std::make_shared<Document>();
        doc->setParent(this);
        _docs.push_back(doc);
    }
};

[TheToaster]

If I am understanding correctly, there will only be 1 instance of the Environment class for the whole program (singleton) correct?

I would suggest you use shared_ptrs. In the createDocument() function, instead of calling setParent with this, you should call setParent with std::shared_from_this. For this, you also need to derive your class from std::enable_shared_from_this. You also need to do this for Document. Here is some information:

https://en.cppreference.com/w/cpp/memory/enable_shared_from_this

Furthermore, why not just return the object directly in getDocument?

Document& getDocument(int index) {return *_docs[index];}
Document const& getDocument(int index) const {return *_docs[index];}

[kitfox]

There should only every be one Environment at a time. It could potentially be deleted and a new one created to replace it, although right now it is just held by my MainWindow.

If I return a reference to a Document, the document might be deleted from Environment while I still hold the reference to it. If I use a smart pointer, I wouldn't have to worry about that.

[TheToaster]

Well the reference won't be invalidated while you are holding it, if that is what you mean. Remember there is still a smart pointer in the vector that manages the resource. You are merely returning a reference to the resource owned by that smart pointer in the vector. Here is some test code that works using smart pointers:

#include <memory>
#include <string_view>
#include <string>
#include <iostream>
#include <vector>

class Environment;
class Document;

class Text
{
    friend Document;
    std::shared_ptr<Document> _parent;
    std::string _text;

    void setParent(std::shared_ptr<Document> p) { _parent = p; }

public:
    std::string getText() const { return _text; }
    void setText(std::string_view text) { _text = text; }

    auto& getParent() { return _parent; }
    auto const& getParent() const { return _parent; }
};

class Document : public std::enable_shared_from_this<Document>
{
    friend Environment;
    std::string a;
    std::shared_ptr<Environment> _parent;
    std::shared_ptr<Text> _text;

    void setParent(std::shared_ptr<Environment> p) { _parent = p; }

public:

    auto getParent() { return _parent; }
    void set_me(std::string b) {a = b;}
    auto get_me() {return a;}

    auto& getText() { return *_text; }
    auto const& getText() const { return *_text; }

    void setText(std::shared_ptr<Text> text)
    {
        _text = text;
        _text->setParent(shared_from_this());
    }
};

class Environment : public std::enable_shared_from_this<Environment>
{
    std::vector<std::shared_ptr<Document>> _docs;
public:

    auto& getDocument(int index) { return *_docs[index]; }
    auto const& getDocument(int index) const { return *_docs[index]; }

    void createDocument()
    {
        std::shared_ptr<Document> doc = std::make_shared<Document>();
        doc->setParent(shared_from_this());
        doc->set_me("I am a string that is printed to the screen");
        _docs.push_back(std::move(doc));
    }
};

int main()
{
  auto env = std::make_shared<Environment>();
  env->createDocument();
  std::cout << env->getDocument(0).get_me() << std::endl;
}

Output:

I am a string that is printed to the screen

The only time you would have to worry about holding invalid references is when the reference to an object is within a stack frame to a particular function. For example, if you return a reference to a local variable from a function, that reference will now be invalid. Smart pointers manage the lifetime of their resources and are heap allocated, thus the data will remain until the end of the program, where they are destroyed, in which case the smart pointer frees the memory if it knows that there are no other owners (using reference counting).

EDIT:
Unless you mean if the data inside the vector was manually popped_back() by the class at some point while you are still holding a reference. The question then remains why you would want a smart pointer to hold onto the data after the document has been removed from the environment? If the data is removed from the Environment then that means it is no longer required and needs to be freed. You are just extending the lifetime of the document when it is no longer even a part of the Environment anymore. Though, there could be some uses to this, like file recovery and such, I didn't see any of those implemented in your code so I assumed you didn't need those features.

Logically, to me, a document should not be able to exist without an environment because the environment OWNS the document. Even if you were implementing some sort of file recovery methods, this should logically be a part of the Environment class and the client code should not do this by itself. The only interface the client should have is the environment, and the environment should handle its own documents.