Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Q: change position of list element without invalidation

Reply
Thread Tools

Q: change position of list element without invalidation

 
 
Jakob Bieling
Guest
Posts: n/a
 
      11-01-2006
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!
--
jb

(reply address in rot13, unscramble first)


 
Reply With Quote
 
 
 
 
Victor Bazarov
Guest
Posts: n/a
 
      11-01-2006
Jakob Bieling wrote:
> 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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask


 
Reply With Quote
 
 
 
 
Jakob Bieling
Guest
Posts: n/a
 
      11-01-2006
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!
--
jb

(reply address in rot13, unscramble first)


 
Reply With Quote
 
Victor Bazarov
Guest
Posts: n/a
 
      11-01-2006
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 ());
>>>
>>> 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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask


 
Reply With Quote
 
Jakob Bieling
Guest
Posts: n/a
 
      11-01-2006
Victor Bazarov wrote:

> 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).

>> 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


[ 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
--
jb

(reply address in rot13, unscramble first)


 
Reply With Quote
 
Gianni Mariani
Guest
Posts: n/a
 
      11-01-2006
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
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_release...b-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.
 
Reply With Quote
 
Jakob Bieling
Guest
Posts: n/a
 
      11-02-2006
Gianni Mariani wrote:
> 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.

>> ... 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_release...b-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
>> 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.


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

>> 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 ?


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
--
jb

(reply address in rot13, unscramble first)


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Position an element dynamically on top of an existing element Konrad Hammerer HTML 14 02-07-2008 11:34 PM
std::list<>::splice invalidation of iterators Ben Pfaff C++ 2 02-01-2008 03:03 AM
Object in list invalidation question matt.elkins@gmail.com C++ 1 01-25-2008 07:32 PM
list::splice and iterator invalidation Mark P C++ 2 09-20-2005 06:13 AM
variable cache invalidation =?Utf-8?B?b251cmJ5aw==?= ASP .Net 0 07-05-2004 02:53 PM



Advertisments