5
¿Es esto solo un efecto secundario de implementación (árbol rojo-negro) o la orden está garantizada por el estándar C++?¿Están garantizados los elementos de un std :: map ordenados?
A
Respuesta
11
La iteración ordenada no es un detalle de implementación; está garantizado por el estándar C++. Es una propiedad fundamental de todos los contenedores asociativos (C++ 03 §23.1.2/9):
La propiedad fundamental de los iteradores de contenedores asociativos es que iterar a través de los contenedores en el orden no descendente de claves donde no descendente se define por la comparación que se utilizó para construirlas. Para cualquier par de iteradores Dereferenceable
iyjque tal distanciai-jes positivo,value_comp(*j, *i) == false
value_comp es el comparador con la que el mapa se construyó (por defecto, es std::less<T>).
+0
+1. Por supuesto, esto no es cierto para los tipos desordenados. – rlbond
+2
@rlbond: cierto. Sin embargo, C++ 03 no tiene contenedores asociativos desordenados y en C++ 0x se clasifican por separado (los "contenedores asociativos" son independientes de los "contenedores asociativos no ordenados"). –
2
Está garantizado por el estándar C++.
+0
Es genial si me puede indicar esta parte del estándar. – Thomson
0
Garantizado. Si desea algo que no esté restringido por este try boost :: unordered_map <>
+0
O, similarmente, 'std :: tr1 :: unordered_map <> '. – Frank
4
§23.1.2/2:
Cada contenedor asociativo es parametrizado en
Keyy un ordenamiento relaciónCompareque induce una estricta ordenamiento débil (25.3) en los elementos deKey. ... El objeto del tipoComparees llamado el objeto de comparación de un contenedor . Este objeto de comparación puede ser un puntero a la función o un objeto de un tipo con un operador de llamada a función apropiado.
El objeto predeterminado Compare es la función menor que std::less<Key>.
El pedido es una propiedad de la función. Es un requisito, no un efecto secundario.
Ordenando los objetos son un efecto secundario. 23.1.2/10 y 23.1.2/9 (citado por James) garantizan que map/set y multimap/multiset tienen teclas de aumento/no disminución, respectivamente, en la secuencia de begin a end.
Cuestiones relacionadas
- 1. ¿Están C++ std :: map <string, string> ordenados?
- 2. std :: map insert o std :: map find?
- 3. Boost.Bind para acceder a los elementos de std :: map en std :: for_each
- 4. Cómo obtener los primeros n elementos de un estándar :: map
- 5. Mapping std :: map to Python
- 6. Cómo insertar en std :: map?
- 7. Cómo convertir un std :: list ordenado de std :: pair a un std :: map
- 8. C++: Heredar de std :: map
- 9. std :: map ordena por datos?
- 10. usando BOOST_FOREACH con std :: map
- 11. Requisitos de tipo para std :: map
- 12. ¿Cómo puedo establecer la distancia entre los elementos ordenados verticalmente?
- 13. Porting std :: map to C?
- 14. Punteros a elementos de std :: vector y std :: list
- 15. ¿Los literales de cadena están garantizados para estar adyacentes entre sí en la memoria?
- 16. std :: map :: emplace() falta - ¿bibliotecas desactualizadas?
- 17. ¿Están obsoletos los mapas de imagen <map>?
- 18. Usando Hadoop, ¿están garantizados mis reductores para obtener todos los registros con la misma clave?
- 19. ¿Cómo eliminarías los elementos de un std :: vector en función de alguna propiedad de los elementos?
- 20. Realizar un seguimiento de los elementos eliminados usando std :: remove_if
- 21. Persistencia de std :: map en C++
- 22. ¿Alguien puede recomendar un contenedor de reemplazo C++ std :: map?
- 23. Cómo obtener elementos ordenados desde una cuadrícula de datos
- 24. std :: map of member function punteros?
- 25. Usando std :: string como clave para std :: map
- 26. ¿Cómo funciona el iterador std :: map?
- 27. C++ Almacenamiento de referencias a valores en std :: map
- 28. const std :: map <boost :: tuples :: tuple, std :: string>?
- 29. ¿Hay alguna manera de intersectar/diff un std :: map y un std :: set?
- 30. Complejidad del tiempo de find() en std :: map?
La clase es std :: map, not stl :: map. –
No, la implementación (árbol rojo-negro, pero no necesariamente) se elige para cumplir con el requisito de pedido. – UncleBens