std::list of objects efficiency

Question

Say you have a std::list of some class. There are two ways you can make this list: 1)

std::list<MyClass> myClassList;
MyClass myClass;
myClassList.push_front(myClass);

Using this method, the copy constructor will be called when you pass the object to the list. If the class has many member variables and you are making this call many times it could become costly.

2)

std::list<MyClass*> myClassList;
MyClass* myClass = new MyClass();
myClassList.push_front(myClass);

This method will not call the copy constructor for the class. I'm not exactly positive what happens in this case, but I think the list will create a new MyClass* and assign the address of the parameter. In fact if you make myClass on the stack instead of the heap and let it go out of scope then myClassList.front() is invalid so that must be the case.

If I am wrong about this please contradict me, but I believe the 2nd method is much more efficient for certain classes.

Answer 1

The important point to consider here is much more subtle than the performance issue.

Standard library containers work on Copy Semantics, they create a copy of the element you add to the container.
In general it is always better to stay away from dynamic memory allocations in C++ unless you absolutely need it. First option is better because you do not have to bother about the memory allocations and deallocations, The container will take the ownership of the object you add to it, And do the management for you.

In Second case the container does not take the ownership of element you add, You have to manage it yourself. And if you must then you should a Smart pointer as container element rather than a raw pointer.

With respect to performance, You will nedd to profile the code samples on your system to see if the performance difference is notable enough to select one approach over the other.

Answer 2

This is always a though question.

First of all, it really depends whether your compiler supports C++11 move semantics or not, as this dramatically change the aspects of the problem.

For those stuck in C++03

There are multiple choices:

std::list<MyClass> list;
list.push_front(MyClass());

Even though semantically there is a copy, the optimizer might remove most of the redundant/dead stores. Most optimizers will require that the definition of the default constructor and copy constuctor be available.

boost::ptr_deque<MyClass> deque;
std::auto_ptr<MyClass> p(new MyClass());
deque.push_front(p);

ptr_vector could be used should you replace push_front with push_back, otherwise it's a bit wasteful. This avoids most of the memory overhead of a std::list<MyClass*> and has the added bonus of automatically handling memory.

boost::stable_vector<MyClass> svec;
svec.push_back(MyClass());
//        ~~~~

There is one copy (as with list) but a guarantee that no further copy should be made within the container (as with list). It also allows a few more operations than list (for example, random access), at the cost of being slower for insertion in the middle for large containers.

For those enjoying C++11

std::list<MyClass> list;
list.push_front(MyClass());

does not generate any copy, instead a move operation occurs.

It is also possible to use the new operations provided to construct objects in place:

std::list<MyClass> list;
list.emplace_front();

will create a new MyClass directly within the node, no copy, no move.

And finally, you may wish for a more compact representation or other operations on the container, in which case:

std::vector<std::unique_ptr<MyClass>> vec;
vec.emplace_back(new MyClass());

Offers you random access and a lower memory overhead.

Answer 3

If you are really concerned about performance but still need to use linked lists, consider using boost::intrusive::list. The main problem with using std::list is that you'll need to allocate new memory from the heap, and that's probably more costly then even the copy construction for most cases. Since boost::intrusive::list leaves allocation to you, you could keep your objects in a std::vector and allocate them in batches. This way, you'd also have better cache locality, another concern in performance. Alternatively, you could use a custom allocator with the std::list to do the same. Since using the custom allocator for std::list is probably around as messy as using a boost intrusive list, I'd go with boost, because you get many other useful features with that (such as keeping the same object in multiple lists, etc.).

BTW, don't be concerned about the copy construction, the compiler will probably optimize out any unnecessary copying (unnecessary given the way you use it).