Elenco C++ per rimuovere le stringhe duplicate

Question

Ho un piccolo problema quando uso le liste.

Cosa ho: Sto leggendo le righe da una chatbox dove nuove righe di testo vengono di tanto in tanto. Prendo sempre le ultime 20 righe dalla scatola, quindi voglio confrontarle con tutte le linee che ho recuperato prima. Se viene scoperta una nuova linea, viene inviata a una funzione esterna che disassembla la linea per un'ulteriore elaborazione. Prima ho usato array e vettori, ma la lista sembra essere il modo migliore per farlo.

La mia idea: Ho una lista chiamata usedlines che contiene tutte le vecchie linee già utilizzate. L'elenco fetchedLines contiene le ultime 20 righe recuperate dalla chat.

No Voglio semplicemente eseguire il ciclo su entrambi per scoprire se le righe recuperate contengono una nuova riga non visualizzata in precedenza. Dopo il ciclo, i resti nelle linee di lettura vengono gestiti fino alla funzione successiva.

Problema: quando eseguo il loop di questo ciclo, dopo un po 'ho un cattivo punto. Perché? Bonus: Qualcuno ha un'idea migliore per risolvere questo compito?

typedef list<string> LISTSTR; 
LISTSTR::iterator f; 
LISTSTR::iterator u; 
LISTSTR fetchedlines;     
LISTSTR usedLines;     



fetchedlines.insert(fetchedlines.end(), "one"); 
fetchedlines.push_back("two"); 
fetchedlines.push_back("three"); 
fetchedlines.push_back("four"); 
fetchedlines.push_back("three"); 

usedLines.push_back("three"); 
usedLines.push_back("blää"); 
usedLines.push_back("lumpi"); 
usedLines.push_back("four"); 


for (u = usedLines.begin(); u != usedLines.end(); u++) 
{ 
for (f = fetchedlines.begin(); f != fetchedlines.end(); f++) 
    { 
    if(*u==*f) 
    fetchedlines.remove(*f); 
    } 

} 

Answer 1

Non è mai necessario modificare un elenco (o quasi tutti gli altri contenitori) durante l'iterazione su di esso. Questo è il tuo problema immediato.

Un problema più interessante è il motivo per cui lo state facendo in questo modo. Non c'è un modo per ottenere numeri sequenziali sulle linee, o forse i timestamp, in modo da poterli confrontare?

Answer 2

La chiamata a fetchedlines.remove(*f) sta invalidando l'iteratore.

EDIT:

Una possibile soluzione al problema che si è invece semplicemente scorrere usedLines e rimuovere tutti gli elementi che sono contenuti fetchedlines.

for (u = usedLines.begin() u != usedLines.end(); u++) 
    fetchedLines.remove(*u); 

//Process all of fetchedLines 

Answer 3

Si sta rimuovendo un elemento da fetchedlines mentre si sta iterando su di esso.

Ecco perché si ottiene un puntatore non valido.

Answer 4

Perché * f è un iteratore che punta a un elemento appena cancellato.

provare quanto segue:

if(*u==*f) 
{ 
    LISTSTR::iterator t = f;; 

    f--; 
    fetchedlines.remove(*t); 
} 

Come un rimuovere parte ricerche attraverso la lista per qualcosa che corrispondono ai dati a cui punta l'iteratore f. Se si vuole semplice sbarazzarsi dei dati puntato si sta meglio facendo

f = fetchedlines.erase(f); 
f--; 

Answer 5

Il motivo che si stanno ottenendo un errore è che fetchedlines.remove (* f) modifica fetchedlines, e se fosse l'ultimo elemento , poi il ciclo di incrementi troppo

provare qualcosa di simile:

for (u = userLines.begin(); u != usedLines.end(); ++u) 
{ 
    for (f = fetchedlines.begin(); f != fetchedlines.end();) 
    { 
     if (*u == *f) 
     { 
      f = fetchedlines.erase (f); 
     } 
     else 
     { 
      ++f; 
     } 
    } 
} 

(che è ovviamente non affrontare se questo è un buon modo per risolvere il problema)

Answer 6

Questo può essere fatto con list::remove_if e un'espressione lambda. Questo metodo è ancora due cicli nidificati ma sono nascosti all'interno delle chiamate di funzione. Questo può essere abbastanza veloce per le liste di piccole dimensioni, ma non scalerà molto bene. Potrebbe essere molto più veloce se i dati sono stati ordinati o se hai usato un contenitore ordinato.

fetchedLines.remove_if([&](std::string &str) 
{ 
    return std::find(usedLines.begin(), usedLines.end(), str) != usedLines.end(); 
});