remove_if odpowiednik dla std :: map

118

Próbowałem usunąć szereg elementów z mapy w oparciu o określone warunki. Jak to zrobić za pomocą algorytmów STL?

Początkowo myślałem o użyciu, remove_ifale nie jest to możliwe, ponieważ remove_if nie działa dla kontenera asocjacyjnego.

Czy istnieje równoważny algorytm „remove_if”, który działa na mapie?

Jako prostą opcję pomyślałem o przejściu mapy i wymazaniu. Ale czy zapętlanie mapy i kasowanie bezpiecznej opcji? (Ponieważ iteratory stają się nieważne po wymazaniu)

Posłużyłem się następującym przykładem:

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.
źródło
Co masz na myśli, mówiąc, że remove_if nie działa?
dirkgently
Nie mogę użyć remove_if, aby znaleźć element na mapie, prawda? Wystąpił błąd czasu kompilacji. Czy coś mi brakuje?
aJ.
Nie - to nie działa, ponieważ remove_if działa poprzez zmianę kolejności sekwencji, przesuwanie elementów, które nie spełniają warunku, pod koniec. Dlatego działa na T [n], ale nie na mapie <T, U>.
MSalters
2
Dzięki C + 11 możesz użyć, for(auto iter=aMap.begin(); iter!=aMap.end(); ){ ....}aby zmniejszyć bałagan. Reszta jest taka, jak mówili inni. To pytanie uratowało mi trochę rozdwajania włosów ;-)
Atul Kumar

Odpowiedzi:

111

Prawie.

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

To, co miałeś pierwotnie, zwiększyłoby iterator dwukrotnie , gdybyś wymazał z niego element; możesz potencjalnie pominąć elementy, które należało usunąć.

Jest to powszechny algorytm, z którego korzystałem i udokumentowałem w wielu miejscach.

[EDYCJA] Masz rację, że iteratory są unieważniane po wymazaniu, ale tylko iteratory odwołujące się do elementu, który jest usuwany, inne iteratory są nadal ważne. Stąd użycie iter++w erase()rozmowie.

Steve Folly
źródło
4
Jestem zmieszany; dlaczego miałbyś używać for (; ...;) zamiast while (...)? Ponadto, chociaż prawdopodobnie to działa, czy .erase nie zwraca iteratora następnego? Wygląda więc na to, że blog if (Some Condition) powinien mieć postać iter = aMap.erase (iter), aby był najbardziej zgodny. Może czegoś mi brakuje? Brakuje mi doświadczenia, które niektórzy z was mają.
taksówkarz
86
Uwaga, w C ++ 11 wszystkie asocjacyjne kontenery, w tym map, zwracają następny iterator z erase(iter). Jest to o wiele czystsze iter = erase( iter ).
Potatoswatter,
10
@taxilian (lat późno) while () lub for () działałoby, ale semantycznie ludzie często używają for () do iteracji w znanym zakresie, a while () dla nieznanej liczby pętli. Ponieważ zakres jest w tym przypadku znany (od początku do końcaIter ), opcja for () nie byłaby niezwykłym wyborem i prawdopodobnie byłaby bardziej powszechna. Ale znowu oba byłyby do zaakceptowania.
Jamin Gray
4
@taxilian Co ważniejsze: dzięki „for” możesz mieć swoją definicję iteratora WEWNĄTRZ zakresu pętli, aby nie zadziałać z resztą programu.
Sanchises,
1
@athos Pytanie jest sformułowane biernie, „zalecane”. Nie ma uniwersalnej rekomendacji. Myślę, że moja ostatnia uwaga jest najprostsza. Obejmuje dwie kopie zmiennej iteratora, która traci trochę na wydajności, jak ktoś tutaj wskazał. To twój wybór, co jest dla ciebie odpowiednie.
Potatoswatter
75

erase_if dla std :: map (i innych kontenerów)

Używam do tego następującego szablonu.

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

To nic nie zwróci, ale usunie elementy ze std :: map.

Przykład użycia:

// '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 */;
});

Drugi przykład (pozwala przekazać wartość testową):

// '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
});
Żelazny Zbawiciel
źródło
3
@CodeAngry Thanks - zawsze wydawało mi się dziwne, że tego jeszcze nie było w std. Rozumiem, dlaczego nie jest członkiem std::map, ale myślę, że coś takiego powinno znajdować się w standardowej bibliotece.
Iron Saviour
3
Zostanie dodany w C ++ 20 dlastd::map i innych.
Roi Danton
3

Mam tę dokumentację z doskonałej referencji SGI STL :

