4 ms·

Some std::list::splice(const_iterator pos, list& other, const_iterator first, const_iterator last) implementations used to be constant-time, since they coul

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

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