¿cuál es la estructura de datos subyacente de la lista, vector y conjunto de STL?¿cuál es la estructura de datos subyacente de la lista, vector y conjunto de STL?
Mi solución:
derecho?
Basándose en los comentarios, para aclarar, estas son las opciones más comunes, pero basado en la complejidad deseada y otros factores, con el respaldo de estas implementaciones puede variar:
Vector = cambio de tamaño dinámicamente matriz
Lista = Doubly Linked List
Set = Red/Black Tree (equilibrada árbol de búsqueda binaria)
creo que posiblemente podría estar confundiendo Montones y BSTs. Un montón se visualiza como un árbol, pero en realidad está construido sobre una estructura de lista indexable (por ejemplo, matriz o vector). C++ proporciona funciones de pila a través del algorithm header en el STL. Las BST son más una estructura basada en clave/valor utilizada para la búsqueda eficiente (que es lo que generalmente desea para un conjunto).
es una lista doblemente vinculada – Praetorian
Esto suele ser cierto, pero tenga en cuenta que esta no es la única opción (depende de la implementación). – avakar
@sgusc, el mapa es un árbol rojo-negro, el conjunto no se debe a que los elementos no estén ordenados. ¿Cuál es la diferencia entre la lista y la lista enlazada? ¿Qué es la estructura de datos de la "lista vinculada"? ¿una lista? – user1002288
La norma no ofrece garantías sobre qué estructuras de datos se utilizan, solo hay garantías de complejidad, por lo que la implementación puede elegir cualquier estructura que las cumpla.
Dicho esto, std::vector es por lo general un dynamic array, std::list es probablemente un doubly-linked list y std::set es lo más a menudo algún tipo de self-balancing binary tree.
Implementación definida, pero en general, 'std :: vector' es una matriz dinámicamente asignada. 'std :: list' es una lista doblemente enlazada (C++ 11 introduce' std :: forward_list' que es una lista individualmente enlazada), y un 'set' generalmente se basa en [árboles rojo-negro] (http://en.wikipedia.org/wiki/Red%E2%80%93black_tree), aunque cualquier cosa que se ajuste a los requisitos de complejidad y comportamiento amortizados de las interfaces definidas en el estándar son implementaciones aceptables. La lista – birryree