Q: change position of list element without invalidation

Discussion in 'C++' started by Jakob Bieling, Nov 1, 2006.

  1. 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)
     
    Jakob Bieling, Nov 1, 2006
    #1
    1. Advertising

  2. Re: change position of list element without invalidation

    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
     
    Victor Bazarov, Nov 1, 2006
    #2
    1. Advertising

  3. Re: change position of list element without invalidation

    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)
     
    Jakob Bieling, Nov 1, 2006
    #3
  4. Re: change position of list element without invalidation

    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
     
    Victor Bazarov, Nov 1, 2006
    #4
  5. Re: change position of list element without invalidation

    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)
     
    Jakob Bieling, Nov 1, 2006
    #5
  6. 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_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.
     
    Gianni Mariani, Nov 1, 2006
    #6
  7. 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_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
    >> 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)
     
    Jakob Bieling, Nov 2, 2006
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?Utf-8?B?b251cmJ5aw==?=

    variable cache invalidation

    =?Utf-8?B?b251cmJ5aw==?=, Jul 5, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    354
    =?Utf-8?B?b251cmJ5aw==?=
    Jul 5, 2004
  2. Vikram

    ASP.NET 2.0 cache invalidation

    Vikram, Jan 16, 2006, in forum: ASP .Net
    Replies:
    1
    Views:
    463
    Julie Lerman
    Jan 16, 2006
  3. Mark P
    Replies:
    2
    Views:
    396
    John Harrison
    Sep 20, 2005
  4. Replies:
    1
    Views:
    242
    James Kanze
    Jan 25, 2008
  5. Ben Pfaff
    Replies:
    2
    Views:
    349
    Ben Pfaff
    Feb 1, 2008
Loading...

Share This Page