español - map c++
Contenedores STL ordenados dinámicamente (12)
Soy bastante nuevo en el STL, así que me preguntaba si hay contenedores dinámicamente clasificables. Por el momento, mi pensamiento actual es usar un vector junto con los diversos algoritmos de ordenación, pero no estoy seguro de si hay 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 en el que pueda modificar el orden de clasificación en tiempo de ejecución, por ejemplo, ordenarlo en orden ascendente y luego volver a ordenarlo en orden descendente.
Definitivamente debe usar un conjunto / mapa. Como hazzen dice, obtienes O (log n) insert / find. No obtendrás esto con un vector ordenado; puede obtener O (log n) find usando la búsqueda binaria, pero la inserción es O (n) porque insertar (o eliminar) un elemento puede hacer que todos los elementos existentes en el vector se desplacen.
El stl no proporciona tal contenedor. Puede definir uno propio, respaldado por un set/multiset o un vector , pero tendrá que reordenar cada vez que la función de clasificación cambie llamando al sort (para un vector ) o creando una nueva colección (para set/multiset ).
Si solo desea cambiar del orden de clasificación creciente al orden de clasificación decreciente, puede usar el iterador inverso en su contenedor llamando a rbegin() y rend() lugar de begin() y end() . Tanto el vector como set/multiset son contenedores reversibles, por lo que esto funcionaría para cualquiera.
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 recuperar. Si tiene operaciones de búsqueda viril, entonces un vector ordenado puede ser más apropiado y luego use lower_bound para buscar el elemento.
Además, su segundo requisito de recurrir en un orden diferente en el tiempo de ejecución realmente significará que el set y multiset no son apropiados porque el predicado no se puede modificar en un tiempo de ejecución.
Por lo tanto, recomendaría un vector ordenado. Pero recuerde pasar el mismo predicado a lower_bound que pasó a la clasificación anterior, ya que los resultados serán indefinidos y muy probablemente incorrectos si pasa el predicado incorrecto.
Los mapas y conjuntos de STL son contenedores ordenados.
En segundo lugar, la recomendación del libro de Doug T: el libro de Josuttis STL es el mejor que he visto como libro de aprendizaje y referencia.
Effective STL es también un excelente libro para aprender los detalles internos de STL y lo que debe y no debe hacer.
No es tan simple. En mi experiencia, insertar / eliminar se utiliza con menos frecuencia que encontrar. La ventaja del vector ordenado es que requiere menos memoria y es más compatible con la memoria caché. Si tiene una versión que es compatible con los mapas STL (como la que he vinculado anteriormente) es fácil cambiar de un lado a otro y usar un contenedor óptimo para cada situación.
Para el vector ordenado "compatible con STL", vea el AssocVector de A. Alexandrescu de Loki .
Parece que quieres un contenedor de varios índices . Esto le permite crear un contenedor y decirle a ese contenedor las diversas formas en que puede atravesar los artículos que contiene. El contenedor guarda varias listas de los elementos y esas listas se actualizan en cada inserción / eliminación.
Si realmente desea volver a ordenar el contenedor, puede llamar a la función std::sort en cualquier std::deque , std::vector , o incluso en una simple matriz de estilo C. Esa función toma un tercer argumento opcional para determinar cómo ordenar los contenidos.
Querrá consultar std :: map
std::map<keyType, valueType>
El mapa está ordenado en función del <operador proporcionado para keyType.
O
std::set<valueType>
También se ordena en el <operador del argumento de la plantilla, pero no permite los 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 más completa de la biblioteca estándar, muy legible y repleta de información oscura y no tan oscura.
Además, como se menciona en 17 de 26, Vale la pena leer Effective Stl by Meyers.
Set y multiset usa un árbol binario subyacente; puede definir el operador <= para su propio uso. Estos contenedores se mantienen ordenados, por lo que puede que no sea la mejor opción si está cambiando los parámetros de clasificación. Los vectores y listas son probablemente los mejores si va a recurrir un poco; en la lista general tiene su propio tipo (generalmente un mergesort) y puede usar el algoritmo de búsqueda binaria stl en vectores. Si las inserciones dominarán, la lista supera al vector.
Si sabes que vas a ordenar un único valor ascendente y descendente, entonces configura tu amigo. Use un iterador inverso cuando desee "ordenar" en la dirección opuesta.
Si sus objetos son complejos y va a ordenar de muchas maneras diferentes según los campos de miembros dentro de los objetos, entonces probablemente esté mejor utilizando un vector y ordenando. Intente hacer sus inserciones todo a la vez, y luego llame al género una vez. Si eso no es factible, entonces la deque puede ser una mejor opción que el vector para grandes colecciones de objetos.
Creo que si estás interesado en ese nivel de optimización, es mejor que perfile tu código con datos reales. (Este es probablemente el mejor consejo que cualquier persona de aquí puede ofrecer: puede que no importe que llame a ordenar después de cada inserción si solo lo hace una vez en una luna azul).
en teoría, un contenedor asociativo (conjunto, multiset, mapa, multimapa) debería ser su mejor solución.
En la práctica, depende del número promedio de los elementos que está insertando. Para menos de 100 elementos, un vector es probablemente la mejor solución debido a: - evitar la asignación continua - desasignación - caché amigable debido a la ubicación de los datos; estas ventajas probablemente superen sin embargo clasificación continua. Obviamente, también depende de la cantidad de deleción de inserción que tenga que hacer. ¿Vas a hacer inserción / eliminación por cuadro?
Más en general: ¿está hablando de una aplicación de rendimiento crítico?
recuerda no optimizar prematuramente ...
std::set es básicamente un contenedor ordenado.