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