2 ms·
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, l
by 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 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.