iteradores bidireccionales en unordered_map?

El siguiente ejemplo mínimo:iteradores bidireccionales en unordered_map?

#include <iostream> 

#include <boost/unordered_map.hpp> 

int main() 
{ 
     boost::unordered_map<int, int> m; 
     boost::unordered_map<int, int>::const_iterator i; 

     m.insert(std::make_pair(1, 2)); 

     i = m.end(); 
     --i; 

     std::cout << i->first << " -> " << i->second << std::endl; 

     return 0; 
}

... falla al compilar.

bidi.cxx: In function ‘int main()’: 
bidi.cxx:13: error: no match for ‘operator--’ in ‘--i’

Según Boost's own documentation:

iterator, const_iterator son de al menos la categoría adelante.

Parecería que eso es todo lo que son. ¿Por qué? ¿Qué restricción técnica impone un hash-map que impide que los iteradores sean bidireccionales?

(gcc versión 4.1.2, Boost versiones 1.40.0 y 1.43.0.)

Fuente

2010-06-08 Thanatos

Esto es pura especulación, pero ten en cuenta que para poder atravesar algo hacia atrás Y hacia adelante, cada nodo necesitaría tener un puntero al siguiente elemento Y al elemento anterior. Si este mapa se implementara SOLAMENTE con punteros a los siguientes elementos, entonces su iterador no tendría forma de descubrir qué ocurría antes del nodo actual, y por lo tanto no hay forma de ir hacia atrás. –

Honestamente, me parece un poco extraño (aunque de vez en cuando útil) que los mapas desordenados incluso tengan iteradores. –

@Niki Yoshiuchi: He usado mucho el concepto correspondiente en Perl. Por lo general, quiero que los hashes de Perl funcionen como matrices asociativas, pero a veces quiero hacer algo con todo el hash. En Perl, utilizo la función 'keys' para obtener una lista de las claves y recorrerla, mientras que en C++ la equivalencia obvia es un iterador directo. Realmente extrañaría la posibilidad de hacer el equivalente de 'foreach' en cualquier colección de datos. –

No hay ninguna razón técnica por un unordered_map no puede tener iteradores bidireccionales. La razón principal es que agregaría un costo adicional a la implementación, y los diseñadores pensaron que nadie necesitaría realmente iteradores bidireccionales en un mapa hash. Después de todo, no hay orden en un hash, por lo que el orden que el iterador le da es completamente arbitrario. ¿Qué atravesaría una orden fija pero arbitraria al revés?

Normalmente, se puede acceder a un unordered_map elemento por elemento o atravesar todo el mapa. Nunca he hecho lo contrario en Perl, yo mismo. Para hacer esto, es necesario un iterador directo, y por lo tanto hay uno allí, y Boost lo garantiza. Para tener iteradores bidireccionales, es probable que sea necesario incluir un puntero adicional en cada entrada, lo que aumenta el uso de la memoria y el tiempo de procesamiento.

No se me ocurre un caso de uso bueno y plausible para iteradores bidireccionales aquí. Si puede, puede pedirle a los mantenedores de Boost que lo tengan en cuenta, aunque es casi seguro que es demasiado tarde para C++ 0x.

Fuente

2010-06-08 15:15:30

En realidad, pensé que la parte de los mapas hash que devolvía los resultados en un orden arbitrario era bastante convincente. Los casos de uso habituales son una búsqueda o una iteración completa. En mi cabeza, siempre se implementaron con un vector de cubos, y un cubo siendo una lista estándar. Nunca se consideraron los ahorros de, posiblemente, el uso de una lista individualmente vinculada. – Thanatos

iteradores bidireccionales en unordered_map?

Respuesta

Cuestiones relacionadas