remove_if Äquivalent für std :: map

Question

Ich habe versucht, eine Reihe von Elementen aus der Karte auf bestimmte Bedingung basiert zu löschen. Wie mache ich es STL-Algorithmen?

Am Anfang dachte ich an remove_if verwenden, aber es ist nicht möglich, da remove_if nicht für assoziative Container funktioniert.

Gibt es einen „remove_if“ äquivalenten Algorithmus, der für die Karte funktioniert?

Als eine einfache Möglichkeit, dachte ich an durch die Karte Looping und löschen. Aber wird Looping durch die Karte und eine sichere Option Löschen? (Wie Iteratoren erhalten ungültig nach dem Löschen)

Ich habe folgendes Beispiel:

bool predicate(const std::pair<int,std::string>& x)
{
    return x.first > 2;
}

int main(void) 
{

    std::map<int, std::string> aMap;

    aMap[2] = "two";
    aMap[3] = "three";
    aMap[4] = "four";
    aMap[5] = "five";
    aMap[6] = "six";

//      does not work, an error
//  std::remove_if(aMap.begin(), aMap.end(), predicate);

    std::map<int, std::string>::iterator iter = aMap.begin();
    std::map<int, std::string>::iterator endIter = aMap.end();

    for(; iter != endIter; ++iter)
    {
            if(Some Condition)
            {
                            // is it safe ?
                aMap.erase(iter++);
            }
    }

    return 0;
}

Answer 1

Fast.

for(; iter != endIter; ) {
            if (Some Condition) {
                    aMap.erase(iter++);
            } else {
                    ++iter;
            }
}

Was hatte man ursprünglich den Iterator erhöhen würde zweimal , wenn Sie ein Element aus es tun löschen; Sie könnten möglicherweise über Elemente überspringen, die gelöscht werden müssen.

Dies ist ein gemeinsamer Algorithmus ich gesehen habe verwendet und dokumentierte in vielen Orten.

[EDIT] Sie sind richtig, dass Iteratoren nach einem Lösch für ungültig erklärt werden, sondern nur Iteratoren das Element verweisen, die gelöscht wird, können andere Iteratoren sind nach wie vor gültig. Daher iter ++ im Lösch () -Aufruf verwendet wird.

Answer 2

erase_if für std :: map (und andere Behälter)

Ich verwende die folgende Vorlage für diese sehr Sache.

namespace stuff {
  template< typename ContainerT, typename PredicateT >
  void erase_if( ContainerT& items, const PredicateT& predicate ) {
    for( auto it = items.begin(); it != items.end(); ) {
      if( predicate(*it) ) it = items.erase(it);
      else ++it;
    }
  }
}

Das wird nichts zurück, aber es wird die Elemente aus dem std :: map entfernen.

Anwendungsbeispiel:

// 'container' could be a std::map
// 'item_type' is what you might store in your container
using stuff::erase_if;
erase_if(container, []( item_type& item ) {
  return /* insert appropriate test */;
});

Zweites Beispiel (Damit können Sie in einem Test Wert zu übergeben):

// 'test_value' is value that you might inject into your predicate.
// 'property' is just used to provide a stand-in test
using stuff::erase_if;
int test_value = 4;  // or use whatever appropriate type and value
erase_if(container, [&test_value]( item_type& item ) {
  return item.property < test_value;  // or whatever appropriate test
});

Answer 3

Ich habe diese Dokumentation aus der ausgezeichneten SGI STL Referenz :

  

Karte hat die wichtige Eigenschaft, dass   ein neues Element in eine Karte einfügen   nicht Iteratoren entkräften, dass   weisen auf vorhandene Elemente. Löschen eines   Element aus einer Karte funktioniert auch nicht   entkräften alle Iteratoren, außer,   Natürlich, für Iteratoren, die tatsächlich   Punkt zu dem Element, das zu sein, ist   gelöscht.

Also, der Iterator Sie haben, die auf das Element zeigt auf gelöscht wird natürlich für ungültig erklärt werden. Tun Sie etwas wie folgt aus:

if (some condition)
{
  iterator here=iter++;
  aMap.erase(here)
}

Answer 4

