Board index » cppbuilder » Iterators the fun never stops :)

Iterators the fun never stops :)


2004-01-16 06:04:35 AM
cppbuilder85
void remove1(std::list<int>& myList)
{
std::list<int>::iterator itrI = myList.begin();
while(itrI != myList.end())
{
if(*itrI == 4 || *itrI == 5)
{
myList.erase(itrI);
}
//******** Is this valid after I erase the iterator ****************
itrI++;
}
}
If the above is not valid how do I code it...I would still like to use the
while loop with itrI++ at the end of it.
Then based on some critera of *itrI remove it from the list and continue on
but I don't want to invalidate my iterators. Note this is one thread its
unrelated to my earlier question about iterators and threads.
 
 

Re:Iterators the fun never stops :)

Actually I know the remove1 function messes up the iterator...after the
first time it removes the iterator next time it reaches the if statement I
get an AV error.
 

Re:Iterators the fun never stops :)

I know I can use
myList.erase(4);
myList.erase(5);
This was a trivial example but I can't use something like that. Because in
my real code I'm not deleting them based on there key but I cast it to a
class and then call some class methods to determine if its time to delete it
yet.
 

{smallsort}

Re:Iterators the fun never stops :)

"JunkMail" < XXXX@XXXXX.COM >wrote in message
Quote
I know I can use

myList.erase(4);
myList.erase(5);
meant myList.remove(4); etc
 

Re:Iterators the fun never stops :)

"JunkMail" < XXXX@XXXXX.COM >wrote in message
Quote
//******** Is this valid after I erase the iterator ****************
Not for a vector, no. When you call erase() on a vector, the erased
iterator is invalid, as is every other iterator after it. However, erase()
returns the next valid iterator in the list, so your code should look more
like the following instead:
void remove1(std::list<int>& myList)
{
std::list<int>::iterator itrI = myList.begin();
while( itrI != myList.end() )
{
if( (*itrI == 4) || (*itrI == 5) )
itrI = myList.erase(itrI);
else
itrI++;
}
}
Better yet, why not just use the STL's remove_if() algorithm instead?
struct Is4Or5
{
bool operator()(const int val) const { return ( (val == 4) || (val
== 5) ); }
};
void remove1(std::list<int>& myList)
{
std::remove_if(myList.begin(), myList.end(), Is4Or5);
}
Gambit
 

Re:Iterators the fun never stops :)

"JunkMail" < XXXX@XXXXX.COM >writes:
Quote
void remove1(std::list<int>& myList)
{
std::list<int>::iterator itrI = myList.begin();
while(itrI != myList.end())
{
if(*itrI == 4 || *itrI == 5)
{
myList.erase(itrI);
}
//******** Is this valid after I erase the iterator ****************
no
Quote
itrI++;
}
}

If the above is not valid how do I code it...I would still like to use the
while loop with itrI++ at the end of it.
Ok, you do it like this
while(itrI != myList.end())
{
if(*itrI == 4 || *itrI == 5)
{
itrI = myList.erase(itrI);
}
else
{
itrI++;
}
}
For std::list, the erase() function returns the next valid iterator.
Otherwise, if you didn't erase something, just increment.
Remember this pattern, it comes up semi-frequently.
--
Chris (TeamB);
 

Re:Iterators the fun never stops :)

"Remy Lebeau \(TeamB\)" < XXXX@XXXXX.COM >writes:
Quote
Better yet, why not just use the STL's remove_if() algorithm instead?

struct Is4Or5
{
bool operator()(const int val) const {
return ( (val == 4) || (val == 5) ); }
};

void remove1(std::list<int>& myList)
{
std::remove_if(myList.begin(), myList.end(), Is4Or5);
}
This is a good suggestion except after calling remove_if (or any of
the non-member function "remove" algorithms), you have to erase the
invalid tail elements...
std::list<int>::iterator new_end =
std::remove_if(myList.begin(), myList.end(), Is4Or5);
MyList.erase(new_end, MyList.end());
--
Chris (TeamB);
 

Re:Iterators the fun never stops :)

Quote
For std::list, the erase() function returns the next valid iterator.
Otherwise, if you didn't erase something, just increment.

Remember this pattern, it comes up semi-frequently.
how about for a std::map? The erase returns void although the help file
says it returns an iterator to the next element? I coppied and pasted the
help for quick reference below. I've verified that it returns void...the
compiler gives an error saying can convert void to the iterator of the map.
"void erase(iterator position);
Deletes the map element pointed to by the iterator position. Returns an
iterator pointing to the element following the deleted element, or end() if
the deleted item was the last one in this list.
void erase(iterator first, iterator last);
If the iterators first and last point to the same map and last is reachable
from first, all elements in the range (first, last) are deleted from the
map. Returns an iterator pointing to the element following the last deleted
element, or end() if there were no elements after the deleted range."
 

Re:Iterators the fun never stops :)

