¿El orden de iteración std :: set siempre es ascendente según la especificación C++?

Question

Aquí http://www.cplusplus.com/reference/stl/set/ He leído que std :: set en C++ se implementa "típicamente" como un árbol (rojo-negro?) Y está ordenado.

No pude entender, ¿significa que según la especificación el orden de iteración del conjunto siempre es ascendente? ¿O es solo un "detalle de implementación habitual" y, a veces, alguna biblioteca/compilador puede violar esta convención?

Answer 1

Según el estándar C++, la iteración sobre los elementos en un std::set procede en orden ordenado según lo determinado por std::less o mediante el argumento opcional de plantilla de predicado de comparación.

(también por el C++ estándar, inserción, las operaciones de búsqueda y eliminación tomar como máximo O (lg n tiempo), por lo equilibradas árboles de búsqueda son actualmente la única opción aplicación viable para std::set, a pesar de que el uso del rojo-negro árboles no es obligatorio según el estándar.)

Answer 2

por la especificación iteración orden de juego siempre es ascendente

Sí, los valores del conjunto siempre en orden ascendente si imprime a cabo de forma secuencial. Como dice la descripción, generalmente se implementa utilizando Red-Black Tree (RBT), pero los escritores del compilador tienen la opción de violar esto, pero por lo general se apega al Tema de RBT ya que cualquier otra implementación no será eficiente en recursos para lograr la tarea de set.

Answer 3

El comparador predeterminado es menor, por lo que el conjunto se ordenará de forma ascendente. Para cambiar esto, puede especificar otro comparador existente o personalizado como argumento de plantilla.

Answer 4

Significa que internamente std::set almacenará sus elementos como un árbol ordenado. Sin embargo, la especificación no dice nada sobre el orden de clasificación. De manera predeterminada, std::set usa std::less y ordenará de menor a mayor. Sin embargo, se puede hacer la función de clasificación sea lo que quiera, utilizando este constructor:

std::set<valueType, comparissonStruct> myCustomOrderedSet; 

Así, por ejemplo:

std::set<int, std::greater<int> > myInverseSortedSet; 

o

struct cmpStruct { 
    bool operator() (int const & lhs, int const & rhs) const 
    { 
    return lhs > rhs; 
    } 
}; 

std::set<int, cmpStruct > myInverseSortedSet; 

De hecho, estos ejemplos son también proporcionado en el sitio web que vinculó. Más específicamente aquí: set constructor.

Answer 5

C++ 11 N3337 proyecto de normahttp://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf

23.2.4 "contenedores asociativos" dice:

1 contenedores asociativos proporcionan una rápida recuperación de los datos en función de las teclas. La biblioteca proporciona cuatro tipos básicos de contenedores asociativos : conjunto, multiset, mapa y multimapa.

y:

10 La propiedad fundamental de los iteradores de contenedores asociativos es que iterar a través de los contenedores en el orden no descendente de teclas donde no descendente se define por la comparación que era utilizado para construirlos.

por lo sí, el orden está garantizado por el estándar de C++, que como se ha mencionado https://stackoverflow.com/a/11812871/895245 básicamente requiere una implementación árbol de búsqueda equilibrado.

También contraste con C++ 11 unordered_set, que puede proporcionar un mejor rendimiento ya que tiene menos restricciones: Why on earth would anyone use set instead of unordered_set? p. Ej. usando un conjunto de hash.