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.

I personally would have a `unique_ptr` in there IF you want the ptrs to be freed. — , Mar 23 '12 at 05:11
There is a third way, which is more probably efficient than both of these: `myClassList.emplace_front()`. Also - if efficiency is a concern, you almost certainly don't want to use `std::list`. — Mankarse, Mar 23 '12 at 05:12
@Mankarse: ironically, for the use case the poster mentionned (objects that are expensive to copy), `std::list<>` is a nice container, mainly because it only ever creates one copy of the object you insert. Other containers (e.g. `std::vector<>`) make copies when you add/remove items to/from the container. — André Caron, Mar 23 '12 at 05:34
I wouldnt use list either. Actually, i never found a reason not to use vector/map although i almost used deque a few times @AndréCaron That made me laugh! Good point — , Mar 23 '12 at 05:34
@AndréCaron: I can't say I agree. If the objects really are that expensive to copy (or move), then a node based container (or a container of `unique_ptr`s) might be worthwhile, but still not `std::list`. Something like [boost::stable_vector](http://www.boost.org/doc/libs/release/doc/html/boost/container/stable_vector.html) might be more appropriate. — Mankarse, Mar 23 '12 at 05:44
@Mankarse: I never said it was the best choice! Besides, the point is moot now that we have move semantics, making vector shifts during insertion and removal so much cheaper :-) — André Caron, Mar 23 '12 at 06:20
@AndréCaron: I agree with you `std::list<>` is a nice container to avoid copy, but `std::list>`... is wasteful. — Matthieu M., Mar 23 '12 at 08:07
@Mankarse: quick note, the author of `stable_vector` is none other than Joaquín M López Muñoz, which authored the impressive Boost.MultiIndex library. Indeed, `stable_vector` design reuses implementation details that can be found in Boost.MultiIndex. — Matthieu M., Mar 23 '12 at 08:27

score 4 · Answer 1 · answered Mar 23 '12 at 05:11

4

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.

answered Mar 23 '12 at 05:11

Alok Save

202,538
53
430
533

Hence why i suggested unique_ptr although thats C++11 (but all the compilers i use support that :)) – Mar 23 '12 at 05:14
Another possibility would be to use a [container intended specifically for pointers](http://www.boost.org/doc/libs/1_49_0/libs/ptr_container/doc/ptr_container.html). – Jerry Coffin Mar 23 '12 at 05:18
@JerryCoffin: It seems like thats an old style unique_ptr but a container rather than a type. I havent check for sure – Mar 23 '12 at 05:21
2

@acidzombie24: Well, sort of. They provide the exception safety of a `container >`, but avoid most of the overhead of a collection of smart pointers. They are intended for the container to own the pointee and not require that elements be copy-constructible or assignable, much like a `container >` would provide. – Jerry Coffin Mar 23 '12 at 05:25
@JerryCoffin: Nice. I'll just finally mention unique_ptr has no overhead but that sounds interesting. I'll use it if i am stuck with a C++03 compiler – Mar 23 '12 at 05:27

score 3 · Accepted Answer · answered Mar 23 '12 at 08:34

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.

score 2 · Answer 3 · answered Mar 23 '12 at 09:00

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).

Thanks for the posts guys, lot's of great answers. Enobayram is the only one that touched on cache locality which is also a major factor in optimising this container. I suppose the only way to really figure out the best solution will be to profile my code later on. — Josh Brittain, Mar 24 '12 at 00:08

score 0 · Answer 4 · edited May 23 '17 at 10:10

The problem with the first approach -- low performance when MyClass is large and inability to have the same object in two data structures (in two lists, each with a different semantics; in a list and a tree; etc). If these downsides do not bother you, go with the first approach.

The second approach is more efficient, but may be harder to manage. For example, you need to correctly destroy MyClass objects if they will not be accessible anymore. This may be non-trivial in the presence of exceptions (read about C++ exception safety). I would recommend you looking at Boost Smart Pointers, which intend to ease C++ pointers management. C++11 has these built-in, so you don't need Boost if you use a modern compiler. Read Wikipedia for a short introduction.

std::list of objects efficiency

4 Answers4