карта, лямбда, remove_if

Итак, у меня проблема с алгоритмом std::map, lambda и stl (remove_if). На самом деле тот же код с std::list или std::vector работает хорошо.

Мой тестовый пример:

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

struct Foo
{
    Foo() : _id(0) {}
    Foo(int id) : _id(id)
    {

    }

    int _id;    
};
typedef std::map<int, Foo> FooMap;


int main()
{
    FooMap m;
    for (int i = 0; i < 10; ++i)
        m[i + 100] = Foo(i);

    int removeId = 6;
    // <<< Error here >>>
    std::remove_if(m.begin(), m.end(), [=](const FooMap::value_type & item) { return item.second._id == removeId ;} ); 

    for (auto & item : m )
        std::cout << item.first << " = " << item.second._id << "\n";    

    return 0;
}

Сообщение об ошибке :

In file included from /usr/include/c++/4.6/utility:71:0,
                 from /usr/include/c++/4.6/algorithm:61,
                 from main.cxx:1:
/usr/include/c++/4.6/bits/stl_pair.h: In member function ‘std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(std::pair<_T1, _T2>&&) [with _T1 = const int, _T2 = Foo, std::pair<_T1, _T2> = std::pair<const int, Foo>]’:
/usr/include/c++/4.6/bits/stl_algo.h:1149:13:   instantiated from ‘_FIter std::remove_if(_FIter, _FIter, _Predicate) [with _FIter = std::_Rb_tree_iterator<std::pair<const int, Foo> >, _Predicate = main()::<lambda(const value_type&)>]’
main.cxx:33:114:   instantiated from here
/usr/include/c++/4.6/bits/stl_pair.h:156:2: error: assignment of read-only member ‘std::pair<const int, Foo>::first’

Я не понимаю, что здесь не так. Итак, я с удовольствием прочитал некоторые советы / указания по этому поводу. Моя цель — использовать новый лямбда-стиль с std::map и алгоритмами, такими как remove_if.

g++ 4.6, -std=c++0x.


c++ lambda c++11 stdmap stl-algorithm
person Reddy    schedule 01.03.2012    source источник
comment
remove_if принимает пару итераторов и возвращает итератор. Как вы думаете, где он удаляет элементы из?   -  person n. 1.8e9-where's-my-share m.    schedule 01.03.2012

Ответы (2)


arrow_upward
30
arrow_downward

Проблема в том, что std::map<K,V>::value_type — это std::pair<const K, V>, также известный как .first — это const, и его нельзя назначить. Лямбды не имеют ничего общего с проблемой здесь.

std::remove_if "удаляет" элементы, перемещая элементы контейнера, чтобы все, что не соответствует предикат находится впереди, перед возвращаемым итератором. Все после этого итератора не указано. Он делает это с помощью простого присваивания, и поскольку вы не можете присвоить значение переменной const, вы получите эту ошибку.†

Имя remove может немного вводить в заблуждение, и в этом случае вам действительно нужно erase_if, но, увы, его не существует. Вам придется перебирать все элементы и удалять их вручную с помощью map.erase(iterator):

for(auto it = map.begin(), ite = map.end(); it != ite;)
{
  if(it->second._id == remove_id)
    it = map.erase(it);
  else
    ++it;
}

Это безопасно, потому что вы можете стереть отдельные узлы в дереве без того, чтобы другие итераторы стали недействительными. Обратите внимание, что я не увеличивал итератор в самом заголовке цикла for, так как это пропустит элемент в случае удаления узла.

† К настоящему моменту вы должны были заметить, что это нанесет ущерб порядку std::map, поэтому ключ равен const, поэтому вы не можете каким-либо образом повлиять на порядок после вставки элемента.

person Xeo    schedule 01.03.2012
comment
Спасибо за ответ. Итак, есть элегантный способ удалить элемент из std::map без уродливого кода: void removeFromMap(FooMap & m, int id) { for (auto it = m.begin(), end = m.end(); it != end; ++it) { if (it->second._id == id) { m.erase(it); break; } } } - person Reddy; 01.03.2012
comment
@Reddy: Нет, другого способа я не знаю. Кстати, если ваши идентификаторы не уникальны, вы сотрете только первый элемент на карте. Если они есть, то эта петля в порядке. - person Xeo; 01.03.2012

arrow_upward
3
arrow_downward

Вы можете использовать поиск и стирание для карты. Это не так удобно, как remove_if, но, возможно, это лучшее, что у вас есть.

int removeId = 6;
auto foundIter = m.find(removeId);

// if removeId is not found you will get an error when you try to erase m.end()
if(foundIter != m.end())
{
    m.erase(foundIter);
}
person YoungJohn    schedule 11.12.2013