¿`std :: set` ordena los elementos en todos los casos?

Question

De cplusplus.com referencia parece que std::set ordena los elementos.

Necesito tener cadenas ordenadas, pero no estoy seguro si funcionará bien en todas las plataformas y compiladores. Principalmente GCC, MinGW, VC.

Answer 1

Por su definición std::set es un contenedor clasificado. Es parte del estándar. Tenerlo ordenado ayuda a mantener que es un conjunto en lugar de solo una colección arbitraria.

Fuente: http://www.sgi.com/tech/stl/set.html

Answer 2

Sí, std::set tiendas de sus elementos, de tal manera que se itera sobre los elementos seran en forma ordenada (y la llamada a std::adjacent_find es mostrar que std::set tiendas de artículos únicos, así).

#include <algorithm> 
#include <iterator> 
#include <ios> 
#include <iostream> 
#include <set> 
#include <string> 

int main() 
{ 
    auto const ss = std::set<std::string> { "foo", "bar", "test" }; 
    std::cout << std::boolalpha << std::is_sorted(begin(ss), end(ss)) << "\n"; 
    std::cout << std::boolalpha << (std::adjacent_find(begin(ss), end(ss)) == end(ss)) << "\n"; 
    std::copy(begin(ss), end(ss), std::ostream_iterator<std::string>(std::cout, "\n")); 
} 

Live Example

Answer 3

actualy std :: set y std :: mapa no están muy ordenadas. Ambos contenedores se implementan como red-black trees. Por lo tanto, cuando itera ese tipo de contenedores, el iterador recorre el árbol de tal forma que parece que el contenedor está ordenado. Al principio se visita el nodo más a la izquierda entonces el padre de uno más a la izquierda y así sucesivamente ...

Answer 4

C++11 N3337 standard draft 23.2.4 "contenedores asociativos":

contenedores

1 asociativos proporcionan una rápida recuperación de datos basados ​​en claves. 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.

así que sí, la orden está garantizada, lo que como https://stackoverflow.com/a/11812871/895245 mencionado básicamente requiere una implementación equilibrada del árbol de búsqueda.

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.