std::list is a doubly linked list, how else do you propose they do this? This is traditionally how list sizes are calculated.
(libc++ keeps a track of the size somewhere, but this in occurs a 4/8 byte overhead)
(libc++ keeps a track of the size somewhere, but this in occurs a 4/8 byte overhead)
It's four goddamn bytes. Or eight if you really want more than 4 billion elements.
As long as you don't have millions of lists with a few elements each -- you can't presume that they are only used one way :)
Hell, you probably lose that much to padding somewhere anyways.
That may make 'splice' slower. See http://home.roadrunner.com/~hinnant/On_list_size.html (I think that could be solved by having list iterators carry a field pointing to their container, but haven't given it much thought. Corrections welcome)
Storing an index in the iterator would not be a solution either. That would mean updating the index in all the existing iterators when you insert an object in the list.
libc++ has the luxury of assuming c++11.
Also, linked lists are notoriously crap for cache coherency / processor pre-fetching and branch prediction by processors anyway, given that there's no guarantee where each node will be allocated - the only way to do that is pull them off a slab allocator or something, in which case you might as well use a vector or deque anyway...
I don't that tracking the size would be a big deal, if you think that doing that they wouldn't be a linked list any more, you could think it as a linked link wrapper.
In any case the complexity guarantees of all the other operations remain true so I don't think it is a big deal.