c++ - qarraydata qt

Complejidad de std:: list:: empalme y otros contenedores de lista

Question

Tengo un código que trata con varios objetos std :: list, y actualmente estoy usando un método muy ineficiente para transferir contenido entre ellos (estoy iterando a través de secciones arbitrarias de una lista, y moviendo los elementos uno por uno al segundo lista). Escribí este código hace algún tiempo antes de conocer la función std :: list :: splice, con la que ahora intento reemplazar mi código, por ejemplo:

list<string> list1, list2;

list1.push_back("a");
list1.push_back("b");
list1.push_back("c"); // list1: "a", "b", "c"

list<string>::iterator iterator1 = list1.begin();
iterator1++: // points to "b"

list2.push_back("x");
list2.push_back("y");
list2.push_back("z"); // list2: "x", "y", "z"

list<string>::iterator iterator2 = list2.begin();
iterator2++; // points to "y"

list1.splice(iterator1, list2, iterator2, list2.end());

// list1: "a", "y", "z", "b", "c"
// list2: "x"

Tengo una pregunta sobre la complejidad de la función de empalme. De acuerdo con esta fuente:

http://www.cplusplus.com/reference/stl/list/splice/

Debe tener una complejidad lineal en el rango entre el primer y el último elemento que se empalma en (iterator2 y list2.end () en mi ejemplo), y la fuente sugiere que esto se debe al avance del iterador. Puedo vivir con esto, pero esperaba una complejidad constante.

Mi suposición (antes de encontrar esta fuente) era que la función de empalme hiciera algo como esto:

1. Corta el enlace entre "x" e "y"
2. Corta el enlace entre "z" y list2.end ()
3. Forme un enlace entre "x" y list2.end ()
4. Cortar el enlace entre "a" y "b"
5. Formar un enlace entre "a" e "y"
6. Formar un enlace entre "y" y "b"

Así restaurando ambas listas para completar cadenas.

El mismo principio se aplicaría entonces a las listas de tamaño arbitrario. No estoy seguro de ver dónde está la necesidad de la función de empalme para avanzar en cualquier iterador, ya que le proporciono todos los iteradores que necesita para hacer su trabajo.

Entonces mi pregunta es, ¿cómo lidia la especificación C ++ con esto? ¿Rompe y vuelve a formar los enlaces solo en los puntos inicial y final del empalme, o avanza a través de cada enlace uno por uno? Si este último, ¿algún otro contenedor de listas (por ejemplo, de QT) proporciona el primero? Mi código reside dentro del bucle interno de un programa de simulación, por lo que darle complejidad constante en lugar de lineal sería bastante valioso.

Answer 1

Este fue un tema muy polémico durante la estandarización de C ++ 11. El problema es que todos los contenedores estándar, incluidas las listas, también tienen una operación de size tiempo constante.

Antes de C ++ 11, muchas implementaciones hacían el tiempo lineal de size y el splice entre diferentes listas de tiempo constante. C ++ 11 ahora requiere que el size sea ​​constante y que el splice sea ​​lineal.

El problema es que, si la longitud del rango empalmado no se cuenta uno por uno, los contenedores no pueden realizar un seguimiento de cuántos elementos se eliminaron y agregaron, y la siguiente llamada al size necesitaría recuperar esta información en O (N) tiempo - usando el N más grande de toda la secuencia, no solo la parte empalmada.

Un contenedor de list no estándar puede proporcionar la operación deseada, ya que siempre que no necesite el size O (1), su argumento es correcto.

En cuanto a otras bibliotecas ... no conozco ninguna, pero Boost debería tener una. (Lo verifiqué, no es así, así que ¡alguien vaya a empezar!) Ya que usted entiende claramente cómo escribir el suyo, hacerlo puede ser menos esfuerzo que contestar con una biblioteca tan grande como Qt.

Si no necesita seguridad de subprocesos, podría implementar un derivador alrededor de std::list en el que cada contenedor solo posee un subintervalo de una lista singleton. Esto eliminaría la mayor parte del esfuerzo de programación al replicar la interfaz estándar.