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 mover los elementos uno por uno a la segunda lista). Me escribió este código hace algún tiempo antes de que yo era consciente de la std :: :: función de lista de empalme, que ahora tengo la intención de reemplazar a 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 con respecto a la complejidad de la función de empalme. De acuerdo con esta fuente:

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

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

Mi hipótesis (antes de encontrar esta fuente) era que la función de empalme hacer algo como esto:

1. romper el vínculo entre "x" e "y"
2. romper el vínculo entre la "z" y list2.end()
3. formar un enlace entre "x" y list2.end()
4. Sever el vínculo entre "a" y "b"
5. Forma un vínculo entre "a" y "y"
6. Forma un enlace entre "y" y "b"

Restaurando así ambas listas para completar las cadenas.

El mismo principio se aplicaría 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.

Así que 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 lista (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 a tiempo constante.

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

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

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

Como para otras bibliotecas ... No conozco ninguna, pero Boost debe tener. (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 contenedor 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.