Mapa ma ważną właściwość polegającą na tym, że wstawienie nowego elementu do mapy nie unieważnia iteratorów wskazujących na istniejące elementy. Wymazanie elementu z mapy również nie unieważnia żadnych iteratorów, z wyjątkiem, oczywiście, iteratorów, które faktycznie wskazują usuwany element.

Tak więc iterator, który masz, który wskazuje na element do usunięcia, zostanie oczywiście unieważniony. Zrób coś takiego:

if (some condition)
{
  iterator here=iter++;
  aMap.erase(here)
}
1800 INFORMACJE
źródło
3
Nie różni się to od oryginalnego kodu. iter ++ zwiększa iterator, a następnie zwraca iterator wskazujący na element przed przyrostem.
Steve Folly
Ale iter nie zostanie unieważniony, ponieważ wtedy usuniemy w tym miejscu
1800 INFORMACJA
@ 1800INFORMATION: wprowadzenie wywołania funkcji jest punktem sekwencji, efekt uboczny przyrostu jest oceniany przed erasewywołaniem. Więc rzeczywiście są równoważne. Mimo to zdecydowanie wolałbym twoją wersję od oryginału.
peterchen
Działa dla tablicy lub wektora, ale spowoduje nieoczekiwany wynik w mapie stl.
hunter_tech
2

Oryginalny kod ma tylko jeden problem:

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

Tutaj wartość iterjest zwiększana raz w pętli for i raz w kasowaniu, co prawdopodobnie zakończy się w jakiejś nieskończonej pętli.

partha biswas
źródło
2

Oto eleganckie rozwiązanie.

for (auto it = map.begin(); it != map.end();)
{   
    (SomeCondition) ? map.erase(it++) : (++it);
}
Korzeń mandragory
źródło
1

Z dolnych nut:

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

Kontener asocjacyjny pary nie może zapewnić mutowalnych iteratorów (zgodnie z definicją w wymaganiach Trivial Iterator), ponieważ typ wartości zmiennego iteratora musi być Assignable, a para nie jest Assignable. Jednak kontener asocjacyjny pary może zapewnić iteratory, które nie są całkowicie stałe: iteratory takie, że wyrażenie (* i). Sekunda = d jest prawidłowe.

piotr
źródło
1

Pierwszy

Mapa ma ważną właściwość polegającą na tym, że wstawienie nowego elementu do mapy nie unieważnia iteratorów wskazujących na istniejące elementy. Wymazanie elementu z mapy również nie unieważnia żadnych iteratorów, z wyjątkiem, oczywiście, iteratorów, które faktycznie wskazują usuwany element.

Po drugie, poniższy kod jest dobry

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

Podczas wywoływania funkcji parametry są oceniane przed wywołaniem tej funkcji.

Więc kiedy iter ++ jest oceniane przed wywołaniem wymazywania, operator ++ iteratora zwróci bieżący element i wskaże następny element po wywołaniu.

Vincent
źródło
1

IMHO nie ma remove_if()odpowiednika.
Nie możesz zmienić kolejności mapy.
Nie remove_if()możesz więc umieścić swoich interesujących par na końcu, na które możesz sprawdzić erase().

user109134
źródło
To naprawdę niefortunne.
allyourcode
1

Na podstawie odpowiedzi Iron Saviour Dla tych, którzy chcieliby zapewnić zakres bardziej podobny do standardowych iteratorów funkcjonalnych.

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

Ciekawe, czy istnieje sposób na zgubienie ContainerTprzedmiotów i uzyskanie tego z iteratora.

Greg Domjan
źródło
1
„Identyfikatory zaczynające się od podkreślenia, po którym następuje duża litera, są zarezerwowane do użytku przez implementację”.
YSC
0

Odpowiedź Steve Folly wydaje mi się bardziej efektywna.

Oto kolejne łatwe, ale mniej wydajne rozwiązanie :

Rozwiązanie wykorzystuje remove_copy_ifdo skopiowania żądanych wartości do nowego kontenera, a następnie zamienia zawartość oryginalnego kontenera na zawartość nowego:

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.
źródło
2
Wydaje się to nieefektywne.
allyourcode
0

Jeśli chcesz usunąć wszystkie elementy z kluczem większym niż 2, najlepszym sposobem jest

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

Działa jednak tylko dla zakresów, a nie dla żadnego predykatu.

Tadeusz Kopeć
źródło
0

Używam w ten sposób

 std::map<int, std::string> users;    
 for(auto it = users.begin(); it <= users.end()) {
    if(<condition>){
      it = users.erase(it);
    } else {
    ++it;
    }
 }
voltento
źródło