5 ms·
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.
by 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 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 );
- jfrunyon 5y agoThis seems like an extremely niche use-case, compared to the prevalence of use-cases needing to check the size of a list.
- ycombobreaker 5y agoThis 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.