Wie entferne ich aus einer Karte, während ich sie iteriere?

Wie entferne ich aus einer Karte, während ich sie iteriere? wie:

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

Wenn ich benutze map.erase es wird die Iteratoren ungültig machen

Das standardmäßige Löschen von assoziativen Containern:

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

Beachten Sie, dass wir wirklich ein gewöhnliches wollen for Schleife hier, da wir den Container selbst ändern. Die bereichsbasierte Schleife sollte ausschließlich Situationen vorbehalten sein, in denen wir uns nur um die Elemente kümmern. Die Syntax für die RBFL macht dies deutlich, indem nicht einmal der Container innerhalb des Schleifenkörpers exponiert wird.

Bearbeiten. Vor C++11 konnten Sie Konstantiteratoren nicht löschen. Da müsste man sagen:

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

Das Löschen eines Elements aus einem Container steht nicht im Widerspruch zur Konstanz des Elements. Analog dazu war es schon immer vollkommen legitim delete p wo p ist ein Zeiger auf eine Konstante. Beständigkeit schränkt die Lebensdauer nicht ein; const-Werte in C++ können immer noch aufhören zu existieren.

Ich persönlich bevorzuge dieses Muster, das etwas klarer und einfacher ist, auf Kosten einer zusätzlichen Variablen:

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

Vorteile dieses Ansatzes:

• der Inkrementor der for-Schleife ist als Inkrementor sinnvoll;
• die Löschoperation ist eine einfache Löschung, anstatt mit einer Inkrementlogik vermischt zu werden;
• nach der ersten Zeile des Schleifenkörpers die Bedeutung von it und next_it bleiben während der gesamten Iteration unverändert, sodass Sie problemlos zusätzliche Anweisungen hinzufügen können, die sich auf sie beziehen, ohne sich darüber den Kopf zu zerbrechen, ob sie wie beabsichtigt funktionieren (außer natürlich, dass Sie sie nicht verwenden können). it nach dem Löschen).

Unter der Annahme von C ++ 11 ist hier ein einzeiliger Schleifenkörper, wenn dies mit Ihrem Programmierstil übereinstimmt:

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

Ein paar andere kleinere Stiländerungen:

• Deklarierten Typ anzeigen (Map::const_iterator) wenn möglich/bequem, über die Verwendung auto.
• Verwenden using für Vorlagentypen, um Hilfstypen zu erstellen (Map::const_iterator) leichter zu lesen/pflegen.

Kurz gesagt: “Wie entferne ich aus einer Karte, während ich sie iteriere?”

• Mit alter Karte implizieren: Das geht nicht
• Mit neuer Karte impl: fast wie von @KerrekSB vorgeschlagen. Aber es gibt einige Syntaxprobleme in dem, was er gepostet hat.

Von der GCC-Karte impl (Anm 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

Beispiel mit altem und neuem Stil:

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

Drucke:

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.

Der C++20-Entwurf enthält die Convenience-Funktion std::erase_if.

Sie können diese Funktion also als Einzeiler verwenden.

std::map<K, V> map_obj;
//calls needs_removing for each element and erases it, if true was reuturned
std::erase_if(map_obj,needs_removing);
//if you need to pass only part of the key/value pair
std::erase_if(map_obj,[](auto& kv){return needs_removing(kv.first);});

Ziemlich traurig, oder? Normalerweise baue ich einen Container mit Iteratoren auf, anstatt sie während der Traversierung zu löschen. Durchlaufen Sie dann den Container und verwenden Sie 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)
}