I think there would be more allocations/deallocations in the c++ version due to copy constructor (if the compiler doesn't compile that out).

In your custom implementation, you first malloc() the 'Widget', and then you malloc a 'ListLink' to store it in, 2 allocations for each node.

std::list will create an internal type that is 'sizeof(Widget) + sizeof(ListLink)' and do one single allocation per node.

That's why you saw the same performance when you changed the std::list store pointers that were allocated with new, as that version also had 2 allocations per node with that setup, 'new Widget' and new 'sizeof(pointer) + sizeof(ListLink)'.

Try timing the loop with 10 million allocations only without any list, and I think you will find that it's not too far from the time of the allocation-step in your list-test.

If you want to count the number of allocations for a C++ implementation, you can override operator new and increment a counter before calling malloc from it.

int g_countNew = 0;
int g_countDelete = 0;

void* operator new(size_t size) {
  ++g_countNew;
  return malloc(size);
}

void operator delete(void *mem) {
  ++g_countDelete;
  free(mem);
}

What do you mean, Erik? I think there would be more allocations/deallocations in the c++ version due to copy constructor (if the compiler doesn't compile that out). There's also if statements in pushing and iterating and popping.

The cost of a single branch to check a null pointer during iteration is miniscule compared to the cost of calling new/malloc/delete/free. And things like the copy constructor for a simple type don't matter - assuming that you're just operating on simple structures or built-in types (not even necessarily POD), any "copies" allocated for temporaries are on the stack. Again, for the purposes of this benchmark, that's fast enough to be irrelevant. The only thing that matters in this situation is how many times you're hitting the system allocator to allocate and free nodes and/or payload.

I thought this was about iterations... Why are we talking about multiple allocations and copy constructors now? It's obvious that allocations are slow, since they usually end up being run by the OS, which runs an entire memory manager (or even just the heap manager, which is probably worse) which needs to do a bit of work before it can allocate the memory. Worst case scenario (although this is probably not the case here), there is no available physical memory, and it has to swap something else to disk to free some.

That's why I mentioned that std::list uses buckets - they also speed up the allocation (even more than just the iteration), if that is the new concern here. It's a really bad idea to ever allocate memory in a loop anyway. If you know how much memory you need beforehand, you should allocate it all at once, and use it. If you don't know how much you need, then just allocate a reasonable initial ammount, then add more when you need it. And by "reasonable", I mean "more than you think you need" in Release builds, and "as little as you can work with" in Debug builds, so you can catch any problems with your memory allocation during development. Std::list does this perfectly for you.

And if you need to copy entire lists of data element by element, then your entire design is probably flawed to begin with.

(Too much coffee. Going to bed...)

std::list does not allocate in buckets; it allocates per-element. You may be thinking of std::deque.

Maybe you're right about std::list, but I don't think std::string allocates every character separately. And by "allocate" I mean that it reserves the memory using the internal allocator, not that it also initializes it. So initialization (via copy constructor) has nothing to do with allocation. Maybe I'll check it out sometime, though. To me it sounds a bit too much that std::list would use additional "next" and "prev" pointers for every element, when it could speed up performance simply by using buckets.

I also found this: http://www.gamedev.net/topic/292334-how-does-stdlist-allocate-its-items/ .

And this: http://accu.org/index.php/journals/1308

I have no clue why std::string and std::list even appear in the same sentence here. While I don't think the standard requires a particular kind of internal storage for an std::string, it needs to support std::string::c_str and storage as anything but a glorified std::vector would be inadvisable (although several std::string implementations do not require allocations for small strings).

That said, I'm really not sure where your enthusiasm for trying to optimize std::list is coming from, especially since it sounds you really want an std::deque in the first place. And while I used to believe (when I was much younger and inexperienced) std::list was a very useful data structure in the past I have found that in actual practical experience it's probably the least used of them all.

I have no clue why std::string and std::list even appear in the same sentence here.

They are both sequence containers. I thought they migh have similar implementation. The default std::allocator is the same for all of them, and it can allocate multiple elements at once (using std::allocator::allocate). And I also think that at least when you insert multiple elements, std::list allocates all the memory for them at once. I'm really just making assumptions and drawing conclusions here though, because I'm too lazy to test this. And you guys talk about "specific implementations" as though STL is just some abstraction - but really, it doesn't abstract the memory allocations. It might give you a method to do that by providing your own allocator, but I think OP was interested in the default implementation here.

That said, I'm really not sure where your enthusiasm for trying to optimize std::list is coming from, especially since it sounds you really want an std::deque in the first place.

I wasn't trying to optimize it. I was just trying to answer the OP's original question. I really don't see what deque has to do with everything I said. Thanks for pointing it out, though.

A std::list that invalidates iterators after erase() or insert(), and does not support remove() and splice() as defined in [23.3.5.5], would be non-conforming.

This statement seems a bit out of place. I never said anything about iterators.

I have no clue why std::string and std::list even appear in the same sentence here.

They are both sequence containers. I thought they migh have similar implementation. The default std::allocator is the same for all of them, and it can allocate multiple elements at once (using std::allocator::allocate). And I also think that at least when you insert multiple elements, std::list allocates all the memory for them at once. I'm really just making assumptions and drawing conclusions here though, because I'm too lazy to test this. And you guys talk about "specific implementations" as though STL is just some abstraction - but really, it doesn't abstract the memory allocations. It might give you a method to do that by providing your own allocator, but I think OP was interested in the default implementation here.

There is no default implementation. The standard requires that the containers have certain member functions and typedefs. The standard sometimes requires that these member functions have a guaranteed complexity. For example std::list::erase for a single element must be O(1) (that's actually an important property because, as Bregma correctly pointed out it makes your list implementation idea with buckets and no next/prev pointers impossible). Another example is that the storage of an std::vector must be continuous (since C++11, but even before no known standard library implemented that differently).

As long as you do not violate the requirements of the standard you can implement the standard library any way you want (and different standard libraries will be implemented differently). For example many (not all) standard libraries implement small string optimization for std::string (so short strings do not require an allocation).

That said, I'm really not sure where your enthusiasm for trying to optimize std::list is coming from, especially since it sounds you really want an std::deque in the first place.

I wasn't trying to optimize it. I was just trying to answer the OP's original question. I really don't see what deque has to do with everything I said.

Me (and apparently several others) in this thread get the distinct impression you are trying to somehow shoehorn an std::list into an std::deque. I don't see how you can implement a list with the suggestions proposed by you without violating the standard. At the same time the std::deque seems to have all that (and more) right out of the box.

A std::list that invalidates iterators after erase() or insert(), and does not support remove() and splice() as defined in [23.3.5.5], would be non-conforming.

This statement seems a bit out of place. I never said anything about iterators.

No you didn't, and that's part of the problem. You try to look at a small part of a list and modify it according to what you think would be better. But you fail to see that doing so would make other things much more difficult or impossible. A list and its iterators (including their guarantees) cannot be looked at separately.

A list and its iterators (including their guarantees) cannot be looked at separately.

It can, when you're trying to implement your own. :)

Thanks for clearing everything up. I wasn't aware of the complexity requirements of STL. Maybe I'll stop being lazy and test it all myself one day, but for now I'm happy to believe you.