Doesn't std::map.erase returns iterator?

Discussion in 'C++' started by Jim Langston, Mar 29, 2008.

  1. Jim Langston

    Jim Langston Guest

    I have a project that compiles in Microsoft Visual C++ .net 2003. I'm
    trying to compile it in Dev C++ to try to get some optimization. However, I
    get an error on this code which seems to tell me it can't assign the
    iterator.:

    typedef std::map<unsigned int, CEffect*> BeamEffectsType;

    // ...

    // Update ALL the -On-The-Fly- or Fired 'Beams' to NEW positions.
    for ( BeamEffectsType::iterator it = Client.BeamEffects.begin(); it !=
    Client.BeamEffects.end(); )
    {
    if ( !(*it).second->Update() )
    {
    delete (*it).second;
    it = Client.BeamEffects.erase(it);
    }
    else
    ++it;
    }

    Where BeamEffects in Client is a BeamEffectsType.

    Abyssal.cpp:2313: error: no match for 'operator=' in 'it =
    (((BeamEffectsType*)(&Client)) + 208324u)->std::map<_Key, _Tp, _Compare,
    _Alloc>::erase [with _Key = unsigned int, _Tp = CEffect*, _Compare =
    std::less<unsigned int>, _Alloc = std::allocator<std::pair<const unsigned
    int, CEffect*> >](it)'
    e:/Dev-Cpp/include/c++/3.4.2/bits/stl_tree.h:152: note: candidates are:
    std::_Rb_tree_iterator<std::pair<const unsigned int, CEffect*> >&
    std::_Rb_tree_iterator<std::pair<const unsigned int, CEffect*>
    >::eek:perator=(const std::_Rb_tree_iterator<std::pair<const unsigned int,

    CEffect*> >&)

    The line 2313 being
    it = Client.BeamEffects.erase(it);

    It shows the same error in another part of the code where I'm doing the same
    thing with the BeamEffects. Is MSVC++ returning an iterator for a std::map
    as an extension, is DevC++ not returning an iterator when it should, or am I
    doing something else wrong that I can't tell?

    Thanks.

    --
    Jim Langston
     
    Jim Langston, Mar 29, 2008
    #1
    1. Advertising

  2. On Sat, 29 Mar 2008 10:07:29 -0700, Jim Langston wrote:

    > I have a project that compiles in Microsoft Visual C++ .net 2003. I'm
    > trying to compile it in Dev C++ to try to get some optimization.
    > However, I get an error on this code which seems to tell me it can't
    > assign the iterator.:
    >
    > typedef std::map<unsigned int, CEffect*> BeamEffectsType;
    >
    > // ...
    >
    > // Update ALL the -On-The-Fly- or Fired 'Beams' to NEW positions.
    > for ( BeamEffectsType::iterator it = Client.BeamEffects.begin(); it
    > !=
    > Client.BeamEffects.end(); )
    > {
    > if ( !(*it).second->Update() )
    > {
    > delete (*it).second;
    > it = Client.BeamEffects.erase(it);
    > }
    > else
    > ++it;
    > }
    >
    > Where BeamEffects in Client is a BeamEffectsType.
    >
    > Abyssal.cpp:2313: error: no match for 'operator=' in 'it =
    > (((BeamEffectsType*)(&Client)) + 208324u)->std::map<_Key, _Tp, _Compare,
    > _Alloc>::erase [with _Key = unsigned int, _Tp = CEffect*, _Compare =
    > std::less<unsigned int>, _Alloc = std::allocator<std::pair<const
    > unsigned int, CEffect*> >](it)'
    > e:/Dev-Cpp/include/c++/3.4.2/bits/stl_tree.h:152: note: candidates are:
    > std::_Rb_tree_iterator<std::pair<const unsigned int, CEffect*> >&
    > std::_Rb_tree_iterator<std::pair<const unsigned int, CEffect*>
    > >::eek:perator=(const std::_Rb_tree_iterator<std::pair<const unsigned int,

    > CEffect*> >&)
    >
    > The line 2313 being
    > it = Client.BeamEffects.erase(it);
    >
    > It shows the same error in another part of the code where I'm doing the
    > same thing with the BeamEffects. Is MSVC++ returning an iterator for a
    > std::map as an extension,


    Yes.

    is DevC++ not returning an iterator when it
    > should, or am I doing something else wrong that I can't tell?
    >
    > Thanks.


    http://www.cplusplus.com/reference/stl/map/erase.html

    --
    OU
     
    Obnoxious User, Mar 29, 2008
    #2
    1. Advertising

  3. Jim Langston

    Jim Langston Guest

    Obnoxious User wrote:
    > On Sat, 29 Mar 2008 10:07:29 -0700, Jim Langston wrote:
    >

    [SNIP]
    >>
    >> typedef std::map<unsigned int, CEffect*> BeamEffectsType;
    >>
    >> // ...
    >>
    >> for ( BeamEffectsType::iterator it = Client.BeamEffects.begin(); it !=
    >> Client.BeamEffects.end(); )
    >> {

    [SNIP]
    >> it = Client.BeamEffects.erase(it);

    [SNIP]
    >> }
    >>
    >> Where BeamEffects in Client is a BeamEffectsType.
    >>
    >> [SNIP]. Is MSVC++ returning an iterator for a std::map as an extension,

    >
    > Yes.
    >

    [SNIP]

    Ahh, dang. I understand that in C++0x all container erases/deletes will
    return an iterator, but that doesn't help me now. It means I'm going to
    have to come up with a new algorithm for one I found quite useful and was
    content with.

    I don't see anything in the documentation stating if .erase invalidates
    iterators for a map. My guessing is it doesn't, allowing me to use:

    for ( BeamEffectsType::iterator it = Client.BeamEffects.begin(); it !=
    Client.BeamEffects.end(); )
    {

    Client.BeamEffects.erase(it++);

    }

    I'm a little hesitant to even think about that being well defined, however,
    since it would be incrementing an iterator that would no longer be valid.
    If that is not valid I would have to do something like:

    for ( BeamEffectsType::iterator it = Client.BeamEffects.begin(); it !=
    Client.BeamEffects.end(); )
    {
    BeamEffectsType::iterator sit = it + 1;
    Client.BeamEffects.erase(it);
    it = sit;
    }

    although I might have to use .advance or something not sure if map iterators
    have + overriden.

    What is a normal algorithm for erasing some entries in a map while iterating
    over them? Even if using an index size_t and a for loop I'm going to have
    to go thorugh shenanigans.




    --
    Jim Langston
     
    Jim Langston, Mar 29, 2008
    #3
  4. Jim Langston

    Greg Herlihy Guest

    On Mar 29, 3:10 pm, "Jim Langston" <> wrote:
    > I don't see anything in the documentation stating if .erase invalidates
    > iterators for a map.  My guessing is it doesn't, allowing me to use:


    Yes, std::map iterators are "stable" - so erasing one std::map
    iterator never invalidates any other iterators in the map.

    >  for ( BeamEffectsType::iterator it =  Client.BeamEffects.begin(); it !=
    > Client.BeamEffects.end(); )
    > {
    >
    >    Client.BeamEffects.erase(it++);
    >
    > }
    >
    > I'm a little hesitant to even think about that being well defined, however,
    > since it would be incrementing an iterator that would no longer be valid.


    No, there is no danger because "it" is incremented -before- the call
    to erase() (and a copy of "it" with its previous value is the argument
    actually passed to erase()). So your algorithm has well-defined
    behavior.

    Greg
     
    Greg Herlihy, Mar 29, 2008
    #4
  5. Jim Langston

    Alan Johnson Guest

    Jim Langston wrote:
    > for ( BeamEffectsType::iterator it = Client.BeamEffects.begin(); it !=
    > Client.BeamEffects.end(); )
    > {
    >
    > Client.BeamEffects.erase(it++);
    >
    > }
    >
    > I'm a little hesitant to even think about that being well defined


    As Greg Herlihy pointed out, your algorithm here is well defined.
    However, there are some more elegant ways of accomplishing the same
    thing. If your goal is to erase every element, as that loop would, then
    use:

    Client.BeamEffects.clear();

    If your goal is to erase everything in the range [iter1, iter2), use:

    Client.BeamEffects.erase(iter1, iter2);

    There is rarely a need to write this sort of manual erase loop.

    --
    Alan Johnson
     
    Alan Johnson, Mar 30, 2008
    #5
  6. Jim Langston

    Alan Johnson Guest

    Alan Johnson wrote:
    > Jim Langston wrote:
    >> for ( BeamEffectsType::iterator it = Client.BeamEffects.begin(); it
    >> != Client.BeamEffects.end(); )
    >> {
    >>
    >> Client.BeamEffects.erase(it++);
    >>
    >> }
    >>
    >> I'm a little hesitant to even think about that being well defined

    >
    > As Greg Herlihy pointed out, your algorithm here is well defined.
    > However, there are some more elegant ways of accomplishing the same
    > thing. If your goal is to erase every element, as that loop would, then
    > use:
    >
    > Client.BeamEffects.clear();
    >
    > If your goal is to erase everything in the range [iter1, iter2), use:
    >
    > Client.BeamEffects.erase(iter1, iter2);
    >
    > There is rarely a need to write this sort of manual erase loop.
    >


    My apologies. I just re-read the rest of the thread and realized what I
    was replying to was taken a bit out of context. In the case where you
    are wanting to manipulate some items and erase others your loop above
    seems to me to be the right approach.

    --
    Alan Johnson
     
    Alan Johnson, Mar 30, 2008
    #6
  7. Jim Langston

    James Kanze Guest

    On 30 mar, 00:10, "Jim Langston" <> wrote:
    > Obnoxious User wrote:
    > > On Sat, 29 Mar 2008 10:07:29 -0700, Jim Langston wrote:


    > [SNIP]


    > >> typedef std::map<unsigned int, CEffect*> BeamEffectsType;


    > >> // ...


    > >> for ( BeamEffectsType::iterator it = Client.BeamEffects.begin(); it !=
    > >> Client.BeamEffects.end(); )
    > >> {

    > [SNIP]
    > >> it = Client.BeamEffects.erase(it);

    > [SNIP]
    > >> }


    > >> Where BeamEffects in Client is a BeamEffectsType.


    > >> [SNIP]. Is MSVC++ returning an iterator for a std::map as an extension,


    > > Yes.


    > [SNIP]


    > Ahh, dang. I understand that in C++0x all container
    > erases/deletes will return an iterator,


    They do now, but for some reason, they didn't in the original
    version of the standard. Some library implementations went
    ahead and had them return the iterator anyway (preferring common
    sense, usability and good programming practice to strict
    conformance), others didn't.

    Just replace the line in question with:
    Client.BeamEffects.erase(it);
    > I don't see anything in the documentation stating if .erase
    > invalidates iterators for a map.


    It invalidates any iterators to the element which is removed,
    but that's all.

    > I'm a little hesitant to even think about that being well
    > defined, however, since it would be incrementing an iterator
    > that would no longer be valid.


    It increments the iterator before calling erase. While the
    original value is still valid. It passes a copy of the original
    value to erase(), but the iterator in your code already points
    to the next element. (Note that a function call is a sequence
    point, so the side effects of the ++ operator must have occured
    before the function is called.)

    --
    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, Mar 30, 2008
    #7
  8. Jim Langston

    Jerry Coffin Guest

    In article <yHuHj.853$>,
    says...

    [ ... ]

    > // Update ALL the -On-The-Fly- or Fired 'Beams' to NEW positions.
    > for ( BeamEffectsType::iterator it = Client.BeamEffects.begin(); it !=
    > Client.BeamEffects.end(); )
    > {
    > if ( !(*it).second->Update() )
    > {
    > delete (*it).second;
    > it = Client.BeamEffects.erase(it);
    > }
    > else
    > ++it;
    > }


    You've gotten a number of replies that cover the question you asked.
    Since you mention doing this at a number of points in the code, you
    _might_ consider wrapping this up into an algorithm, something like
    this:

    // warning: none of the code in this post has been tested.
    //
    template <class Iterator, class bool_func, class deleter_func>
    void apply_if(Iterator b, Iterator e, bool_func f, appl_func d) {
    Iterator i=b;
    while (i!=e)
    if (f(*i))
    d(*i);
    else
    ++i;
    }

    Then you could use the binders from the standard library, or
    (preferably) TR1 and/or Boost to bind the arguments correctly.
    Alternatively, you could write thoes bits of code yourself:

    template <class Iterator>
    bool Update2nd(Iterator i) {
    return i->second->Update();
    }

    template <class Collection>
    class del2nd {
    Collection &c_;
    public:
    del2nd(Collection &c) :c_(c) {}

    void operator()(typename Collection::iterator it) {
    delete it->second;
    c_.erase(it);
    }
    };

    template <class Collection>
    del2nd<Collection> deleter(Collection &c) {
    return del2nd<Collection>(c);
    }

    Using this would look something like:

    apply_if(Client.BeamEffects.begin(), Client.BeamEffects.end(),
    std::not(Update2nd), deleter(Client.BeamEffects));

    If you don't mind your code working a bit differently from the way most
    of the (current) library does, you can simlify that a bit:

    template <class Collection, class bool_func, class deleter>
    void erase_if(Collection &c, bool_func f, deleter d) {
    typename Collection::iterator it = c.begin();
    while (it!=c.end())
    if (f(*it)) {
    d(*it);
    c.erase(it++);
    }
    else
    ++it;
    }

    In thise case, your binders would look something like:

    template <class Iterator>
    bool NotUpdate2nd(Iterator it) {
    return !it->second->Update();
    }

    template <class Iterator>
    void del2nd(Iterator it) {
    delete it->second;
    }

    and using it would be something like:

    erase_if(Client.BeamEffects, NotUpdate2nd, del2nd);

    Of course, it may be open to debate whether (either of these) is really
    a good idea or not.

    They do isolate the tricky bit of code incrementing the iterator into
    one place. With careful name choices, they may also make the intent a
    great deal clearer.

    OTOH, especially with poor name choices they could obfuscate the intent.
    Even though the binders are individually trivial and easy to understand,
    enough of them can be a pain to maintain. They also take what was one
    piece of code and break it up into a number of separate pieces, so
    following everything that's going on can be a bit of a pain.

    As it stands right now, I'd say the code above is open to considerable
    improvement -- in particular, instead of 'del2nd' and 'NotUpdate2nd',
    I'd prefer something that referred directly to what's logically
    happening with the object stored as the assoicated data in
    Client.BeamEffects. OTOH, if you have a number of different maps for
    different things and you carry out similar actions on all of them, being
    more generic like this is may be more readable.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
     
    Jerry Coffin, Mar 30, 2008
    #8
    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. Angus Leeming
    Replies:
    5
    Views:
    2,952
    Howard Hinnant
    Feb 4, 2004
  2. Pieter Thysebaert

    STL std::map erase

    Pieter Thysebaert, May 13, 2004, in forum: C++
    Replies:
    26
    Views:
    14,328
    Robbie Hatley
    May 14, 2004
  3. Replies:
    6
    Views:
    697
    Jim Langston
    Oct 30, 2005
  4. erase vs. erase

    , Mar 25, 2006, in forum: C++
    Replies:
    7
    Views:
    391
    Pete Becker
    Mar 30, 2006
  5. Dalbosco J-F
    Replies:
    3
    Views:
    908
    Marcus Kwok
    Aug 3, 2006
Loading...

Share This Page