remove_if odpowiednik dla std :: map

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

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.

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

Teraz std::experimental::erase_ifjest dostępny w nagłówku <experimental/map>.

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

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

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.

Oto eleganckie rozwiązanie.

for (auto it = map.begin(); it != map.end();)
{   
    (SomeCondition) ? map.erase(it++) : (++it);
}

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.

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.

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().

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.

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

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.

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