CODEWITHSUNDEEP
c++containers
user541686
user541686

Reputation: 210765

Is having a container of a type as a field a bad idea in C++?

Is it a bad idea in C++ to do something like:

struct Node
{
    string name;
    vector<Node> children;
};

I'm asking because it looks to me like resizing children for any reason could potentially cause an exponential copying cascade. But on the other hand, vector<Node*> has its own problems, and things like vector<shared_ptr<Node>>, while safe, have poor memory locality (due to too many indirections), which starts hurting when you're trying to e.g. build a gigantic tree in memory.

So, in general, is it a bad idea to have a container of your own type in C++ (03)? Are there other reasons to avoid (or prefer) this idiom, instead of using containers of pointers?

Upvotes: 1

Views: 148

Answers (4)

Mankarse
Mankarse

Reputation: 40643

If vector is std::vector, then this code has undefined behaviour as [res.on.functions] states (with similar wording in both C++03 and C++11):

... In particular, the effects are undefined in the following cases: ... if an incomplete type is used as a template argument when instantiating a template component, unless specifically allowed for that component.

If you want to do this, use an implementation of vector that explicitly allows recursive instantiations, such as boost::container::vector.

Upvotes: 0

justin
justin

Reputation: 104718

Is having a container of a type as a field a bad idea in C++?

It's not bad as a general rule. It really comes down to the context.

In this case, the indirections of a shared pointer should not be significant compared to nontrivial resize operations, and the cascading (assuming that will be a problem).

If you can reserve the proper sizes prior to populating the vector or make copying trivial, then there's not much to worry about here.

If it's really gigantic, you could base your nodes of an external store, which handled (and potentially shared) the nodes. Then your resizing ops would be trivial, as your children would all be pointers.

Depending on the size of the Nodes, this:

struct Node
{
    string name;
    shared_pointer<vector<Node> > children;
};

may be better than shared nodes. It really depends on the size, depth, how often you resize. A container isn't bad, but you will have to know how your program will execute to choose the best strategy (profiling can also help here, even in cases when you figure you know the fastest).

If you know you have a lot of objects and a lot of resizing to do, then an fast external store will be a good choice; jalf's answer outlines a good strategy for this.

You could also use a list of node vectors on a backing store if you will have a lot of mutations, and pointers to list elements for the children.

Support for these more complex implementations also takes more time than your current design, but they are worth trying if you do need to perform a lot of mutations. Simplicity to implement and maintain would then be a bonus to your original design.

If your graph really doesn't grow very large, another approach would be to use custom allocators which either referred to a backing store of nodes, or shrank less often than the default allocators.

Upvotes: 2

Stack Overflow is garbage
Stack Overflow is garbage

Reputation: 248289

Depends on several things:

  • does your compiler support move semantics (and if so, have you added move constructor/move assignment operator to the Node class)
  • how likely are you to resize the vector?
  • how deep is your data structure going to be? How many levels of nodes are going to have to be copied/moved if one of them has its vector resized?

You're right, it could potentially have this effect, but only if your data structure is deep and wide enough for the cascade to actually be noticeable.

Adding move semantics to your class would solve the problem entirely, but alternatively, you could modify the data structure. One option might be to not store the vectors inside nodes at all. Perhaps keep one single large vector which is shared between all nodes, and let each node store two iterators pointing to the range of elements that belong to it.

Upvotes: 2

Andrei
Andrei

Reputation: 5015

Won't making children a pointer to a vector of Nodes help with the copying cascade?

Upvotes: 0

Related Questions