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

J

Jim Langston

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 said:
>::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.
 
O

Obnoxious User

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 said:
::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
 
J

Jim Langston

Obnoxious said:
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.
 
G

Greg Herlihy

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
 
A

Alan Johnson

Jim said:
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.
 
A

Alan Johnson

Alan said:
Jim said:
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.
 
J

James Kanze

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

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

Jerry Coffin

[ ... ]
// 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.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top