Re: use remove_if in map

wangbo wrote: 
Hi£¬ Can I use remove_if in map,I write some codes like this,but it can't
compile,why:

class RemoveInvalid
{
public:
 RemoveInvalid(std::set<int> validset)
 {
  m_validset = validset;
 };
 std::set<int> m_validset;
 bool operator ()(std::pair<int,int> con)
 {
  if(m_validset.find(con.first) != m_validset.end())
   return false;
  return true;
 };
};
...
std::map<int,int> m_con_defnum;
...
m_con_defnum.erase(std::remove_if(m_con_defnum.begin(),m_con_defnum.end(),Re
moveInvalid(validcon)),m_con_defnum.end());

You cannot use mutating algorithms on std::map or std::set, essentially because the operation *i = val is illegal for iterators of those containers. In any case, remove_if is only a good algorithm for containers that aren't node based, like std::vector and std::deque. For std::list, std::list::remove_if is more efficient. If you had a set, you could use set_difference to do what you want. With std::map, you have two options. The first is to iterate over the valid set and copy the valid map elements into another map (possibly via a vector, to easily allow the use of the map's iterator range constructor). This is O(s * log m) where s is the size of the valid set, and m that of the map. Option 2 is to iterate over the map and check each element for validity. This is O(m * log(s)) (and it basically what you have been trying to do). In plain code:

for(std::map<int,int>::iterator i = m_con_defnum.begin(),
      end = m_con_defnum.end();
    i != end;)
{
  if (validset.find(i->first) == validset.end())
  {
    m_con_defnum.erase(i++);
  }
  else
  {
    ++i;
  }
}

Note the use of post-increment on i - this ensures that i is incremented before it is invalidated by the erase operation.

Tom
.

Relevant Pages

  • Riemann surface for iteration of complex map?
    ... I once had a thread here where I mentioned the idea of using a Riemann ... surface to "continuously iterate" a complex map: ... real and theta any real. ...
    (sci.math)
  • Why is not "sub" necessary? What is the difference: block and expression?
    ... I'm trying to understand the map function in perl and have been studying ... When David calls his iterate function, why does he not need to use the ... keyword "sub"? ...
    (perl.beginners)
  • Re: Collection
    ... The purpose of a Map is to hold associations; using a Map as a List is overkill. ... If, OTOH, you do need the associative lookup and only occasionally need to loop through the entrySet, then just iterate over the entrySet. ... It is unlikely that you actually need both Mapness and sortedness. ...
    (comp.lang.java.programmer)
  • Another kind of ConcurrentModificationException, how can I solve it?
    ... I will iterate a map and send out a message to ... pointing. ... completely handled the notification. ...
    (comp.lang.java.programmer)
  • Re: do u know ramanujan numbers algorithm
    ... You could also iterate only over two variables and save the values ... Before actually adding it to the map, ... keys in the map that are small enough that re-encountering them ... Any one else interested pay me $200 for the solution. ...
    (comp.lang.java.programmer)