Der ursprüngliche Code hat nur ein Problem:

for(; iter != endIter; ++iter)
{
    if(Some Condition)
    {
        // is it safe ?
        aMap.erase(iter++);
    }
}

Hier wird der iter erhöht einmal in dem for-Schleife und ein anderes Mal in Lösch, die wahrscheinlich in irgendeiner Endlosschleife enden wird.

Answer 5

Nun std::experimental::erase_if ist in Header <experimental/map> zur Verfügung.

Siehe auch: http://en.cppreference.com/w/cpp / experimental / map / erase_if

Answer 6

Von den unteren Noten von:

http://www.sgi.com/tech/stl/PairAssociativeContainer.html

ein Paar Assoziative Container können wandelbar Iteratoren nicht bieten (wie in den Trivial Iterator Anforderungen definiert ist), weil der Wert Typ eines wandelbaren Iterator zuordenbar sein muß, und das Paar ist nicht übertragbar. Allerdings kann ein Paar Assoziative Container Iteratoren bieten, die nicht völlig konstant: Iteratoren, so dass der Ausdruck (* i) .second = d gilt.

Answer 7

Erste

  

Karte hat die wichtige Eigenschaft, dass ein neues Element in eine Karte einfügen Iteratoren nicht ungültig machen, die auf bestehende Elemente verweisen. Löscht ein Element aus einer Karte auch ungültig macht keine Iteratoren, außer natürlich, für Iteratoren, die tatsächlich auf das Element verweisen, die gelöscht wird.

Zweitens ist der folgende Code ist gut

for(; iter != endIter; )
{
    if(Some Condition)
    {
        aMap.erase(iter++);
    }
    else
    {
        ++iter;
    }
}

Wenn Sie eine Funktion aufrufen, werden die Parameter vor dem Aufruf ausgewertet dieser Funktion.

Also, wenn iter ++ ausgewertet wird, bevor der Anruf zu löschen, der ++ Operator des Iterators wird das aktuelle Element zurückkehren und zum nächsten Punkt nach dem Aufruf verweisen.

Answer 8

IMHO gibt es keine remove_if() gleichwertig.
Sie können eine Karte neu anordnen.
So remove_if() kann nicht Ihre Paare von Interesse am Ende setzen, auf dem Sie erase() aufrufen können.

Answer 9

Basierend auf Iron Savior Antwort Für diejenigen, die eine Reihe mehr entlang der Linien von std Funktions nehmen Iteratoren zur Verfügung stellen wollen .

template< typename ContainerT, class _FwdIt, class _Pr >
void erase_if(ContainerT& items, _FwdIt it, _FwdIt _Last, _Pr _Pred) {
    for (; it != _Last; ) {
        if (_Pred(*it)) it = items.erase(it);
        else ++it;
    }
}

Neugierig, ob es irgendeine Art und Weise ist es, den ContainerT Artikel zu verlieren und dass erhalten von dem Iterator.

Answer 10

Steve Folly Antwort ich die effizienter fühlen.

Hier ist eine weitere leicht, aber weniger effiziente Lösung :

Die Lösung remove_copy_if verwendet die Werte, die wir wollen in einen neuen Container zu kopieren, dann tauscht den Inhalt des Originalbehälters mit denen der neuen:

std::map<int, std::string> aMap;

...
//Temporary map to hold the unremoved elements
std::map<int, std::string> aTempMap;

//copy unremoved values from aMap to aTempMap
std::remove_copy_if(aMap.begin(), aMap.end(), 
                    inserter(aTempMap, aTempMap.end()),
                    predicate);

//Swap the contents of aMap and aTempMap
aMap.swap(aTempMap);

Answer 11

Wenn Sie alle Elemente mit Schlüsseln größer als 2 löschen wollen, dann ist der beste Weg ist,

map.erase(map.upper_bound(2), map.end());

Funktioniert nur für Bereiche allerdings nicht für jedes Prädikat.

Answer 12

Ich verwende wie diese

 std::map<int, std::string> users;    
 for(auto it = users.begin(); it <= users.end()) {
    if(<condition>){
      it = users.erase(it);
    } else {
    ++it;
    }
 }