4 ms·
It's interesting that size() has to be constant-time. From what I understand of the standard linked from the blog post, it looks like size() being constant-time
by thamer 5y ago
It's interesting that size() has to be constant-time. From what I understand of the standard linked from the blog post, it looks like size() being constant-time is a property of Container and not each individual method (§ 23.2.1, page 747).
What does this mean for implementations that want to have these properties but have internal structures that make this inherently difficult? Do they have to recompute a cached size value during other operations, and amortize the cost of size() on insert, for example?
I can see it being tricky in some situations: imagine a collection with expiring data, for example. You might want to prune the expired items in the background, but still have size() return the number of elements currently not expired. How would someone do this while maintaining an exact size() value when the background clean-up will inherently take some time?
- plorkyeran 5y agoThe standard's requirements for the standard library types don't imply any corresponding requirement for types you define yourself. If you want to write a container which can't reasonably do O(1) size() then you just don't do O(1) size(). If such a container was added to the standard library, the standard library's Container requirements will be adjusted to permit that.
- chakkepolja 5y agoExactly, most STL algorithms, for example, can be applied using iterators as well. But anyway if GP has specific requirements iterator invalidation might be a problem too, they wouldn't probably want to constrain their interface to that of STL containers.
- tialaramex 5y agoWait, isn't the point of the STL algorithms that they use iterators? For sure the iterator over a vector may be very cheap to use, but it is still an iterator, even if you tacitly know it's just pointer arithmetic under the hood.
- fhrow4484 5y ago> What does this mean for implementations that want to have these properties but have internal structures that make this inherently difficult I'm not sure I can think of an example of such a data structure? my understanding is that whatever your data structure is, you can keep a "size_t current_size;" private counter which you atomically increment/decrement on every insertion/deletion. size() is simply: size_t size() { return current_size; } In your background clean-up example structure, if the background thread is removing N elements, it must decrease current_size by N. Atomically! (i.e. remove the element and decrease the current_size using a mutex::lock/unlock)
- johntb86 5y agoSome std::list::splice(const_iterator pos, list& other, const_iterator first, const_iterator last) implementations used to be constant-time, since they could just change some pointers in the spliced nodes. Nowadays they take linear time, since they need to count how many nodes are transferred so they can update the sizes correctly.
- jfrunyon 5y agoWouldn't this still be constant-time today? It doesn't need to count the nodes because the other list already has a count of its nodes.
- MauranKilom 5y agoNo, because you can splice in the middle. Given just the iterators you simply have no other way than counting. (The reason why it used to be constant time is that it didn't have to count because it didn't have to compute the new size).
- hermitdev 5y agoNo, because you'd still need book keeping around the length of [first, last), even if the implementation does under-the-hood O(1) movement of nodes in [first, last) from other to *this. Computing the length of [first, last) is still an O(n) operation for forward iterators. Maybe you're assuming [first, last) is the entirety of other? For that case, there are overloads for splicing an entire list in O(1) time: void splice( const_iterator pos, list& other ); void splice( const_iterator pos, list&& other );
- brandmeyer 5y agoOnce upon a time, size() wasn't required to be constant-time. This showed up in some standard library implementations of std::list::size which actually did count all the things. The painful ABI break at C++11 is a big part of why implementors were so opposed to allowing another ABI break in C++20.
- jeffbee 5y agoIt's also why other people in the C++ community are opposed to ABIs themselves.
- brandmeyer 5y agoThe live-at-head model really only works well in a cloud computing or JIT environments. It really shouldn't have been a surprise to find that this model is unpopular outside of those narrow use-cases.
- tialaramex 5y ago> What does this mean for implementations that want to have these properties but have internal structures that make this inherently difficult? Such implementations are de facto forbidden in the STL. Although its containers have vague names like "forward_list" today the C++ STL's containers are in practice very specific data structures that have the specified properties because other data structures would miss one or more of the requirements. This suits "stability at all costs" C++ programmers fine. Better that every C++ program is 10% slower than that their buggy library from 1995 has to be fixed to actually do what the standard says rather than whatever worked in 1995. If you care about this but you like C++ you just don't use the STL. Third parties are free to make containers that use data structures that aren't old enough to stand for President of the United States of America, some of them aren't even old enough to legally drive in the United States of America.