Contenedores STL ordenados dinámicamente

Question

Soy bastante nuevo en STL, así que me preguntaba si hay contenedores que se puedan ordenar dinámicamente.Por el momento, mi idea actual es utilizar un vector junto con los distintos algoritmos de clasificación, pero no estoy seguro de si existe una selección más apropiada dada la (presumiblemente) complejidad lineal de insertar entradas en un vector ordenado.

Para aclarar "dinámicamente", estoy buscando un contenedor cuyo orden de clasificación pueda modificar en tiempo de ejecución, p.ordénelo en orden ascendente y luego vuelva a ordenarlo en orden descendente.

Answer 1

Si sabe que va a ordenar según un único valor de forma ascendente y descendente, entonces set es su amigo.Utilice un iterador inverso cuando desee "ordenar" en la dirección opuesta.

Si sus objetos son complejos y los va a ordenar de muchas maneras diferentes según los campos de miembros dentro de los objetos, entonces probablemente sea mejor usar un vector y ordenar.Intente hacer todas las inserciones a la vez y luego llame a ordenar una vez.Si eso no es factible, entonces deque puede ser una mejor opción que el vector para grandes colecciones de objetos.

Creo que si estás interesado en eso nivel de optimización, será mejor que perfile su código utilizando datos reales.(Cuál es probablemente el mejor consejo que alguien aquí puede dar:Puede que no importe que llames a ordenar después de cada inserción si solo lo haces una vez en una luna azul.)

Answer 2

Querrás mirar std::map

std::map<keyType, valueType>

El mapa se ordena según el operador < proporcionado para keyType.

O

std::set<valueType>

También se ordena según el operador < del argumento de la plantilla, pero no permite elementos duplicados.

hay

std::multiset<valueType>

que hace lo mismo que std::set pero permite elementos idénticos.

Recomiendo encarecidamente "La biblioteca estándar de C++" de Josuttis para obtener más información.Es la descripción general más completa de la biblioteca estándar, muy legible y repleta de información oscura y no tan oscura.

Además, como lo mencionan 17 de 26, vale la pena leer Effective Stl de Meyers.

Answer 3

Parece que quieres un contenedor multiíndice.Esto le permite crear un contenedor y decirle a ese contenedor las diversas formas en que puede desear atravesar los elementos que contiene.Luego, el contenedor mantiene varias listas de elementos, y esas listas se actualizan en cada inserción/eliminación.

Si realmente desea volver a clasificar el contenedor, puede llamar al std::sort funcionar en cualquier std::deque, std::vector, o incluso una simple matriz estilo C.Esa función toma un tercer argumento opcional para determinar cómo ordenar los contenidos.

Answer 4

El stl no proporciona tal contenedor.Puedes definir el tuyo propio, respaldado por un set/multiset o un vector, pero tendrás que volver a ordenar cada vez que la función de clasificación cambie llamando sort (para vector) o creando una nueva colección (por set/multiset).

Si solo desea cambiar de un orden de clasificación creciente a un orden de clasificación decreciente, puede usar el iterador inverso en su contenedor llamando rbegin() y rend() en lugar de begin() y end().Ambos vector y set/multiset Son contenedores reversibles, por lo que esto funcionaría para cualquiera de los dos.

Answer 5

std::set Es básicamente un contenedor ordenado.

Answer 6

Definitivamente deberías usar un conjunto/mapa.Como dice Hazzen, obtienes O(log n) insert/find.No obtendrás esto con un vector ordenado;puede obtener una búsqueda O(log n) mediante la búsqueda binaria, pero la inserción es O(n) porque insertar (o eliminar) un elemento puede provocar que se desplacen todos los elementos existentes en el vector.

Answer 7

No es tan simple.En mi experiencia, insertar/eliminar se usa con menos frecuencia que buscar.La ventaja del vector ordenado es que requiere menos memoria y es más compatible con el caché.Si tiene una versión que es compatible con mapas STL (como la que vinculé antes), es fácil alternar y usar el contenedor óptimo para cada situación.

Answer 8

en teoría, un contenedor asociativo (conjunto, multiconjunto, mapa, multimapa) debería ser su mejor solución.

En la práctica, depende del número promedio de elementos que estés colocando.para menos de 100 elementos, un vector es probablemente la mejor solución debido a:- Evitar la consignación continua -desarnalización - Cache Friendly debido a la localidad de datos, estas ventajas probablemente superarán, sin embargo, la clasificación continua.Obviamente también depende de cuántas inserciones y eliminaciones tengas que hacer.¿Vas a realizar una inserción/eliminación por cuadro?

Más generalmente:¿Estás hablando de una aplicación crítica para el rendimiento?

recuerde no optimizar prematuramente...

Answer 9

La respuesta es, como siempre, depende.

set y multiset son apropiados para mantener los elementos ordenados, pero generalmente están optimizados para un conjunto equilibrado de agregar, eliminar y buscar.Si tiene operaciones de búsqueda masculinas, entonces una ordenada vector puede ser más apropiado y luego usar lower_bound para buscar el elemento.

Además, su segundo requisito de recurrir en un orden diferente en tiempo de ejecución en realidad significará que set y multiset no son apropiados porque el predicado no se puede modificar en tiempo de ejecución.

Por tanto, recomendaría un vector ordenado.Pero recuerda pasar el mismo predicado a lower_bound que pasó al tipo anterior ya que los resultados no estarán definidos y probablemente serán incorrectos si pasa el predicado incorrecto.

Answer 10

Set y multiset utilizan un árbol binario subyacente;puede definir el operador <= para su propio uso.Estos contenedores se mantienen ordenados por sí solos, por lo que puede que no sean la mejor opción si cambia los parámetros de clasificación.Los vectores y las listas probablemente sean mejores si va a recurrir bastante;en general, la lista tiene su propia clasificación (generalmente una clasificación de combinación) y puede usar el algoritmo de búsqueda binaria stl en vectores.Si las inserciones dominan, la lista supera al vector.

Answer 11

Los mapas y conjuntos STL son contenedores ordenados.

Apoyo la recomendación del libro de Doug T: el libro STL de Josuttis es el mejor que he visto como libro de aprendizaje y de referencia.

STL efectivo También es un libro excelente para aprender los detalles internos de STL y lo que debes y no debes hacer.

Answer 12

Para vectores ordenados "compatibles con STL", consulte A.AssocVector de Alexandrescu de Loki.