Как удалить с карты во время итерации?

Question

Как удалить с карты при ее повторении? как:

std::map<K, V> map;
for(auto i : map)
    if(needs_removing(i))
        // remove it from the map

Если я использую map.erase, это сделает недействительными итераторы

Answer 1

Стандартная итерация стирания ассоциативного контейнера:

for (auto it = m.cbegin(); it != m.cend() /* not hoisted */; /* no increment */)
{
  if (must_delete)
  {
    m.erase(it++);    // or "it = m.erase(it)" since C++11
  }
  else
  {
    ++it;
  }
}

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

Edit. До C ++ 11 вы не могли стереть const-итераторы.Там вы должны сказать:

for (std::map<K,V>::iterator it = m.begin(); it != m.end(); ) { /* ... */ }

Стирание элемента из контейнера не противоречит константности элемента.По аналогии, это всегда было совершенно законно для delete p, где p - указатель на константу.Константность не ограничивает продолжительность жизни;константные значения в C ++ могут прекратить существование.

Answer 2

Я лично предпочитаю эту схему, которая немного яснее и проще за счет дополнительной переменной:

for (auto it = m.cbegin(), next_it = it; it != m.cend(); it = next_it)
{
  ++next_it;
  if (must_delete)
  {
    m.erase(it);
  }
}

Преимущества этого подхода:

• инкрементатор цикла for имеет смысл как инкрементор;
• операция стирания является простым стиранием, а не смешивается с логикой приращения;
• после первой строки тела цикла значения it и next_it остаются неизменными на протяжении всей итерации, что позволяет вам легко добавлять дополнительные операторы, ссылающиеся на них, без разбора на вопрос, будут ли они работать по назначению (кроме Конечно, вы не можете использовать it после удаления).

Answer 3

Короче говоря "Как удалить с карты во время итерации?"

• При использовании старой карты: вы не можете
• При использовании новой карты: почти как @KerrekSB предложил.Но есть некоторые синтаксические проблемы в том, что он написал.

Из карты GCC Impl (примечание GXX_EXPERIMENTAL_CXX0X ):

#ifdef __GXX_EXPERIMENTAL_CXX0X__
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // DR 130. Associative erase should return an iterator.
      /**
       *  @brief Erases an element from a %map.
       *  @param  position  An iterator pointing to the element to be erased.
       *  @return An iterator pointing to the element immediately following
       *          @a position prior to the element being erased. If no such 
       *          element exists, end() is returned.
       *
       *  This function erases an element, pointed to by the given
       *  iterator, from a %map.  Note that this function only erases
       *  the element, and that if the element is itself a pointer,
       *  the pointed-to memory is not touched in any way.  Managing
       *  the pointer is the user's responsibility.
       */
      iterator
      erase(iterator __position)
      { return _M_t.erase(__position); }
#else
      /**
       *  @brief Erases an element from a %map.
       *  @param  position  An iterator pointing to the element to be erased.
       *
       *  This function erases an element, pointed to by the given
       *  iterator, from a %map.  Note that this function only erases
       *  the element, and that if the element is itself a pointer,
       *  the pointed-to memory is not touched in any way.  Managing
       *  the pointer is the user's responsibility.
       */
      void
      erase(iterator __position)
      { _M_t.erase(__position); }
#endif

Пример со старым и новым стилем:

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

using namespace std;
typedef map<int, int> t_myMap;
typedef vector<t_myMap::key_type>  t_myVec;

int main() {

    cout << "main() ENTRY" << endl;

    t_myMap mi;
    mi.insert(t_myMap::value_type(1,1));
    mi.insert(t_myMap::value_type(2,1));
    mi.insert(t_myMap::value_type(3,1));
    mi.insert(t_myMap::value_type(4,1));
    mi.insert(t_myMap::value_type(5,1));
    mi.insert(t_myMap::value_type(6,1));

    cout << "Init" << endl;
    for(t_myMap::const_iterator i = mi.begin(); i != mi.end(); i++)
        cout << '\t' << i->first << '-' << i->second << endl;

    t_myVec markedForDeath;

    for (t_myMap::const_iterator it = mi.begin(); it != mi.end() ; it++)
        if (it->first > 2 && it->first < 5)
            markedForDeath.push_back(it->first);

    for(size_t i = 0; i < markedForDeath.size(); i++)
        // old erase, returns void...
        mi.erase(markedForDeath[i]);

    cout << "after old style erase of 3 & 4.." << endl;
    for(t_myMap::const_iterator i = mi.begin(); i != mi.end(); i++)
        cout << '\t' << i->first << '-' << i->second << endl;

    for (auto it = mi.begin(); it != mi.end(); ) {
        if (it->first == 5)
            // new erase() that returns iter..
            it = mi.erase(it);
        else
            ++it;
    }

    cout << "after new style erase of 5" << endl;
    // new cend/cbegin and lambda..
    for_each(mi.cbegin(), mi.cend(), [](t_myMap::const_reference it){cout << '\t' << it.first << '-' << it.second << endl;});

    return 0;
}

отпечатки:

main() ENTRY
Init
        1-1
        2-1
        3-1
        4-1
        5-1
        6-1
after old style erase of 3 & 4..
        1-1
        2-1
        5-1
        6-1
after new style erase of 5
        1-1
        2-1
        6-1

Process returned 0 (0x0)   execution time : 0.021 s
Press any key to continue.

Answer 4

Довольно грустно, а? Обычно я делаю это для создания контейнера итераторов вместо удаления во время обхода. Затем переберите контейнер и используйте map.erase ()

std::map<K,V> map;
std::list< std::map<K,V>::iterator > iteratorList;

for(auto i : map ){
    if ( needs_removing(i)){
        iteratorList.push_back(i);
    }
}
for(auto i : iteratorList){
    map.erase(*i)
}

Answer 5

Предполагая C ++ 11, вот тело цикла с одной строкой, если это соответствует вашему стилю программирования:

using Map = std::map<K,V>;
Map map;

// Erase members that satisfy needs_removing(itr)
for (Map::const_iterator itr = map.cbegin() ; itr != map.cend() ; )
  itr = needs_removing(itr) ? map.erase(itr) : std::next(itr);

Пара других незначительных изменений стиля:

• Показывать объявленный тип (Map::const_iterator), когда это возможно / удобно, с использованием auto.
• Используйте using для типов шаблонов, чтобы облегчить чтение / обслуживание вспомогательных типов (Map::const_iterator).