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.
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.
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.
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; }
std::list::splice(const_iterator pos, list& other, const_iterator first, const_iterator last)
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 );Fortunately, the single-node splice is still fast. But batch allocations, say related to some scatter/gather operations, would still be hit by this change.
(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).
std::list WAS noncounting. introducing std::counting_list was an option. I didn't follow this decision so I don't know why they opted to break the behavior (performance expectations).
C style strings are the classical example. Computing the size (strlen) takes linear time. Not saying that this is a good idea or anything, but it's extremely common.
One could imagine a binary tree implemented in a similar manner. It costs a little time and memory to keep track of the current size, but it almosy always pays off.
if (it->expiry_time < now) erase(it);
This is what I meant by "have size() return the number of elements currently not expired". What you're describing is "size returns the number of elements currently not expired OR expired but not yet cleaned up", which is different.
What does `now` even mean? It's presumably a sampled count from a running clock. With concurrent execution, there's no guarantee about the relationship between two thread's samples of the clock unless you synchronize them. One thread may read the clock, then get preempted for a while before doing any actual work. According to the preempted thread's point of view it's still in the present and running calculations without a care in the world, but from the preempting thread's point of view it's frozen in the past to be thawed out in the future.
Do you really need to be that picky about coherency of this hypothetical multi-threaded expiring data structure? So what if the size reads slightly larger on average? It seems like the reasonable direction to err on, since elements are getting deleted out from under you anyway, and so there's an inherent race condition between when a thread would call size() and then call another function dependent on the result of calling size().
If you need it to truly be cycle-by-cycle coherent with the hardware clock, then you'll need to add synchronization. The size() function will no longer take a predictably constant time, as it will either block on a mutex, spin some number of times on a lock-free atomic, or remove expired elements itself.
As other folk have also pointed out, though, the time complexity of the STL member functions are only a self-imposed rule. A function like size can do whatever you want if you're writing the implementation.
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?