Erase specific elements in std::map

Question

I want to erase some elements in my std::map.
I wrote erase + remove_if technique which I always do with other sequence containers.
But it wasn't compile with map. Why?
And How can I do this job?

std::map<int, int> m;

bool foo(const std::pair<int, int>& p)
{
    return p.second > 15;
}

int _tmain(int argc, _TCHAR* argv[])
{
    m.insert(make_pair(0, 0));
    m.insert(make_pair(1, 10));
    m.insert(make_pair(2, 20));
    m.insert(make_pair(3, 30));

    m.erase(
        remove_if(m.begin(), m.end(), foo),
        m.end()); // compile error

    return 0;
}

Answer 1

Write it like this for map, since remove_if won't work for map iterators (it merely puts offending elements at the end, and map iterators don't allow for this):

template <typename Map, typename F>
void map_erase_if(Map& m, F pred)
{
    typename Map::iterator i = m.begin();
    while ((i = std::find_if(i, m.end(), pred)) != m.end())
        m.erase(i++);
}

or if you like one-liners:

template <typename Map, typename F>
void map_erase_if(Map& m, F pred)
{
    for (typename Map::iterator i = m.begin();
         (i = std::find_if(i, m.end(), pred)) != m.end();
         m.erase(i++));
}

Answer 2

"With other sequence containers" is your error - map is an associative container! In associative containers, elements are defined by their key (as opposed to their insertion order in sequence containers), and you erase elements by key:

m.erase(12);

Erasing by key value has the same complexity as lookup (e.g. O(log n) for map, O(1) for unordered map, etc.). Alternatively, you can erase by iterator in constant time. Erasing an iterator invalidates that iterator, but no others (again unlike in sequence containers), so if you want to iterate over a map, the typical idiom is this:

for (auto it = m.cbegin(); it != m.cend(); ) // no "++"!
{
  if (it->second > 15)  // your own condition goes here
  {
    m.erase(it++);
  }
  else
  {
    ++it;
  }
}

Answer 3

Because std::map is not "sequence container" :) remove_if will try to put useless elements to the end of the map, but this will cause of violating of implicit data-structure (red-black tree in most cases) of the map. The implicit data-structure defines place of each element in the map, and that is why remove_if is not allowed for std::map.

You should erase elements from std::map one after another (or giving some interval) in loop.

Somethin like this:

it = m.begin();
while ((it = std::find_if(it, m.end(), pred)) != m.end())
    m.erase(it++);

Answer 4

This idiom only works for sequence like containers - entries in a map (associative) cannot be re-ordered (the key doesn't change - so how you can you possibly expect to move an entry to some other position - e.g. end). The correct way to do this is to find the entry and remove it - i.e. it = map.find(); map.erase(it++)

Answer 5

But it wasn't compile with map. Why?

When using remove_if, the type of dereferenced iterators must meet the requirements of CopyAssignable. That is it should be possible to assign one value to another.

For std::map<int, int> the value is std::pair<const int, int> which represents key value pairs of map and which is not CopyAssignable. The reason for this const int for key is how map works internally as other people already pointed.

By the way you will get the same compilation errors for sequence container like this:

std::vector<std::pair<const int, int>>;

Answer 6

Try something like this

#include <iostream>
#include <map>
#include <algorithm>

class foo 
{
public:
    enum CompType { GREATER=1, LESS=-1 };
    foo(int nVal=15, enum CompType ctype=GREATER)
    : m_nVal(nVal)
    , m_bGreater(ctype==GREATER)
    {
    }
    bool operator()(std::pair<int, int> p) 
    {
        if (m_bGreater)
            return p.second > m_nVal;
        else
            return p.second < m_nVal;
    }
private:
    int  m_nVal;
    bool m_bGreater;
};

void MapRemove(std::map<int, int> &m, foo &pred)
{
    auto itr = std::find_if(m.begin(), m.end(), pred);
    while (itr != m.end())
        itr = std::find_if(m.erase(itr), m.end(), pred);
}

int main(int argc, char *argv[])
{
    std::map<int, int> m;

    m.insert(std::make_pair(0, 0));
    m.insert(std::make_pair(1, 10));
    m.insert(std::make_pair(2, 20));
    m.insert(std::make_pair(3, 30));

    MapRemove(m, foo());

    for (auto itr=m.begin(); itr!=m.end(); ++itr)
        std::cout << "(" << itr->first << ", " 
                  << itr->second << ")" << '\n';

    return 0;
}