remove_if на карте, пытающейся передать const как неконстантный - почему?

Вот фрагмент кода, который должен отфильтровывать элементы карты, которые удовлетворяют предикату, в новую карту (MCVE-fied):

#include <algorithm>
#include <unordered_map>
#include <iostream>

using namespace std;

int main() {
    unordered_map<string, int> m = { { "hello", 1 }, { "world", 2 } };
    auto p = [](const decltype(m)::value_type& e) { return e.second == 2; };
    const auto& m2(m);
    auto m3(m2);
    auto it = remove_if(m3.begin(), m3.end(), p);
    m3.erase(it, m3.end());
    cout << "m3.size() = " << m3.size() << endl;
    return 0;
}

Сбой компиляции в строке remove_if(), и я получаю:

In file included from /usr/include/c++/4.9/utility:70:0,
                 from /usr/include/c++/4.9/algorithm:60,
                 from /tmp/b.cpp:1:
/usr/include/c++/4.9/bits/stl_pair.h: In instantiation of ‘std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(std::pair<_T1, _T2>&&) [with _T1 = const std::basic_string<char>; _T2 = int]’:
/usr/include/c++/4.9/bits/stl_algo.h:868:23:   required from ‘_ForwardIterator std::__remove_if(_ForwardIterator, _ForwardIterator, _Predicate) [with _ForwardIterator = std::__detail::_Node_iterator<std::pair<const std::basic_string<char>, int>, false, true>; _Predicate = __gnu_cxx::__ops::_Iter_pred<main()::<lambda(const value_type&)> >]’
/usr/include/c++/4.9/bits/stl_algo.h:937:47:   required from ‘_FIter std::remove_if(_FIter, _FIter, _Predicate) [with _FIter = std::__detail::_Node_iterator<std::pair<const std::basic_string<char>, int>, false, true>; _Predicate = main()::<lambda(const value_type&)>]’
/tmp/b.cpp:12:48:   required from here
/usr/include/c++/4.9/bits/stl_pair.h:170:8: error: passing ‘const std::basic_string<char>’ as ‘this’ argument of ‘std::basic_string<_CharT, _Traits, _Alloc>& std::basic_string<_CharT, _Traits, _Alloc>::operator=(const std::basic_string<_CharT, _Traits, _Alloc>&) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]’ discards qualifiers [-fpermissive]
  first = std::forward<first_type>(__p.first);
        ^

Почему это происходит? remove_if не нужно использовать неконстантные ключи карты (в данном случае строки) - если я не ошибаюсь. Возможно, autoПредположим, как-то я хочу неконстантных итераторов? Если это так, что я делаю, кроме того, чтобы описать тип (я хочу избежать этого, так как этот код должен быть шаблонным).

Источник

3 ответа

Решение

Ваш пример терпит неудачу даже без всех этих промежуточных переменных.

unordered_map<string, int> m = { { "hello", 1 }, { "world", 2 } };
auto p = [](const decltype(m)::value_type& e) { return e.second == 2; };  
auto it = remove_if(m.begin(), m.end(), p);

Приведенный выше код завершится с такими же ошибками. Вы не можете использовать remove_if с ассоциативными контейнерами, потому что алгоритм работает, перемещая элементы, которые удовлетворяют вашему предикату, в конец контейнера. Но как бы вы изменить порядок unordered_map?

Написать цикл для стирания элементов

for(auto it = m.begin(); it != m.end();)
{
  if(p(*it)) it = m.erase(it);
  else ++it;
}

Или вы можете упаковать это в алгоритм

template<typename Map, typename Predicate>
void map_erase_if(Map& m, Predicate const& p)
{
    for(auto it = m.begin(); it != m.end();)
    {
      if(p(*it)) it = m.erase(it);
      else ++it;
    }
}

Если у вас есть стандартная реализация библиотеки, которая реализует базовые расширения библиотеки стирания контейнера, то у вас есть алгоритм, аналогичный приведенному выше в std::experimental Пространство имен.

Источник

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

Для ассоциативных контейнеров вам понадобится обычный цикл:

for (auto it = m.begin(); it != m.end(); )
{
    if (it->second == 2) { m.erase(it++); }
    else                 { ++it;          }
}

Если вы удаляете из списка, используйте remove вместо этого функция-член, которая принимает предикат.

Источник

Из контекста:

Удаление выполняется путем смещения (с помощью назначения перемещения) элементов в диапазоне таким образом, что элементы, которые не должны быть удалены, появляются в начале диапазона.

Вы не можете переупорядочить элементы в ассоциативном контейнере, так как unordered_map это не имеет смысла, потому что перемещение элементов в конец ничего не значит, они все равно проверяются ключами.

Источник
Другие вопросы по тегам