Q: change position of list element without invalidation

[Jakob Bieling]

Hi,

I want to move an element from a std::list to the end of the same list.
To get this done, I thought I'd just do something like:

std::list <int> lst;
lst.push_back (0);
lst.push_back (1);
lst.push_back (2);
lst.splice (lst.end (), lst, lst.begin (), ++ lst.begin ());

This does change the list from [0, 1, 2] to [1, 2, 0]. The problem is,
that any iterators I have pointing to '0' are now invalid. Are there ways to
get this done without invalidating my iterators? Theoretically, it should be
possible (if I would reimplement a list container myself), shouldn't it?
Does the Standard provide methods to achieve this?

Now for some more background information: The application is a server
and the list holds all connected clients. Whenever some action has been
taken, the corrensponding element in the list is moved[*] to the end of the
list. This way, the first element will always be the client that has
responded (or has been served) _least_ recently. Along with the time, I can
easily timeout on any client. I just examine the first element in the
"client list", wait at most some time T (which I can calculate now) and if
nothing happened with this client during that time, I know it has timed out.
As it stands, splice would be perfect. But I also manage another list with
iterators into the "client list". That list is a "job list" and holds
iterators to clients, that have pending jobs (pending, because a request is
already being processed for that client and requests can only be satisfied
in the same order they arrive). And this is the problem. When moving a
client to the end of the "client list", the "job list" could then contain
invalid iterators.

One solution would be, to store the actual client structures somewhere
else (for example yet another list) and have both the "client list" and the
"job list" just contain iterators into that "store list". This would solve
it all, really, but I am not quite happy with this solution. It feels
somewhat clumsy. I'd appreciate any more thoughts on this!

[*] (I do not want to actually move any memory, but instead just
rearrange the next/prev node-links.. but I just realize that I am not even
sure whether splice may deep-copy or not ..)

Thanks for your help!

 

[Victor Bazarov]

Hi,

I want to move an element from a std::list to the end of the same
list. To get this done, I thought I'd just do something like:

std::list <int> lst;
lst.push_back (0);
lst.push_back (1);
lst.push_back (2);
lst.splice (lst.end (), lst, lst.begin (), ++ lst.begin ());

This does change the list from [0, 1, 2] to [1, 2, 0]. The problem
is, that any iterators I have pointing to '0' are now invalid. Are
there ways to get this done without invalidating my iterators?
Theoretically, it should be possible (if I would reimplement a list
container myself), shouldn't it? Does the Standard provide methods to
achieve this?

