In C ++, la rimozione di un oggetto da un elenco

Question

Sto scrivendo un programma che è più o meno in questo modo:

#include <list>

list<MyClass> things;

class MyClass {
   // some stuff

   void remove() {
       things.remove_if(THING_IS_ME);
   }
};

Di cosa ho bisogno di scrivere al posto di THING_IS_ME?

In altre parole, sto usando un elenco STL globale come un insieme di cose. A un certo punto, un oggetto che è nell'elenco riconosce che è ridondante e vuole a) ottenere sé rimosso dalla lista, e b) ottenere stessa distrutto.

Come posso fare questo?

non ho scritto C ++ per circa 15 anni e sono un po 'confuso da questa pagina qui: http://www.cplusplus.com/reference/algorithm/remove_if/

Quali sono questi predicati? Non C ++ hanno funzioni di ordine superiore ora?

Answer 1

(In origine una serie di commenti, ma riscritta come una risposta dopo aver scoperto quello che il PO in realtà voleva fare.)

Ti rendi conto che il negozio contenitori STL copie di cose che si inseriscono, giusto? Ciò significa che le istanze di MyClass meglio essere paragonabile (per esempio tramite operator==) -. Non si può semplicemente confrontare gli indirizzi in quanto saranno sempre diverso

Se avere copie di MyClass non ha senso, allora probabilmente stai meglio con un puntatore contenitore .

Detto questo, il C ++ usa un linguaggio di copia-semantica per impostazione predefinita. Il linguaggio richiede che si fanno le cose come riferimenti espliciti nel codice. Mi raccomando che si prende in mano un buon C ++ libro o si essere scattato da problemi come questo in futuro.

Answer 2

Le cose sono cambiate radicalmente in C ++ negli ultimi 15 anni. Nella proposta di luglio 1994 Alexander Stepanov di una libreria che incorpora le sue idee di programmazione generica ricevuto l'approvazione finale da parte del comitato ANSI / ISO. Questa libreria che noi oggi chiamiamo comodamente lo STL in seguito divenne una libreria standard C ++. La storia del STL è quanto di più affascinante come le idee dietro di esso, e sicuramente vale la pena di lettura.

La funzione std::remove_if() che avete trovato è solo un altro riflesso di questa filosofia che è diventato parte dell'identità moderna C ++ 's. In breve, questa è una funzione generica che funziona su qualsiasi contenitore (sequenza) di elementi e con qualsiasi (cosa che agisce come a) condizione. A tal fine, è necessario fornire la funzione di due cose:

1. un paio di iteratori che delimitano la gamma di elementi che si desidera lavorare su;
2. e predicato che, quando viene richiamato su un elemento, restituisce vero se l'elemento deve essere rimosso e falso in caso contrario.

Come si è visto, in questo caso il predicato che si desidera è quello di uguaglianza. E perché è un compito comune per rimuovere elementi basata sulla parità standard fornisce anche la funzione std::remove(), che assume un predicato di uguaglianza implicita. Naturalmente, è necessario assicurarsi che gli elementi possono confrontare:

bool operator==(const MyClass& a, const MyClass& b)
{
    // return true if the two are equal, and false otherwise.
}

Possiamo quindi utilizzare il nostro predicato per rimuovere elementi di tipo MyClass:

std::remove(things.begin(), things.end(), *this);  // if *this == elem

Si ricordi che la funzione std::remove() standard funziona su qualsiasi contenitore, anche quelli che non sono ancora stati creati. Perché ogni sorta di contenitore ha il suo modo di rimuovere elementi, questa funzione non può realmente eseguire la rimozione senza conoscere i dettagli di implementazione del contenitore funziona su. Così, invece, gli elementi funzionali std::remove() swap intorno tale che gli elementi "cancellata" sono alla fine del contenitore. Poi, restituisce un iteratore che punta al primo elemento degli elementi consecutivi "rimossi".

typedef std::list<MyClass>::iterator iter;
iter first_removed = std::remove(things.begin(), things.end(), *this);

Infine, rimuoviamo veramente elementi chiamando la funzione di rimozione del contenitore specifico, che funziona su una singola posizione nella lista o su una serie di elementi consecutivi per rimuovere:

things.erase(first_removed, things.end());

Non è raro vedere questa sorta di codice in una sola riga:

things.erase(std::remove(things.begin(), things.end(), *this),
             things.end());

Tutto questo può sembrare eccessivo e complicato, ma ha alcuni vantaggi. Per prima cosa, questo disegno di libreria standard supporta la programmazione dinamica. Permette anche la libreria standard ai contenitori di offerta con le interfacce molto sottili, così come alcune funzioni gratuite che il lavoro su diversi tipi di contenitori. Esso consente di creare rapidamente un contenitore e immediatamente ottenere tutte le caratteristiche della libreria standard per il lavoro con esso. In alternativa, si permette di scrivere rapidamente una funzione generica che funziona istantaneamente con tutti i contenitori standard -. Quelle già scritte e quelle non ancora scritte

Answer 3

In primo luogo, un semplice ciclo scritto a mano:

for( list<MyClass>::iterator it = things.begin(); it != things.end(); /*  */ ) {
    if( qualifiesForDelete( *it ) ) {
        it = things.erase( it );
    }
    else {
        ++it;
    }
}

In secondo luogo, utilizzando l'algoritmo del remove_if. remove_if essendo un algoritmo, al contrario di una funzione membro di list, non può effettivamente eliminare elementi, piuttosto sposta l'elementi-essere-soppressi verso la fine dell'elenco. Successivamente erase deve essere richiamato. Questo è un idioma molto importante, erase-rimuovere linguaggio , che deve essere appresa.

things.erase( 
    remove_if( things.begin(), things.end(), deletionPredicate ), 
    things.end() 
);

dove deletionPredicate è una funzione o oggetto-funzione che prende un singolo parametro di tipo e ritorna bool. Gli elementi di cui viene restituita true sono considerati per essere rimosso.

Answer 4

La funzione remove_if prende tre parametri: due iteratori che definiscono la gamma di cui si sta lavorando, e un predicato (funzione di test che restituisce bool). L'inizio iteratore punta al primo elemento che si desidera lavorare su; i punti di fine iteratore all'elemento dopo l'ultimo elemento della gamma.

Nell'esempio dalla href="http://www.cplusplus.com/reference/algorithm/remove_if/" si è collegato al , il predicato è la linea di codice che dice

bool IsOdd (int i) { return ((i%2)==1); }

Per rendere il codice fare quello che vuoi, avresti bisogno di scrivere qualcosa di simile:

things.remove_if(things.begin(), things.end(), SomePredicateFunction);

e desideri definire SomePredicateFunction in questo modo (sostituendo true con un test appropriato):

bool SomePredicateFunction (MyClass c) { return true; }