News for hackers. Stuff that matters.
Re:Clang is now feature complete for C++14 by cmircea on Thursday November 07, 2013 @08:30AM (#6689150)
I think everyone will agree that using 4 bytes to store the size a much better idea than potentially enumerating millions of nodes just to count them, in the process completely blowing the cache and any optimizations the processors may do.

It's four goddamn bytes. Or eight if you really want more than 4 billion elements.

Re:Clang is now feature complete for C++14 by berkut on Thursday November 07, 2013 @09:33AM (#6689482)
Most STL implementations have always done this. This is one reason why it's better to use the empty() check for an empty container instead of size() == 0 for all container types.

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

Re:Clang is now feature complete for C++14 by cmircea on Thursday November 07, 2013 @03:50PM (#6692285)
Sure, but blowing the cache just to count is nuts.
Re:Clang is now feature complete for C++14 by apaprocki on Thursday November 07, 2013 @08:35AM (#6689175)
> 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 :)

Re:Clang is now feature complete for C++14 by Someone on Thursday November 07, 2013 @09:39AM (#6689512)
According to http://www.cplusplus.com/reference/list/list/size/, list::size must be constant time in C++11.

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)

Re:Clang is now feature complete for C++14 by TwistedWave on Thursday November 07, 2013 @03:41PM (#6692234)
Having list iterators carry a field pointing to their container wouldn't help you determine the number of objects between two iterators when you splice, which is what you need in order to maintain the object count.

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.

Re:Clang is now feature complete for C++14 by Someone on Thursday November 07, 2013 @06:27PM (#6693272)
Of course. Thanks.
Re:Clang is now feature complete for C++14 by sharth on Thursday November 07, 2013 @10:27AM (#6689806)
It changes the ABI of std::list, which is a serious concern.
Re:Clang is now feature complete for C++14 by snogglethorpe on Thursday November 07, 2013 @09:36PM (#6694084)
... and figuring out how to deal with that is the reason that libstdc++ is moving slowly on this.

libc++ has the luxury of assuming c++11.

Re:Clang is now feature complete for C++14 by angersock on Thursday November 07, 2013 @09:34AM (#6689488)
No, really, it's quite a safe assumption.

Hell, you probably lose that much to padding somewhere anyways.

Re:Clang is now feature complete for C++14 by vinkelhake on Thursday November 07, 2013 @01:01PM (#6691039)
Then you might be better off with a std::forward_list which is typically the size of a pointer.
Re:Clang is now feature complete for C++14 by beerscout on Thursday November 07, 2013 @09:52AM (#6689597)
Not everybody will agree. One of the main advantages of std::list is splicing that can be done in O(1) if the size is not stored.
Re:Clang is now feature complete for C++14 by protomyth on Thursday November 07, 2013 @01:00PM (#6691033)
If the standard says it needs to be O(1) then you implement it that way and have a different list for fast splicing if needed.
Re:Clang is now feature complete for C++14 by astrodust on Thursday November 07, 2013 @11:09AM (#6690125)
Just make it the native size based on architecture. 4-byte int for 32-bit, 8-byte for 64-bit. It's impossible to store more than 4 billion elements on a 32-bit machine, you run out of memory first.