How to implement this data structure in c++

Question

I am moving from C#/Java to C++ and have trouble getting my head around the proper way to do things.

I am building a sort of data-structure to support an algorithm and functionality. So suppose an outer object holds an std::vector<Widget> vecW and an std::vector<Vidget> vecV. It creates a number of objects of type Widget, and adds them to vecW. It subsequently makes a number of instances of Vidget, and adds them to vecV. (In case it matters: The memory allocated for those objects is supposed to be freed when the outer object is destroyed.)

Now, there is some custom logic that dictates, for each object of type Widget in the list, that it needs access to some of the objects of type Vidget. (Vice versa, if widget w has access to vidget v, then vidget v needs access to widget w.)

In C#, I would just keep a List<vidget> ListOfVidgets in each Widget, and a List<Widget> ListOfWidgets in each Vidget, and instantiate these lists based on the custom logic. Similar for Java (I believe List<Vidget> in C# is like arraylist<Vidget> in java, and a bit like std::vector<Vidget*>/std::vector<Vidget> in C++).

So I could go for std::vector<Vidget*> in each widget, to be instantiated based on custom logic. Is this the best approach? Or are there approaches with smart pointers (or even other approaches) that are to be preferred?

---

Edit: The lifecycle is as follows: 1) Outer object get's created and populated (with widgets/vidgets). 2) Custom logic determines the relations. 3) The data structure is used. (So no changes to relations and/or added/removed widgets during use.) 4) (only) when the outer object is destroyed, then memory needs to be freed.

Answer 1

Here's what I'd do.

class Widget {
  ...
    void AddVidget(Vidget* vidget);
  private:
    std::vector<Vidget*> vigets_;
};
std::vector<std::unique_ptr<Vidget>> vidgets;
// Since widgets will have references to vidgets, safet
// to instantiate after vidgets (so widgets is cleaned up
// first).
std::vector<std::unique_ptr<Widget>> widgets;
...
widgets[i].add_vidget(vidjets[j].get());

This gives you pointer stability.

Answer 2

Generally, I would first look for a way to redesign so that this requirement goes away. It isn't usually necessary for objects to find other objects through objects above them this way. Sometimes you can arrange to pass the objects information each time they execute through their owners.

But assuming you can't change the design, you don't want to use either pointers or references. You don't want to use them because vectors can move their objects around in memory, invalidating both pointers and references. Also, ordinary pointers make ownership unclear.

Instead, use a vector of std::shared_ptrs to objects. Create the objects with std::make_shared if possible. This will manage the object's lifetime to persist until it's remove from the vector.

For one object that needs to access another, you have two choices. Use another std::shared_ptr to the same object if you might want to extend the lifetime of the object that's referred to until the object holding a reference to it is destroyed.

Use std::weak_ptr if you don't want to extend the lifetime of the object -- just remember that a weak pointer can become stale if the target's lifetime ends. You either need to ensure this never happens or check the weak pointer every time you access it. It's probably best to always check it anyway just to sanely handle error conditions.

In order of my personal preference, you could:

1. Rearchitect so that there is no need to store these references. For example, the outer object could own the relationships and pass references to the inner objects every time it invoked them. There may even be better options. The outer object can provide an API that inner objects can use and the inner objects can keep a reference to the outer object.

2. Use shared_ptr and weak_ptr. This is clean, easy to understand, and can cleanly catch any errors. It has some overhead, but only on the setup and teardown which shouldn't matter if these objects are long-lived.

3. Use a custom smart pointer. The inner objects can be given a custom smart pointer by the outer object that provides the inner objects an easy way to access the objects they need.

4. Use unique_ptr and vectors of raw pointers.

Answer 3

The main problem with using std::vector is that the addresses of the contained objects is subject to change when the vector changes - especially while you are filling it up.

Given your lifetime characteristics, your objects are going to be fully created before any relationships are built and not changed until after processing is over. This means you don't have a problem using pointers for the relationships.

In which case I would likely do something like this:

class Widget
{
public:

private:
    std::vector<class Vidget*> ListOfVidgets;
};

class Vidget
{
public:

private:    
    std::vector<class Widget*> ListOfWidgets;
};

class OuterObject
{
public:

private:
    std::vector<Widget> vecW;
    std::vector<Vidget> vecV;
};

That should be very efficient as the ownership semantics well established. The outer vectors own everything and the inner object vectors simply contain non-owning relationship pointers.

Answer 4

Don't mess with pointers. That is the old C style way of thinking.

If you're going to work with objects in C++, then make your lists/vectors/maps of Widget and Vidget and let the STL container own the object in question. Then you never have to worry about dereferencing bad pointers, etc.

As for your next requirement, that Widgets need access to Vidgets and vice versa, you'll need to implement that logic in a mapping. I think in terms of databases, so I'd have a table that maps W-to-V and V-to-W, with methods that would return references to the necessary objects. When it comes to C++, I'd probably implement that using std::map with some sort of ID (artificial if need be) to the widget or vidget.