Удаление определенных элементов в std:: map

Я хочу удалить некоторые элементы на моей std:: map.
Я написал метод erase + remove_if, который я всегда делаю с другими контейнерами последовательности.
Но он не собирался с картой. Почему?
И как я могу выполнить эту работу?

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;
}

Ответ 1

Запишите его так же, как и для map, так как remove_if не будет работать для итераторов map (он просто помещает элементы-нарушители в конец, а map итераторы этого не допускают):

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++);
}

или если вам нужны однострочные:

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++));
}

Ответ 2

Потому что std::map не "контейнер последовательности":) remove_if попытается поместить бесполезные элементы в конец карты, но это приведет к нарушению неявной структуры данных (красно-черного дерева в большинстве случаев) карты. Неявная структура данных определяет место каждого элемента на карте, и поэтому remove_if не допускается для std::map.

Вы должны стирать элементы из std::map один за другим (или задавая некоторый интервал) в цикле.

Что-то вроде этого:

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

Ответ 3

"С другими контейнерами последовательности" - ваша ошибка - map - ассоциативный контейнер! В ассоциативных контейнерах элементы определяются их ключом (в отличие от их порядка вставки в контейнерах последовательностей), и вы удаляете элементы по ключу:

m.erase(12);

Удаление по значению ключа имеет ту же сложность, что и поиск (например, O (log n) для карты, O (1) для неупорядоченной карты и т.д.). Кроме того, вы можете стереть итератор в постоянное время. Стирание итератора делает недействительным этот итератор, но не другие (опять же в отличие от контейнеров последовательностей), поэтому, если вы хотите перебирать карту, типичная идиома такова:

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

Ответ 4

Эта идиома работает только для последовательности, такой как контейнеры - записи на карте (ассоциативные) не могут быть перенаправлены (ключ не изменяется - так как вы можете ожидать, что переместите запись в какую-либо другую позицию - например, конец). Правильный способ сделать это - найти запись и удалить ее - т.е. it = map.find(); map.erase(it++)

Ответ 5

Попробуйте что-то вроде этого

#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;
}

Ответ 6

Но он не был скомпилирован с картой. Почему?

При использовании remove_if тип разыменованных итераторов должен соответствовать требованиям CopyAssignable. То есть должно быть возможно присвоить одно значение другому.

Для std::map<int, int> значение std::pair<const int, int>, которое представляет пары ключевых значений карты и не является CopyAssignable. Причиной этого const int для ключа является то, как карта работает внутри, как уже указывали другие люди.

Кстати, вы получите одинаковые ошибки компиляции для контейнера последовательности следующим образом:

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