Thorsten Ottosen said:
| You can find vehement supporters for this flexibility for list::size,
| but I'm not one of them. I believe that not only is this flexibility
| not needed, it makes list::size useless, and actually dangerous.
well, the question is: are there other operations than splice() which
would benefit from a O(n) size()? Otherwise there should be no
"should" in the standard.
Ivan Vecerina said:
Could you list the trade-offs for std::list to store its item count?
I know that splice operations between std::list instances then become
more expensive, and I agree I would not care much about that.
Any other practical obstacle you have been encountering?
Sure.
list::splice is the only function where there is an order of complexity
change. However, my last sentence is, I believe, overly alarming, and
indeed, an exaggeration.
There are 5 possible valid splice situations: splicing from self or
splicing from another list, crossed with splicing 1 element, some
elements, or all elements. The O(1) size leads to an O(some) splice in
one of these five situations (best viewed in a mono-spaced font):
list::splice complexity with O(1) size
+------+-----------------+-----------------+
| | from self | from other |
+------+-----------------+-----------------+
| one | O(1) | O(1) |
+------+-----------------+-----------------+
| some | O(1) | O(some) |
+------+-----------------+-----------------+
| all | not valid | O(1) |
+------+-----------------+-----------------+
In the "splice some from other" case, the splice function must compute:
std::distance(first, last);
where [first, last) represents the range "some" which is to be spliced
from other. So the constant on that linear complexity term is really
quite small (but of course not zero).
To combat this, Metrowerks (which has a O(1) list::size) offers yet
another splice overload:
void splice(iterator position, list& x, iterator first,
iterator last, size_type n);
Where a precondition is that the last parameter "n" is equal to
distance(first, last). It turns out that clients that use the "splice
some from other" functionality usually know, or can compute without
changing algorithmic complexity, distance(first, last). Furthermore, in
debug builds this precondition is checked (along with a host of other
checks in debug builds).
The result is that distance(first, last) no longer needs to be computed
within splice (in release mode) and so "splice some from other" is also
now truly O(1).
Now on to the question: What does O(1) list::size benefit?
Answer: Both client code, and the implementation of list.
I have had the opportunity to review much C++ production code using
std::list, which I have not written. Of the code I've reviewed,
list::size is used much, much more often than list::splice. And
list::size is sometimes used in a way that could turn a linear algorithm
into a quadratic one (such as the end condition in a for loop). Yet I
haven't noticed "splice some from other" being used in a context where
it could change the complexity of an algorithm. Note this is not to say
it isn't used in such a context. Just that I haven't actually seen it
in production code that I've reviewed.
Conclusion (anecdotal, not scientific): std::list clients ignorant of
this issue are more likely to be bitten by an O(N) list::size than by an
O(some) list::splice some from other.
In the implementation of std::list, there are some functions that can
take good advantage of an O(1) size (though it does not result in a
complexity reduction).
When list::resize is shrinking, an O(1) size can be used to choose
whether it is better to iterate from begin to the start of the erase
range, or from end to the start of the erase range. Indeed, I've seen
implementations of list::resize that have an O(N) size and the first
thing they do is compute distance(begin(), end()).
For operator== and operator!= for list one can check size() first (if it
is O(1)) before continuing with the element by element check,
potentially making these operations more efficient for common cases.
For list assignment (operator=, and assign overloads), the exception
safety guarantee can be increased from from basic to strong for the case
that T's assignment has a nothrow guarantee (at no extra expense).
Trying to do this with an O(N) size is computationally not practical.
list::sort is simpler to implement, and potentially slightly faster if
one can use an O(1) size to efficiently bisect the list in preparation
for a merge sort.
The cost of updating the size data within list to support an O(1) size
does not significantly effect any function, much less change its
complexity (except of course for the "splice some from other" function
already stated).
For my money, the pros outweigh the cons by a significant margin for an
O(1) list::size. Not the least of which is that (if standardized)
clients could depend upon list::size portably.
-Howard
