remove_if equivalente per std :: map

Question

Stavo cercando di cancellare un intervallo di elementi dalla mappa in base a condizioni particolari. Come posso farlo utilizzando gli algoritmi STL?

Inizialmente ho pensato di usare remove_if ma non è possibile poiché remove_if non funziona per il contenitore associativo.

C'è qualche " remove_if " algoritmo equivalente che funziona per la mappa?

Come semplice opzione, ho pensato di passare in rassegna la mappa e cancellare. Ma passare in rassegna la mappa e cancellare un'opzione sicura? (Poiché gli iteratori diventano non validi dopo la cancellazione)

Ho usato il seguente esempio:

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

Quasi.

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

Ciò che avevi originariamente incrementerebbe l'iteratore due volte se cancellassi un elemento da esso; potresti potenzialmente saltare gli elementi che dovevano essere cancellati.

Questo è un algoritmo comune che ho visto usato e documentato in molti luoghi.

[EDIT] Hai ragione sul fatto che gli iteratori sono invalidati dopo una cancellazione, ma solo gli iteratori che fanno riferimento all'elemento che è stato cancellato, altri iteratori sono ancora validi. Quindi utilizzare iter ++ nella chiamata erase ().

Answer 2

erase_if per std :: map (e altri contenitori)

Uso proprio il seguente modello proprio per questo.

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

Questo non restituirà nulla, ma rimuoverà gli oggetti dalla std :: map.

Esempio di utilizzo:

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

Secondo esempio (consente di passare un valore di prova):

// '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

Ho ricevuto questa documentazione dal eccellente riferimento SGI STL :

  

La mappa ha l'importante proprietà che   inserendo un nuovo elemento in una mappa   non invalida gli iteratori che   indicare elementi esistenti. Cancellazione di un   anche l'elemento da una mappa non lo fa   invalidare eventuali iteratori, ad eccezione di   ovviamente, per gli iteratori che in realtà   punta sull'elemento che è   cancellati.

Quindi, l'iteratore che hai che punta all'elemento da cancellare sarà ovviamente invalidato. Fai qualcosa del genere:

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

Answer 4

Il codice originale ha un solo problema:

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

Qui iter viene incrementato una volta nel ciclo for e un'altra volta nella cancellazione, che probabilmente finirà in un ciclo infinito.

Answer 5

Ora, std::experimental::erase_if è disponibile nell'intestazione <experimental/map>.

Vedi: http://en.cppreference.com/w/cpp / sperimentale / carta / erase_if

Answer 6

Dalle note di fondo di:

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

un contenitore associativo di coppia non può fornire iteratori mutabili (come definito nei requisiti Iteratore triviale), poiché il tipo di valore di un iteratore mutabile deve essere assegnabile e la coppia non è assegnabile. Tuttavia, un contenitore associativo di coppia può fornire iteratori che non sono completamente costanti: iteratori tali che l'espressione (* i) .second = d è valida.

Answer 7

Prima

  

La mappa ha la proprietà importante che l'inserimento di un nuovo elemento in una mappa non invalida gli iteratori che puntano a elementi esistenti. Anche la cancellazione di un elemento da una mappa non invalida alcun iteratore, tranne, ovviamente, per gli iteratori che puntano effettivamente all'elemento che viene cancellato.

Secondo, il seguente codice è buono

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

Quando si chiama una funzione, i parametri vengono valutati prima della chiamata a quella funzione.

Quindi quando iter ++ viene valutato prima della chiamata da cancellare, l'operatore ++ dell'iteratore restituirà l'elemento corrente e punterà all'elemento successivo dopo la chiamata.

Answer 8

IMHO non esiste remove_if() equivalente.
Non è possibile riordinare una mappa.
Quindi erase() non può mettere alla fine le tue coppie di interessi sulle quali puoi chiamare <=>.

Answer 9

Basato su Risposta di Iron Savior Per coloro che desiderano fornire un intervallo più lungo le linee di std funzionali prendendo iteratori .

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

Curioso se c'è un modo per perdere gli oggetti ContainerT e ottenerli dall'iteratore.

Answer 10

Risposta di Steve Folly Mi sento più efficiente.

Ecco un'altra soluzione facile ma meno efficiente :

La soluzione utilizza remove_copy_if per copiare i valori desiderati in un nuovo contenitore, quindi scambia i contenuti del contenitore originale con quelli di quello nuovo:

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

Se vuoi cancellare tutti gli elementi con chiave maggiore di 2, il modo migliore è

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

Funziona solo per intervalli, non per alcun predicato.

Answer 12

Uso così

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