Std :: list of object performance

Question

Say you have a std :: list of some class. You can do this list in two ways: 1)

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

Using this method, the copy constructor will be called when the object is transferred to the list. If a class has many member variables and you make this call many times, this can become expensive.

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 quite sure what happens in this case, but I think this list will create a new MyClass * and assign the address of the parameter. In fact, if you make myClass on the stack instead of a heap and let it go out of scope, then myClassList.front () is invalid, so that should be so.

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

Answer 1

This is always a question.

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

For those stuck in C ++ 03

There are several options:

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

Even if there is a semantically copy, the optimizer can delete most of the backup / dead storage. Most optimizers will require a default constructor definition and copy constants.

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

ptr_vector can be used if you replace push_front with push_back , otherwise it is a little wasteful. This avoids most of the memory overhead std::list<MyClass*> and has the added bonus of automatically processing memory.

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

There is one copy (like the list), but the guarantee that no additional copy (like with the list) should be made in the container. It also allows you to perform several operations than a list (for example, random access), due to a slower nesting in the middle for large containers.

For those who use C ++ 11

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

does not create any copy; instead, a move operation occurs.

It is also possible to use new operations to create objects:

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

will create a new MyClass directly inside the node, without copying, without moving.

And finally, you may wish for a more compact view 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 lower overhead.

Answer 2

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

Standard container libraries work on Copy Semantics, they create a copy of the element that you add to the container.
In general, it is always better to stay away from dynamic memory allocations in C ++ if you do not need it. The first option is better because you do not need to worry about memory allocation and freeing up memory. The container will take responsibility for the object that you add to it, and do the management for you.

In the second case, the container does not receive ownership of the added item, you must manage it yourself. And if you need to, then you need the Smart pointer as a container element, not a raw pointer.

In terms of performance, you will not be able to profile code samples in your system to find out if there are enough differences in performance to choose one approach over another.

Answer 3

If you are really concerned about performance, but should still use linked lists, consider using boost :: intrusive :: list . The main problem with using std::list is that you will need to allocate new memory from the heap, and this is probably more expensive than even the copy construct for most cases. Since boost::intrusive::list leaves a selection to you, you can save your objects in std::vector and distribute them in batches. This way you will also have more cache space, another performance issue. Alternatively, you can use your own allocator with std :: list to do the same. Since using a custom allocator for std::list is probably around as messy as using an inlaid boost list, I would go with boost because you have many other useful features (e.g. storing the same object in multiple lists, etc.).).

By the way, don't worry about building a copy, the compiler will probably optimize any unnecessary copy (unnecessary, given how you use it).

Answer 4

The problem with the first approach is poor performance when MyClass is large and unable to have the same object in two data structures (in two lists, each with different semantics, in a list and tree, etc.). If these shortcomings are you don't worry, go to the first approach.

The second approach is more efficient, but it can be more difficult to manage. For example, you need to properly destroy MyClass objects if they are no longer available. This can be nontrivial with exceptions (read about C ++ exception safety ). I would recommend you see Boost Smart Pointers , which intend to simplify C ++ pointer management. C ++ 11 has these built-in functions, so you don't need Boost if you use a modern compiler. Read Wikipedia for a brief introduction.