remove_if-Äquivalent für std :: map

118

Ich habe versucht, eine Reihe von Elementen aus der Karte zu löschen, basierend auf einer bestimmten Bedingung. Wie mache ich das mit STL-Algorithmen?

Anfangs dachte ich an die Verwendung, remove_ifaber es ist nicht möglich, da remove_if für assoziative Container nicht funktioniert.

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

Als einfache Option dachte ich daran, die Karte zu durchlaufen und zu löschen. Aber ist das Durchlaufen der Karte und das Löschen eine sichere Option? (Da Iteratoren nach dem Löschen ungültig werden)

Ich habe folgendes Beispiel verwendet:

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;
}
aJ.
quelle
Was meinst du damit, dass remove_if nicht funktioniert?
dirkgently
Ich kann remove_if nicht verwenden, um ein Element in der Karte zu finden, oder? Es gab einen Fehler bei der Kompilierung. Vermisse ich etwas
aJ.
Nein - es funktioniert nicht wie remove_if, indem eine Sequenz neu angeordnet wird und Elemente verschoben werden, die die Bedingung gegen Ende nicht erfüllen. Daher funktioniert es auf einem T [n], aber nicht auf einer Karte <T, U>.
MSalters
2
Mit C + 11 können Sie for(auto iter=aMap.begin(); iter!=aMap.end(); ){ ....}Unordnung reduzieren. Ruhe ist wie andere sagten. Diese Frage ersparte mir gerade einige Haarspalterei ;-)
Atul Kumar

Antworten:

111

Fast.

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

Was Sie ursprünglich hatten, würde den Iterator zweimal erhöhen, wenn Sie ein Element daraus löschen würden. Sie könnten möglicherweise Elemente überspringen, die gelöscht werden mussten.

Dies ist ein gängiger Algorithmus, den ich an vielen Stellen verwendet und dokumentiert habe.

[BEARBEITEN] Sie haben Recht, dass Iteratoren nach einem Löschvorgang ungültig werden, aber nur Iteratoren, die auf das gelöschte Element verweisen, andere Iteratoren sind noch gültig. Daher iter++im erase()Anruf verwenden.

Steve Folly
quelle
4
Ich bin verwirrt; warum würden Sie für (; ...;) anstelle von while (...) verwenden? Auch wenn dies wahrscheinlich funktioniert, gibt .erase nicht einen Iterator des nächsten zurück? Es scheint also, dass das if-Blog (Some Condition) iter = aMap.erase (iter) sein sollte, um am besten kompatibel zu sein. Vielleicht fehlt mir etwas? Mir fehlt die Erfahrung, die einige von Ihnen haben.
Taxilian
86
Beachten Sie, dass in C ++ 11 alle assoziativen Container, einschließlich map, den nächsten Iterator von zurückgeben erase(iter). Es ist viel sauberer zu tun iter = erase( iter ).
Potatoswatter
10
@taxilian (Jahre zu spät) while () oder for () würden funktionieren, aber semantisch wird häufig for () zum Iterieren über einen bekannten Bereich und while () für eine unbekannte Anzahl von Schleifen verwendet. Da der Bereich in diesem Fall bekannt ist (von Anfang bis Ende ), wäre for () keine ungewöhnliche Wahl und wahrscheinlich häufiger. Aber auch hier wären beide akzeptabel.
Jamin Gray
4
@taxilian Noch wichtiger: Mit 'for' können Sie Ihre Iteratordefinition IN den Bereich der Schleife einfügen, damit sie nicht mit dem Rest Ihres Programms in Konflikt gerät.
Sanchises
1
@athos Die Frage wird passiv formuliert: "Es wird empfohlen." Es gibt keine universelle Empfehlung. Ich denke, mein letzter Kommentar ist der einfachste Weg. Es handelt sich um zwei Kopien der Iteratorvariablen, was ein wenig an Effizienz verliert, wie hier jemand betont hat. Es ist Ihr Anruf, was für Sie angemessen ist.
Potatoswatter
74

erase_if für std :: map (und andere Container)

Ich benutze die folgende Vorlage für genau diese 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;
    }
  }
}

Dies gibt nichts zurück, entfernt jedoch die Elemente aus der std :: map.

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 (ermöglicht die Übergabe eines Testwerts):

// '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
});
Eisenretter
quelle
3
@CodeAngry Danke - es kam mir immer komisch vor, dass es das noch nicht gab std. Ich verstehe, warum es kein Mitglied von ist std::map, aber ich denke, so etwas sollte in der Standardbibliothek sein.
Iron Savior
2
Wird in C ++ 20 fürstd::map und andere hinzugefügt .
Roi Danton
3