I think you're looking to 'erase' the iterator and then 'insert' the
value where you need it. None of the interators (except the one which
you're manipulating) is invalidated.

[..]

V

 

[Jakob Bieling]

Victor Bazarov wrote:

Jakob Bieling wrote:

I want to move an element from a std::list to the end of the same
list. To get this done, I thought I'd just do something like:

std::list <int> lst;
lst.push_back (0);
lst.push_back (1);
lst.push_back (2);
lst.splice (lst.end (), lst, lst.begin (), ++ lst.begin ());

This does change the list from [0, 1, 2] to [1, 2, 0]. The problem
is, that any iterators I have pointing to '0' are now invalid. Are
there ways to get this done without invalidating my iterators?
Theoretically, it should be possible (if I would reimplement a list
container myself), shouldn't it? Does the Standard provide methods to
achieve this?

I think you're looking to 'erase' the iterator and then 'insert' the
value where you need it. None of the interators (except the one which
you're manipulating) is invalidated.

Yes, but that is the problem. I may have an iterator pointing to the
element I am placing at the end. And that iterator should still be valid
after changing the list. But as I do more and more research on this, I think
the, what I called "clumsy", solution with one list of elements and two
lists of iterators is the way to go after all. Comments welcome!

Thanks!

 

[Victor Bazarov]

Victor Bazarov wrote:

Jakob Bieling wrote:

I want to move an element from a std::list to the end of the same
list. To get this done, I thought I'd just do something like:

std::list <int> lst;
lst.push_back (0);
lst.push_back (1);
lst.push_back (2);
lst.splice (lst.end (), lst, lst.begin (), ++ lst.begin ());

This does change the list from [0, 1, 2] to [1, 2, 0]. The
problem is, that any iterators I have pointing to '0' are now
invalid. Are there ways to get this done without invalidating my
iterators? Theoretically, it should be possible (if I would
reimplement a list container myself), shouldn't it? Does the
Standard provide methods to achieve this?

I think you're looking to 'erase' the iterator and then 'insert' the
value where you need it. None of the interators (except the one
which you're manipulating) is invalidated.

Yes, but that is the problem. I may have an iterator pointing to
the element I am placing at the end. And that iterator should still
be valid after changing the list.

But that's impossible.

Let me take it back. It's possible. You can move all elements before
and after the iterator instead. But that would make any iterators to
those elements invalid.

But as I do more and more research
on this, I think the, what I called "clumsy", solution with one list
of elements and two lists of iterators is the way to go after all.
Comments welcome!

If you wrap it in a function that would return a new iterator, why
couldn't you simply do

template<class C>
typename C::iterator move_element(C& c, typename C::iterator from,
typename C::iterator before)
{
typename C::value_type v = *from;
c.erase(from);
return c.insert(before, v);
}
....
myiterator = move_element(mylist, myiterator, mylist.end());

Perhaps you're just too hung up on the design that you have (and it
is probably marvelous, I've no doubt), but don't dismiss other (and
probably simpler) solutions.

V

 

[Jakob Bieling]

Jakob Bieling wrote:

Victor Bazarov wrote:

Jakob Bieling wrote:
I want to move an element from a std::list to the end of the
same list. To get this done, I thought I'd just do something like:

std::list <int> lst;
lst.push_back (0);
lst.push_back (1);
lst.push_back (2);
lst.splice (lst.end (), lst, lst.begin (), ++ lst.begin ());

problem is, that any iterators I have pointing to '0' are now
invalid. [..]
I think you're looking to 'erase' the iterator and then 'insert' the
value where you need it. None of the interators (except the one
which you're manipulating) is invalidated.

Yes, but that is the problem. I may have an iterator pointing to
the element I am placing at the end. And that iterator should still
be valid after changing the list.

But that's impossible.

Let me take it back. It's possible. You can move all elements before
and after the iterator instead. But that would make any iterators to
those elements invalid.

Guess I am making too many assumptions about the implementation for this
to work. Or my idea is flawed. Ideally, if an iterator holds a pointer to a
node, changing the next/prev links of that node will not affect other
iterators to this element, because the node structure is still where it used
to be (ie. the memory address will not change).

If you wrap it in a function that would return a new iterator, why
couldn't you simply do

[ move function snipped]

Because then I would have traverse the "job list" to find a possible
iterator to the old element and update that. I was trying to get around
that.

Perhaps you're just too hung up on the design that you have (and it
is probably marvelous, I've no doubt), but don't dismiss other (and
probably simpler) solutions.

I guess I will just let it be for today and rethink this whole thing
tomorrow. Maybe I will find one of the simpler solutions Thanks for your
ideas!

regards

 

[Gianni Mariani]

This does change the list from [0, 1, 2] to [1, 2, 0]. The problem is,
that any iterators I have pointing to '0' are now invalid.

Are you sure ? Anyhow, I don't know what splice says about splicing
from the same container but I would not do it. I would splice the
element into a temporary container and then splice it back into the
original. In theory, the iterator should still be valid.

... Are there ways to
get this done without invalidating my iterators? Theoretically, it should be
possible (if I would reimplement a list container myself), shouldn't it?

You can implement something to do this yourself. In fact I have and
it's open source. It is in an unofficial version of the Austria C++
library that you can pull from

http://netcabletv.org/public_releases/nctv_pub-6126.tar.bz2

Warning - it's 100 megs. This contains a generic "activity list" type
that is used as a thread pool. It's quite simple to use. You don't
have to use it like a thread pool, you can bring in your own "thread
provider". This might be too specific.

There is also the "at::List" stuff which is as ugly as all get out but
it does also provide a way for an object to "know" which lists it's
connected to and to remove itself from any list.

The whole "self aware" object issue is something that the stl containers
make awfully difficult.

Does the Standard provide methods to achieve this?

Probably but with alot of complexity in client code. You can probably
write something simpler for client code yourself.

Now for some more background information: The application is a server
and the list holds all connected clients. Whenever some action has been
taken, the corrensponding element in the list is moved[*] to the end of the
list.

Wouldn't you want to remove it from the "active" list when somthing was
done and only place it back on the todo list once a new event occurred
that required work done on that connection ?

.... This way, the first element will always be the client that has

responded (or has been served) _least_ recently. Along with the time, I can
easily timeout on any client.

BTW, race conditions in this kind of code are very easy to create. I've
written servers like this many times (unfortunately) and it's quite
involved. In a multi threaded environment it is quite tricky to get right.

....

One solution would be, to store the actual client structures somewhere
else (for example yet another list) and have both the "client list" and the
"job list" just contain iterators into that "store list". This would solve
it all, really, but I am not quite happy with this solution. It feels
somewhat clumsy. I'd appreciate any more thoughts on this!

How do you clean up the iterators ?

[*] (I do not want to actually move any memory, but instead just
rearrange the next/prev node-links.. but I just realize that I am not even
sure whether splice may deep-copy or not ..)

list::splice does not do a deep copy. std::list assignment or copy
construct does.

 

[Jakob Bieling]

Jakob Bieling wrote:

This does change the list from [0, 1, 2] to [1, 2, 0]. The
problem is, that any iterators I have pointing to '0' are now
invalid.

Are you sure ? Anyhow, I don't know what splice says about splicing
from the same container but I would not do it. I would splice the

I just checked and it is guaranteed to work. But it officially
invalidates the iterators/references to spliced elements, which is the
problem.

You can implement something to do this yourself. In fact I have and
it's open source. It is in an unofficial version of the Austria C++
library that you can pull from

http://netcabletv.org/public_releases/nctv_pub-6126.tar.bz2

Thanks, I will have a look into that.

Now for some more background information: The application is a
server and the list holds all connected clients. Whenever some
action has been taken, the corrensponding element in the list is
moved[*] to the end of the list.

Wouldn't you want to remove it from the "active" list when somthing
was done and only place it back on the todo list once a new event
occurred that required work done on that connection ?

Well, the "active" list (I think this is what I called "client list"?)
contains all connected clients, no matter if they are currently waiting for
a request to be satisfied or not. I will only remove from there, when a
client disconnects. A client will only get into the "job list", when it has
sent a request while another one is for this client is still in progress.

... This way, the first element will always be the client that has

BTW, race conditions in this kind of code are very easy to create. I've
written servers like this many times (unfortunately) and it's
quite involved. In a multi threaded environment it is quite tricky
to get right.

Right, but this is a smaller server and thus single threaded. Otherwise
I would probably have used a lock-free list. But multithreading is nothing
to worry about here

How do you clean up the iterators ?

Using the above solution, I would already know which iterator in the
"client list" to remove (from the close-notification). For the job-list, I
still have to traverse that list and find the iterator. Since disconnects do
not happen that frequently, this is acceptable.

regards