¿cuál es la estructura de datos óptima para un contenedor de grupo?

Question

Por el momento, utilizo la plantilla de contenedor vectorial STL para volver a colocar y obtener las conexiones.

1) en get, se devuelve una conexión y "erase()" d del vector de grupo.

2) al momento de la liberación, la conexión se devuelve al grupo a través de "push_back()".

Esto puede ser muy pesado si se utiliza con frecuencia la agrupación. Entonces mi pregunta es, ¿hay alguna forma de mejorar el rendimiento aquí cambiando a otra estructura de datos?

Answer 1

• Si solo se agrega en la parte posterior y se borra de la parte posterior, vector está bien.
• Si agrega y borra desde el frente y atrás, pero nunca desde el medio, use deque.
• Si con frecuencia debe insertar y borrar desde el medio, use list.
• Dependiendo de sus requisitos de búsqueda y recorrido, set podría ser una alternativa.

En cualquier caso, debe perfil el rendimiento; use un typedef para su contenedor principal para que pueda cambiar y probar rápidamente las diferentes opciones.

Puede haber otros requisitos que no nos están diciendo, pero que son importantes para la elección del envase:

• del vector y deque son contenedores de acceso aleatorio; list y set están basados ​​en nodos. Esto afecta la invalidación del iterador.
• vector, deque y la lista son contenedores de secuencia, mientras que el conjunto es asociativo; esto afecta la búsqueda por valor.

Answer 2

Guarde el vector si conoce el número máximo de conexiones posibles por adelantado (consulte el vector :: reserva).

De lo contrario, use std :: list.

Al final también depende de su plataforma y de la versión del compilador utilizado y libstdC++.

Answer 3

std::vector es probablemente el mejor contenedor para piscina. O (1) para inserción y también puede tener O (1) para eliminarlo si no necesita mantener el orden. Puede cambiar el último elemento con el elemento eliminado y reducir el tamaño del vector. También std::vector es bastante eficiente en cuanto a espacio en comparación con otros contenedores. El bajo consumo de memoria también significa un mejor rendimiento debido a más éxitos de la memoria caché de la CPU.