Ich habe diese Dokumentation von der ausgezeichneten SGI STL-Referenz erhalten :

Map hat die wichtige Eigenschaft, dass das Einfügen eines neuen Elements in eine Map keine Iteratoren ungültig macht, die auf vorhandene Elemente verweisen. Das Löschen eines Elements aus einer Karte macht auch keine Iteratoren ungültig, außer natürlich für Iteratoren, die tatsächlich auf das zu löschende Element verweisen.

Der Iterator, der auf das zu löschende Element zeigt, wird natürlich ungültig. Mach so etwas:

if (some condition)
{
  iterator here=iter++;
  aMap.erase(here)
}
1800 INFORMATIONEN
quelle
3
Dies unterscheidet sich nicht vom ursprünglichen Code. iter ++ erhöht den Iterator und gibt dann einen Iterator zurück, der vor dem Inkrement auf das Element zeigt.
Steve Folly
Aber iter wird nicht ungültig, da wir dann an der Position von hier löschen
1800 INFORMATION
@ 1800INFORMATION: Die Eingabe eines Funktionsaufrufs ist ein Sequenzpunkt. Der inkrementelle Nebeneffekt wird ausgewertet, bevor er eraseaufgerufen wird. Sie sind also in der Tat gleichwertig. Trotzdem würde ich Ihre Version dem Original vorziehen.
Peterchen
Es funktioniert für Arrays oder Vektoren, führt jedoch zu unerwarteten Ergebnissen in der STL-Zuordnung.
hunter_tech
2

Der ursprüngliche Code hat nur ein Problem:

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

Hier wird das itereinmal in der for-Schleife und ein anderes Mal beim Löschen inkrementiert, was wahrscheinlich in einer Endlosschleife enden wird.

Partha Biswas
quelle
2

Hier ist eine elegante Lösung.

for (auto it = map.begin(); it != map.end();)
{   
    (SomeCondition) ? map.erase(it++) : (++it);
}
Mandrake-Wurzel
quelle
1

Aus den Grundtönen von:

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

Ein paarassoziativer Container kann keine veränderlichen Iteratoren bereitstellen (wie in den Anforderungen für triviale Iteratoren definiert), da der Werttyp eines veränderlichen Iterators zuweisbar sein muss und das Paar nicht zuweisbar ist. Ein paarassoziativer Container kann jedoch Iteratoren bereitstellen, die nicht vollständig konstant sind: Iteratoren, sodass der Ausdruck (* i) .second = d gültig ist.

piotr
quelle
1

Zuerst

Map hat die wichtige Eigenschaft, dass das Einfügen eines neuen Elements in eine Map keine Iteratoren ungültig macht, die auf vorhandene Elemente verweisen. Das Löschen eines Elements aus einer Karte macht auch keine Iteratoren ungültig, außer natürlich für Iteratoren, die tatsächlich auf das zu löschende Element verweisen.

Zweitens ist der folgende Code gut

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

Beim Aufruf einer Funktion werden die Parameter vor dem Aufruf dieser Funktion ausgewertet.

Wenn also iter ++ vor dem zu löschenden Aufruf ausgewertet wird, gibt der ++ - Operator des Iterators das aktuelle Element zurück und zeigt nach dem Aufruf auf das nächste Element.

Vincent
quelle
1

IMHO gibt es kein remove_if()Äquivalent.
Sie können eine Karte nicht neu anordnen.
Sie remove_if()können also Ihre Interessenpaare nicht an das Ende setzen, an dem Sie anrufen können erase().

user109134
quelle
Das ist wirklich unglücklich.
Allyourcode
1

Basierend auf der Antwort von Iron Saviour Für diejenigen, die eine größere Reichweite im Sinne von Standard-Funktions-Iteratoren bieten möchten.

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 eine Möglichkeit gibt, die ContainerTGegenstände zu verlieren und diese vom Iterator zu erhalten.

Greg Domjan
quelle
1
"Bezeichner, die mit einem Unterstrich gefolgt von einem Großbuchstaben beginnen, sind für die gesamte Verwendung durch die Implementierung reserviert."
YSC
0

Steve Follys Antwort ich umso effizienter.

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

Die Lösung remove_copy_ifkopiert die gewünschten Werte in einen neuen Container und tauscht dann den Inhalt des ursprünglichen Containers gegen den des neuen aus:

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);
aJ.
quelle
2
Das scheint ineffizient.
Allyourcode
0

Wenn Sie alle Elemente mit einem Schlüssel größer als 2 löschen möchten, ist der beste Weg

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

Funktioniert jedoch nur für Bereiche, nicht für Prädikate.

Tadeusz Kopec
quelle
0

Ich benutze so

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