In article <pa************ *************** *@gmx.net>, Dhruv
<dh*******@gmx. net> wrote:
| > -----------
| >
| > 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).
|
| How would the client know n, again, distance would be a O(N)
| operation......
Often the work of defining the range to splice from is O(N) whether you
count the number of elements or not.
Please reread:
In article <11************ ************@me trowerks.com>, Howard Hinnant
<hi*****@metrow erks.com> wrote:
| 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.
In article <pa************ *************** *@gmx.net>, Dhruv
<dh*******@gmx. net> continued:
| It would be better to just stick to the current solution.
In article <11************ ************@me trowerks.com>, Howard Hinnant
<hi*****@metrow erks.com> wrote:
| as an addition to the existing interface.
How does this addition to the current interface make the situation
worse? If you don't know n, just don't supply it. I'm not proposing
to remove any existing signatures. And the addition does not create
any ambiguities or other problems that I can see.
void splice(iterator position, list& x);
void splice(iterator position, list& x, iterator i);
void splice(iterator position, list& x, iterator first, iterator last);
void splice(iterator position, list& x, iterator first, iterator last,
size_type n); // proposed
| Actually, there
| are many ways to implement this particular splice O(N) for size() == (1).
| I'd like to know which one would be the best.
| Some that come to mind are:
|
| 1. Individually decrement size for the other list, and increment the
| current size, while splicing the individual elements (seems like
| inefficient).
Seems inefficient to me too.
| 2. Splice the range into a temporary list, and then the size for that list
| is known, so its fine. Again, here, we will have to use a special splice,
| which does not do anything to size, so it can be O(1). Then, we subtract,
| and add size() of the temporary list to the other list, and *this.
How does the temporary list know the size?
| 3. Same thing as (2), but in a loop.
You've lost me on that one.
The best way I know of to implement
void splice(iterator position, list& x, iterator first, iterator last);
(assuming O(1) size)
is to first check if the range [first, last) is empty and if so, do
nothing. Then if this != &x, compute the distance [first, last) and
subtract that amount from x.size() and add it to this->size(). Then
(regardless if this == &x or not) twiddle the links at first and at
last to disconnect [first, last) from x, and connect it to *this.
No need to visit each node, except for computing distance(first, last).
No need for a temporary list.
In the proposed variant, there is no need to compute distance(first,
last) as it is supplied by the client. Though a debug build might
compute distance(first, last) anyway just to make sure the client knows
what he's talking about.
--
Howard Hinnant
Metrowerks