Quote
"void erase(iterator position);
Deletes the map element pointed to by the iterator position. Returns an
iterator pointing to the element following the deleted element, or end() if
the deleted item was the last one in this list.
The help from stlport (don't know which BCB/STL you're using.
for std::map:
There are three, two that you describe and on that returns a size_t.
void erase(iterator position) //Erases the element pointed to by pos
size_type erase(const key_type&k) // Erases the element whose key is k
void erase(iterator first, iterator last) // Erases the elements pointed to in a range.
None say that they return an iterator. Two have a void type so they don't return
anything.
Which help are you using?
I imagine the question is (in the first case) what is pos after the erase.
I think with a list, it's the next position.
I'm fairly sure with a vector that it's invalid.
I'm not sure with a map but I would imagine it acts as a list. At any rate,
to test this, I don't think you want to check the return of erase but where
pos is after the erase.
 

Re:Iterators the fun never stops :)

"JunkMail" < XXXX@XXXXX.COM >writes:
Quote
>For std::list, the erase() function returns the next valid iterator.
>Otherwise, if you didn't erase something, just increment.
>
>Remember this pattern, it comes up semi-frequently.

how about for a std::map? The erase returns void although the help file
says it returns an iterator to the next element?
Then the help file is incorrect. Remember:
"If the map and the terrain disagree, trust the terrain" (Swiss army aphorism
quoted in D&E).
The idiom for map, uhh, std::map is like this: [adapted from Chris's code]
while(itrI != myMap.end())
{
if (shouldIErase(*itrI))
{
myMap.erase(itrI++);
}
else
{
++itrI;
}
}
Note that it once uses pre-increment (because that's more efficient, and I
assume that's what Chris meant to use as well) and once post-increment
(because it's needed).
The call myMap.erase(itrI++) invalidates the iterator object passed as
argument (and all other iterators referring to the same map element). This
isn't harmful becuase itrI has already been advance at that time.
Unlike std::vector and std::deque, std::map guarantees that only iterators
referring to the erased element are invalidated, hence this is safe.
std::list also gives this guarantee, so the above idiom would work for lists,
as well. I prefer using erase()'s return value, though, because that is more
in line with the other sequence containers; if std::vector is to be used
instead of std::list, no change is needed. Substituting std::vector for
std::list is more likely than substituting std::map for std::list.
 

Re:Iterators the fun never stops :)

XXXX@XXXXX.COM (Thomas Maeder [TeamB]) writes:
Quote
Note that it once uses pre-increment (because that's more efficient, and I
assume that's what Chris meant to use as well) and once post-increment
(because it's needed).
Yes, thanks.
Quote
The call myMap.erase(itrI++) invalidates the iterator object passed as
argument (and all other iterators referring to the same map element). This
isn't harmful becuase itrI has already been advance at that time.

Unlike std::vector and std::deque, std::map guarantees that only iterators
referring to the erased element are invalidated, hence this is safe.

std::list also gives this guarantee, so the above idiom would work for lists,
as well. I prefer using erase()'s return value, though, because that is more
in line with the other sequence containers; if std::vector is to be used
instead of std::list, no change is needed. Substituting std::vector for
std::list is more likely than substituting std::map for std::list.
It does seem weird that list.erase returns an interator but map.erase
does not. An unfortunate inconsistency.
--
Chris (TeamB);
 

Re:Iterators the fun never stops :)

Chris Uzdavinis (TeamB) < XXXX@XXXXX.COM >writes:
Quote
It does seem weird that list.erase returns an interator but map.erase
does not. An unfortunate inconsistency.
On de.comp.lang.iso-c++, I recently speculated that it's an instance of
"don't pay for what you don't need". Since all associative containers give
the necessary guarantees for the post-increment idiom to work, their erase()
member function needn't return an iterator.
std::list<>::erase() needn't either, but it may have been deemed appropriate
for it to be consistent with the other sequence containers.
Substituting once sequence container for another seems more likely than
substituting a std::deque for a std::map (and getting bitten by the different
return type).
But, as I said, that's mere speculation.
 

Re:Iterators the fun never stops :)

XXXX@XXXXX.COM (Thomas Maeder [TeamB]) writes:
Quote
But, as I said, that's mere speculation.
I think Josuttis confirms your speculation (don't pay for what you
don't use) but he said in his book he disagrees with the decision
(page 205 in The Standard C++ Library:
"A solution would be easy if erase() always returned the value
of the following element.... It was a design decision not to
provide this trait, because if not needed, it costs unnecessary
time. I don't agree with this decision however, because code is
getting more error prone and complicated (and may cost even more
in terms of time.)"
I'd prefer consistency, especially since they already provide this
feature for lists, so it's not unprecedented.
--
Chris (TeamB);
 

Re:Iterators the fun never stops :)

Hi!
Chris Uzdavinis (TeamB) wrote:
Quote
I'd prefer consistency, especially since they already provide this
feature for lists, so it's not unprecedented.
I agree. Even STL algorithms like for_each return things the caller
should already know.
Frank