4 ms·

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

> 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 ago
Some 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 ago
  Wouldn'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 ago
    No, 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 ago
    No, 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 );
    - jfrunyon 5y ago
      This seems like an extremely niche use-case, compared to the prevalence of use-cases needing to check the size of a list.
      - ycombobreaker 5y ago
        This niche is exactly why I've used std::list in several cases. It allows fairly easy preallocation of list nodes. 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.
- ape4 5y ago
  Interesting, a good case for another std::list<> like std::non_counting_list<>
  - ycombobreaker 5y ago
    Reminds me of Michael Bolton from Office Space, "Why should I change, he's the one who sucks!" 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).
klyrs 5y ago
> I'm not sure I can think of an example of such a data structure? 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.
- kllrnohj 5y ago
  Which is long since fixed with std:string & co. The data structure concept of a string has no need for linear length calculation. Rather, C just did strings badly.
thamer 5y ago
My point was that the background thread would remove elements periodically, by checking something like: if (it->expiry_time < now) erase(it); Where erase() could certainly remove the item and update the size, but it would remove elements after they have expired. So if size() must return the actual number of unexpired elements present right now, the cached counter you mention would not be up to date. 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.
- sgtnoodle 5y ago
  When you have multiple threads running concurrently, you're going to have to deal with coherency and synchronization one way or another. 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.

johntb86 5y ago

Some 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 ago
Wouldn'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 ago
  No, 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 ago
  No, 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 );
  - jfrunyon 5y ago
    This seems like an extremely niche use-case, compared to the prevalence of use-cases needing to check the size of a list.
    - ycombobreaker 5y ago
      This niche is exactly why I've used std::list in several cases. It allows fairly easy preallocation of list nodes. 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.
ape4 5y ago
Interesting, a good case for another std::list<> like std::non_counting_list<>
- ycombobreaker 5y ago
  Reminds me of Michael Bolton from Office Space, "Why should I change, he's the one who sucks!" 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).

klyrs 5y ago

> I'm not sure I can think of an example of such a data structure? 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.

kllrnohj 5y ago
Which is long since fixed with std:string & co. The data structure concept of a string has no need for linear length calculation. Rather, C just did strings badly.

thamer 5y ago

My point was that the background thread would remove elements periodically, by checking something like: if (it->expiry_time < now) erase(it); Where erase() could certainly remove the item and update the size, but it would remove elements after they have expired. So if size() must return the actual number of unexpired elements present right now, the cached counter you mention would not be up to date. 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.

sgtnoodle 5y ago
When you have multiple threads running concurrently, you're going to have to deal with coherency and synchronization one way or another. 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.