Lista de C++ eliminar cadenas duplicadas

Question

Tengo un pequeño problema cuando uso listas.

Lo que tengo: Estoy leyendo líneas de un chat donde nuevas líneas de texto vienen de vez en cuando. Siempre busco las últimas 20 líneas del cuadro, luego quiero compararlas con todas las líneas que he buscado antes. Si se descubre una nueva línea, se envía a una función externa que desensambla la línea para su posterior procesamiento. Antes usaba matrices y vectores, pero la lista parece ser la mejor manera de hacerlo.

Mi idea: Tengo una lista llamada usedlines que contiene todas las líneas viejas ya usadas. La lista fetchedLines contiene las 20 líneas más recientes extraídas de la ventana de chat.

No, simplemente quiero pasar a través de ambos para ver si las líneas captadas contienen una nueva línea no vista anteriormente. Después del ciclo, los restos de las líneas capturadas se manejan a la siguiente función.

Problema: Cuando recorro este ciclo, obtengo un puntero malo después de un tiempo. ¿Por qué? Bonificación: ¿Alguien tiene una mejor idea para resolver esta tarea?

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

Nunca debe modificar una lista (o casi cualquier otro contenedor) mientras itera sobre ella. Ese es tu problema inmediato.

Un problema más interesante es por qué lo hace así en primer lugar. ¿No hay una forma de obtener números secuenciales en las líneas, o tal vez marcas de tiempo, por lo que podría simplemente compararlos?

Answer 2

La llamada a fetchedlines.remove(*f) es invalidante su iterador.

EDIT:

Una posible solución al problema que tiene es que en lugar de simplemente repetir usedLines y eliminar todos los elementos en fetchedlines que están contenidos.

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

//Process all of fetchedLines 

Answer 3

Usted está quitando un elemento de fetchedlines mientras que su están iterando ella.

Es por esto que obtienes un puntero malo.

Answer 4

Porque * f es un iterador que apunta a un elemento que acaba de borrar.

intente lo siguiente:

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

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

Como acotación al margen eliminar las búsquedas a través de la lista para algo que coincida con los datos apuntados por el iterador f. Si desea sencilla de deshacerse de los datos apuntaban a que es mejor hacer

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

Answer 5

La razón de que está recibiendo un error es que fetchedlines.remove (* f) modifica fetchedlines, y si era el último elemento , entonces el bucle para incrementos demasiado

intentar algo como esto:

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

(eso es, por supuesto, no se dirige a si esta es una buena manera de resolver el problema)

Answer 6

Esto se puede hacer con list::remove_if y una expresión lambda. Este método sigue siendo dos bucles anidados, pero están ocultos dentro de las llamadas a funciones. Esto puede ser lo suficientemente rápido para listas pequeñas, pero no se escalará muy bien. Podría ser mucho más rápido si los datos fueron ordenados o si usó un contenedor ordenado.

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