Why does stl::list copy elements added to the list?

Asked 2012-10-16T14:05:25.830

The Standard Template Library documentation for list says:

void push_back ( const T& x );

Add element at the end Adds a new element at the end of the list, right after its current last element. The content of this new element is initialized to a copy of x.

These semantics differ greatly from the Java semantics, and confuse me. Is there a design principle in the STL that I'm missing? "Copy data all the time"? That scares me. If I add a reference to an object, why is the object copied? Why isn't just the object passed across?

There must be a language design decision here, but most of the commentary I've found on Stack Overflow and other sites focuses on the exception throwing issues associated with the fact that all this object copying can throw exceptions. If you don't copy, and just handle references all those exception problems go away. Very confused.

Please note: in this legacy code base I work with, boost is not an option.

c++ stl

Edit Report

2 Answers

You don't add a reference to an object. You pass an object by reference. That's different. If you didn't pass by reference, an extra copy might have been made even before the actual insert.

And it does a copy because you need a copy, otherwise code like:

std::list<Obj> x;
{
   Obj o;
   x.insert(o);
}

would leave the list with an invalid object, because o went out of scope. If you want something similar to Java, consider using shared_ptr. This gives you the advantages you're used to in Java - automatic memory management, and lightweight copying.

answered 2012-10-16T14:09:10.507

Java works the same way, actually. Allow me to explain:

Object obj = new Object();
List<Object> list = new LinkedList<Object>();
list.add(obj);

What is the type of obj? It is a reference to an Object. The actual object is floating around somewhere on the heap—the only thing you can do in Java is pass around references to it. You pass a reference to the object to the list's add method, and the list stores a copy of that reference in itself. You can later modify the named reference obj without affecting the separate copy of that reference stored in the list. (Of course, if you modify the object itself, you can see that change through either reference.)

C++ has more options. You can emulate Java:

class Object {};
// ...
Object* obj = new Object;
std::list<Object*> list;
list.push_back(obj);

What is the type of obj? It is a pointer to an Object. When you pass it to the list's push_back method, the list stores a copy of that pointer in itself. This has the same semantics as Java.

But if you think about it from an efficiency standpoint… how big is a C++ pointer/Java reference? 4 bytes or 8 bytes, depending on your architecture. If the object that you care about is around that size or smaller, why would bother putting it on the heap and then passing pointers to it everywhere? Just pass the object:

class Object {};
// ...
Object obj;
std::list<Object> list;
list.push_back(obj);

Now, obj is an actual object. You pass it to the list's push_back method, which stores a copy of that object in itself. This is a C++ idiom, in a way. Not only does it make sense for small objects, where a pointer is pure overhead, it also makes thing easier in a non-GC language (ther

answered 2012-10-16T14:21:23.853

Why does stl::list copy elements added to the list?

2 Answers

Your Answer