In article <3f************ ***@News.CIS.DF N.DE>, Alf P. Steinbach
<al***@start.no > wrote:
| What it illustrates is, I believe, a design _defect_: the arguments
| of list::splice do not seem to offer (the implementation) any way to pass
| in the size of the range although that size might well be known by the
| client code.
|
| The decision seems to have been to "go safe" with a very low-
| level and general specification of a range. I think "go safe" is not
| compatible with a very low-level and general specification. In short,
| I think that that choice (efficiency versus safety) should be the
| library user's decision to make, not something forced and frozen,
| especially since there are so many other ways of introducing bugs.
Agreed. It would be great to add an additional splice signature:
void splice(iterator position, list& x, iterator first, iterator last,
size_type n);
Precondition: n == distance(first, last)
I reviewed the places I'm using splice: Most of the time I'm splicing
in an entire list, so this isn't an issue (it's always constant time).
But in one place I'm splicing in a range. And in that particular
example, I already know n before I call splice. It is a waste to have
list::splice recompute it.
-----------
Another aspect of this eternal debate that usually gets neglected is
that an O(1) size can also aid several other list operations. It
doesn't actually change the complexity of any of these other functions,
but it does make them faster (sometimes significantly so), or enable
strong exception safety in some circumstances:
resize
operator==
operator!=
operator=
assign
maybe sort
For example, in resize you just have to flat out compute size if you
don't already have it, so that you can decide whether you want to
append or erase.
In operator== you can check size first (if it is O(1)) and avoid the
element to element compare if the size's are different.
In operator= and assign you can use O(1) size to bump the exception
safety from basic to strong if T::operator= doesn't throw, at no
addtional computational or memory expense, while at the same time
recycling existing nodes as needed.
-----------
On the "lazy-size" concept: It seems to me like a significant amount
of logic/checking/code in order to avoid this one operation under
void splice(iterator position, list& x, iterator first, iterator last)
{
...
size_type delta_size = distance(first, last);
...
}
When you take into account increased code size, possibly increased
per-container overhead, and possible increased run-time checking in
most of the other list members, it seems like a heavy price to pay just
to avoid computing the distance between first and last in this one
function (which the standard says has linear complexity).
-----------
<shrug> The standard says that list::size() /should/ have constant
complexity. It also says that deque::size() /should/ have constant
complexity. Can you imagine the noise it would generate if someone
decided to ship a deque (or vector or string or map) with a size()
function that was O(N)?
Personally I would rather get a compile time error if list::size() was
O(N). At least then I would know that I need to distance(l.begi n(),
l.end()) and the computational cost would be clear and explicit. Same
logic goes against list::operator[](size_type). It would be easy to
implement, but unexpectedly expensive.
-----------
All that being said, I'd still love to see:
void splice(iterator position, list& x,
iterator first, iterator last, size_type n);
Precondition: n == distance(first, last)
as an addition to the existing interface. I believe such an addition
would settle this debate once and for all. And then we could make
std::container: :size() O(1), instead of "should be" O(1).
--
Howard Hinnant
Metrowerks
