Re: Problems removing an element from a std::set using a reverse_iterator
irotas <google@irotas.net> wrote:
The article states that option 1 is fine for all standard containers
*except* for std::string and std::vector, which often implement
iterators as built-in pointers (C++ imposes the constraint that
pointers returned from functions may not be modified).
chapter and verse please. this implies that
char *p = "abzxycd";
if(*(strchr(p,'z')+3) !='c') {/* */}
is illegal , [not safe but it is legal]
However, the
article claims that option 2 works for all standard containers, and
therefore is the preferred technique.
I do see a huge problem with your code. You are invalidating the
reverse_iterator by invalidating its 'base iterator'.
first you find the last entry . thats ok then you erase that entry
noe you increment the reverse iterator , decrementing the base
iterator so it no points to the erased element. that is you are doing
this under the hood:
std::set<unsigned int>::iterator it = my_set.end();
while (it != my_set.begin()
{
std::set<unsigned int>::iterator tmp = it; --tmp;
if(pred(*tmp))
{
erase(it);
}
--it; // Ouch it now points to erased element if it was erased.
}
You need to do something like.
template <class Cont, class Pred>
void erase_backward_if(Cont &c, Pred pred)
{
typename Cont::iterator it;
typename Cont::reverse_iterator rit;
// find the first to remove
rit = std::find_if(c.rbegin(),c.rend(), pred);
// while any to remove.
while(rit != c.rend())
{
// copy the base iterator to erase to it for safe keeping
it = --(rit.begin());
// 'advance' the reverse iterator
rit = std::find_if(++rit,c.rend(),pred());
// now erase the elment pointed to by it.
c.erase(it);
}
}
now the data is not removed from the container until the
reverse_iterator has moved to the 'next position' and beyond.
Of course this is O(N) but apparently that is not a problem.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]