Hacker News Reader

Comment by mm321 | Hacker News Reader

Oh! before doing C++14 gcc should please fix the std::list class; the size() method walks over the whole list in order to determine its size, outrageous.

template<typename _Tp, typename _Alloc = std::allocator<_Tp> > class list : protected _List_base<_Tp, _Alloc> { ... size_type size() const { return std::distance(begin(), end()); }

View on HN

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)

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.

> 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 :)

No, really, it's quite a safe assumption.

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

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)

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.

Of course. Thanks.

It changes the ABI of std::list, which is a serious concern.

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

Then you might be better off with a std::forward_list which is typically the size of a pointer.

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

Sure, but blowing the cache just to count is nuts.

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.

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.

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.

The standard in C++11 demands that size must be O(1). Also, there are some compilers that already are complaint in that regard.

That's new in C++11 though, isn't it? I'm pretty sure (i.e. I haven't checked the spec) that as far as C++03 the complexity was allowed to be linear. Honestly my sense of aesthetics agrees -- linked lists aren't supposed to have constant-time operations, there are better choices if that is a requirement. And if you want an augmented data structure you should cook your own: a list with extra tracking (i.e. ever node needs to have a pointer to the global thingy!) and insertion hooks isn't a "list" any more.

Yeah, they changed the wording from "should" to "must" be O(1) in C++11, which means that before, even when they encourage the implementer to do it constant, that was in fact optional.

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.

Make your own wrapper.

That's why i like C; you never bitch about such things, you just do your own list;

In C++ you are supposed to reuse standard abstractions; So you can - do your own std::list; (still have to copy iterators and everything into it;-) - do your own wrapper around std::list that exposes a weaker interface, - make your own list and everybody start to bitch that you are reinventing the wheel.

As you know in C++ you can do things the C++ way or the C way. That's why I like C++. If you want O(1) for size() of a collection you can use std::vector<> Of course, it doesn't suit every situation.

Reply on news.ycombinator.com