Any fast method to swap two nodes in a STL list?

[Atlas]

To swap to nodes in list, changing pointers is enough. But the stl swap
method seems to copy their values, doesn't it?

[Mike Wahler]

"Atlas" <Ma*****@gmail.com> wrote in message
news:11*********************@f14g2000cwb.googlegro ups.com...

To swap to nodes in list, changing pointers is enough. But the stl swap
method seems to copy their values, doesn't it?

All standard library containers have copy semantics.
Why is this a problem?

-Mike

[John Harrison]

Atlas wrote:

To swap to nodes in list, changing pointers is enough. But the stl swap
method seems to copy their values, doesn't it?

std::list have several methods called 'splice' which can move nodes in a
list without copying.

john

[Kristo]

John Harrison wrote:

Atlas wrote:

To swap to nodes in list, changing pointers is enough. But the stl swap
method seems to copy their values, doesn't it?

std::list have several methods called 'splice' which can move nodes in a
list without copying.

That's not allowed for what he wants to do. A list may not splice()
with itself.

Kristo

[Kristo]

Atlas wrote:

To swap to nodes in list, changing pointers is enough. But the stl swap
method seems to copy their values, doesn't it?

In general, yes. But std::swap is specialized for all of the standard
container classes, so calling swap on two list elements probably just
exchanges pointers.

Kristo

[Andrew Koenig]

"Kristo" <kr*******@gmail.com> wrote in message
news:11**********************@g14g2000cwa.googlegr oups.com...

That's not allowed for what he wants to do. A list may not splice()
with itself.

Use splice to move the elements in question into another list, then use
splice again to move them back.

[Shezan Baig]

Kristo wrote:

John Harrison wrote:

Atlas wrote:

To swap to nodes in list, changing pointers is enough. But the stl swap
method seems to copy their values, doesn't it?

std::list have several methods called 'splice' which can move nodes in a
list without copying.

That's not allowed for what he wants to do. A list may not splice()
with itself.

Isn't there an overloaded splice that does allow the list to be the
same? I got the following from the SGI STL documentation, but I'll be
suprised if it wasn't in the standard:

void splice(iterator position,
list<T, Alloc>& x,
iterator i);
"position must be a valid iterator in *this, and i must be a
dereferenceable iterator in x. Splice moves the element pointed to by i
from x to *this, inserting it before position. All iterators remain
valid, including iterators that point to elements of x. If position ==
i or position == ++i, this function is a null operation. This function
is constant time."
Hope this helps,
-shez-

[John Harrison]

Kristo wrote:

John Harrison wrote:

Atlas wrote:

To swap to nodes in list, changing pointers is enough. But the stl swap
method seems to copy their values, doesn't it?

std::list have several methods called 'splice' which can move nodes in a
list without copying.

That's not allowed for what he wants to do. A list may not splice()
with itself.

Kristo

There are three different versions of splice. Two of them allow a list
to splice with itself. It all depends on precisely what the OP wants to do.

john

[Atlas]

John Harrison wrote:

Kristo wrote:

John Harrison wrote:

Atlas wrote:

To swap to nodes in list, changing pointers is enough. But the stl swap
method seems to copy their values, doesn't it?
std::list have several methods called 'splice' which can move nodes in a
list without copying.

That's not allowed for what he wants to do. A list may not splice()
with itself.

Kristo

There are three different versions of splice. Two of them allow a list
to splice with itself. It all depends on precisely what the OP wants to do.

john

Unfortunately I didn't find any one like "Two of them allow a list to
splice with itself".

[Ivan Vecerina]

"Kristo" <kr*******@gmail.com> wrote in message
news:11**********************@g43g2000cwa.googlegr oups.com...
: Atlas wrote:
: > To swap to nodes in list, changing pointers is enough. But the stl
swap
: > method seems to copy their values, doesn't it?
:
: In general, yes. But std::swap is specialized for all of the standard
: container classes, so calling swap on two list elements probably just
: exchanges pointers.
It doesn't.
If you call swap on two iterators, it is the iterators that will be
swapped.
If you swap the dereferenced iterators, std::swap will have no way to know
that both elements are part of a list. And the side effect of swapping
the values, anyway, are different from those of exchanging the position
of two list items.
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form

[Ivan Vecerina]

"Atlas" <Ma*****@gmail.com> wrote in message
news:11**********************@f14g2000cwb.googlegr oups.com...
: John Harrison wrote:
....
: > >>Atlas wrote:
: > >>
: > >>>To swap to nodes in list, changing pointers is enough. But the stl
swap
: > >>>method seems to copy their values, doesn't it?
....
: > There are three different versions of splice. Two of them allow a list
: > to splice with itself. It all depends on precisely what the OP wants
to do.
: >
: > john
:
: Unfortunately I didn't find any one like "Two of them allow a list to
: splice with itself".

I'm surprised this thread does not seem to get anywhere yet: this problem
ought to have a reasonably simple solution.
So let me concretely give it a try.

The easiest seems to use the second form of list.splice().
From the standard:
<<<
void splice(iterator position, list<T,Allocator>& x, iterator i);

Effects: Inserts an element pointed to by i from list x before position
and removes the element from x.
The result is unchanged if position == i or position == ++i. Invalidates
only the iterators and references to the spliced element.
Throws: Nothing
Requires: i is a valid dereferenceable iterator of x.
Complexity: Constant time.

Since you can have position==i, it seems obvious that x can be the same
list as 'this'.

So wouldn't something like the following work?
template<class T, class Allocator>
void swap_list_items
( std::list<T,Allocator>& l
, std::list<T,Allocator>::iterator a
, std::list<T,Allocator>::iterator b
)
{
std::list<T,Allocator>::iterator aPlus = a;
++aPlus; // after position of a, will not be invalidated
l.splice( b, l, a ); // move a before b, invalidates a
l.splice( aPlus, l, b ); // move b before aPlus (where A was)
}

This untested snippet is just a proposed solution, for others to review,
and might be buggy. But I'm sure we can work something out ;)

Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form