std::list remove element mid iteration

Discussion in 'C++' started by Christopher, Dec 20, 2007.

  1. Christopher

    Christopher Guest

    The situation is that a std::list<std::set<std::string> > is being
    iterated through. Upon certain criteria some sets become empty. I need
    to remove the empty sets from the list.

    Is it safe to iterate through a list and call list::erase( iterator )
    in mid iteration?
     
    Christopher, Dec 20, 2007
    #1
    1. Advertising

  2. Christopher

    red floyd Guest

    Christopher wrote:
    > The situation is that a std::list<std::set<std::string> > is being
    > iterated through. Upon certain criteria some sets become empty. I need
    > to remove the empty sets from the list.
    >
    > Is it safe to iterate through a list and call list::erase( iterator )
    > in mid iteration?


    Well, you can use

    struct set_is_empty
    {
    bool operator()(const std::set& s) const { return s.empty(); }
    };

    std::erase(std::remove_if(l.begin(), l.end(), set_is_empty());

    or else, the canonical iteration for this list is:

    for (it = l.begin(); it != l.end(); )
    if (it->empty())
    it = l.erase(it);
    else
    ++it;
     
    red floyd, Dec 20, 2007
    #2
    1. Advertising

  3. Christopher

    red floyd Guest

    red floyd wrote:
    > Christopher wrote:
    >> The situation is that a std::list<std::set<std::string> > is being
    >> iterated through. Upon certain criteria some sets become empty. I need
    >> to remove the empty sets from the list.
    >>
    >> Is it safe to iterate through a list and call list::erase( iterator )
    >> in mid iteration?

    >
    > Well, you can use
    >
    > struct set_is_empty
    > {
    > bool operator()(const std::set& s) const { return s.empty(); }
    > };
    >
    > std::erase(std::remove_if(l.begin(), l.end(), set_is_empty());

    crap. That should be:

    l.erase(std::remove_if(l.begin(), l.end(), set_is_empty()), l.end());
    >
    > or else, the canonical iteration for this list is:
    >
    > for (it = l.begin(); it != l.end(); )
    > if (it->empty())
    > it = l.erase(it);
    > else
    > ++it;
     
    red floyd, Dec 20, 2007
    #3
  4. Christopher

    James Kanze Guest

    On Dec 20, 2:10 am, red floyd <> wrote:
    > Christopher wrote:
    > > The situation is that a std::list<std::set<std::string> > is being
    > > iterated through. Upon certain criteria some sets become empty. I need
    > > to remove the empty sets from the list.


    > > Is it safe to iterate through a list and call list::erase( iterator )
    > > in mid iteration?


    > Well, you can use


    > struct set_is_empty
    > {
    > bool operator()(const std::set& s) const { return s.empty(); }
    > };


    > std::erase(std::remove_if(l.begin(), l.end(), set_is_empty());


    Which could be unnecessarily expensive. In the case of
    std::list, the canonical form is:

    l.remove_if( set_is_empty() ) ;

    However, the original poster said that sets "become" empty
    during his iteration, so this can't be used.

    > or else, the canonical iteration for this list is:


    > for (it = l.begin(); it != l.end(); )
    > if (it->empty())
    > it = l.erase(it);
    > else
    > ++it;


    Adopted to his case, you'd add braces and put the if at the end
    of the loop. (Also, I'd write this with a while, rather than a
    for. Something like:

    std::list<...>::iterator iter = l.begin() ;
    while ( iter != l.end() ) {
    // processing...
    if ( iter->empty() ) {
    iter = l.erase( iter ) ;
    } else {
    ++ iter ;
    }
    }

    I'd prefer even more if that if could be replaced with a ?: on
    the right side of an assignment, since the most important aspect
    here is the update of the iterator, and not how it's being
    updated, but I can't think of a nice way of doing this off hand.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Dec 20, 2007
    #4
  5. Christopher

    Guest

    On 12ÔÂ20ÈÕ, ÏÂÎç5ʱ40·Ö, James Kanze <> wrote:
    > On Dec 20, 2:10 am, red floyd <> wrote:
    >
    > > Christopher wrote:
    > > > The situation is that a std::list<std::set<std::string> > is being
    > > > iterated through. Upon certain criteria some sets become empty. I need
    > > > to remove the empty sets from the list.
    > > > Is it safe to iterate through a list and call list::erase( iterator )
    > > > in mid iteration?

    > > Well, you can use
    > > struct set_is_empty
    > > {
    > > bool operator()(const std::set& s) const { return s.empty(); }
    > > };
    > > std::erase(std::remove_if(l.begin(), l.end(), set_is_empty());

    >
    > Which could be unnecessarily expensive. In the case of
    > std::list, the canonical form is:
    >
    > l.remove_if( set_is_empty() ) ;

    That is what I found in MSDN,
    remove_if is a STL algorithm which removes all elements from the range
    (First,Last) that cause the predicate to return true. It returns an
    iterator equal to Last - n, where n = number of elements removed. The
    last n elements of the range have undefined values. The size of the
    container remains the same.
    But there is a method named remove_if in std::list.
    template<class Predicate>
    void remove_if(
    Predicate _Pred
    )
    Erases elements from a list for which a specified predicate is
    satisfied.
    I didn't know there is a method named remove_if in the std::list. Can
    any one told me why there is no similar method in vector ?

    Thanks in advance,:)
     
    , Dec 20, 2007
    #5
  6. Christopher

    James Kanze Guest

    On Dec 20, 12:40 pm, "" <> wrote:
    > On 12月20æ—¥, 下åˆ5æ—¶40分, James Kanze <> wrote:


    > > On Dec 20, 2:10 am, red floyd <> wrote:


    > > > Christopher wrote:
    > > > > The situation is that a std::list<std::set<std::string> > is being
    > > > > iterated through. Upon certain criteria some sets become empty. I need
    > > > > to remove the empty sets from the list.
    > > > > Is it safe to iterate through a list and call list::erase( iterator )
    > > > > in mid iteration?
    > > > Well, you can use
    > > > struct set_is_empty
    > > > {
    > > > bool operator()(const std::set& s) const { return s.empty(); }
    > > > };
    > > > std::erase(std::remove_if(l.begin(), l.end(), set_is_empty());


    > > Which could be unnecessarily expensive. In the case of
    > > std::list, the canonical form is:


    > > l.remove_if( set_is_empty() ) ;


    > That is what I found in MSDN,
    > remove_if is a STL algorithm which removes all elements from the range
    > (First,Last) that cause the predicate to return true. It returns an
    > iterator equal to Last - n, where n = number of elements removed. The
    > last n elements of the range have undefined values. The size of the
    > container remains the same.
    > But there is a method named remove_if in std::list.
    > template<class Predicate>
    > void remove_if(
    > Predicate _Pred
    > )
    > Erases elements from a list for which a specified predicate is
    > satisfied.
    > I didn't know there is a method named remove_if in the std::list. Can
    > any one told me why there is no similar method in vector ?


    Because you don't need it, and it's not directly supported by
    the underlying data structure.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Dec 20, 2007
    #6
    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. Replies:
    6
    Views:
    660
    Jim Langston
    Oct 30, 2005
  2. Replies:
    3
    Views:
    336
    terminator
    Mar 25, 2007
  3. Andy
    Replies:
    3
    Views:
    490
    James Kanze
    Jun 8, 2007
  4. Javier
    Replies:
    0
    Views:
    399
    Javier
    Apr 18, 2008
  5. Rudi
    Replies:
    5
    Views:
    5,045
Loading...

Share This Page