Como dices I assume the buckets can get big..., es mejor usar std::list. La búsqueda es lineal en ambos casos, pero la adición de elementos es constante en std::list.
I guess they're all the same, since data isn't ordered - No, no lo son. Si lo fueran, solo habría un contenedor. Cada contenedor tiene sus propias ventajas y desventajas, diferentes contenedores se utilizan para diferentes situaciones.
Un poco de información acerca del vector:
std::vector tiene capacidad , es por eso que tiene capacity() y size() métodos. Ambos son diferentes. Entonces, supongamos que la capacidad es 4 y usted tiene 2 elementos, entonces el tamaño será 2. Entonces, agregar otro elemento incrementará el tamaño (será 3) y todo será muy rápido.
Pero, ¿qué sucede cuando tienes que agregar más de 5 elementos y la capacidad es 4? completamente nueva se asigna memoria, todos elementos antiguos son copiado en la nueva memoria, todos elementos antiguos son destruidos (sus destructores son llamados, si los tipos definidos por el usuario). Entonces la memoria anterior tiene que ser liberado. Estas son operaciones costosas si crees que añadir/eliminar elementos será más frecuente.
Puede evitar esto, usando el método std::vector::reserve para reservar memoria previamente y no reasignar memoria nueva todo el tiempo y copiar todo una y otra vez. Pero esto es útil cuando conoces el tamaño aproximado de estos vectores. Supongo que no lo hace en su situación (reservar mucha memoria tampoco es una buena solución; no debe desperdiciar memoria así como así) Así que, de nuevo, preferiría std :: list.
O double hash.
De todos modos, esta asignación de nueva memoria y copia de objetos no ocurrirá tan a menudo, ya que std::vector es "inteligente" y cuando se asigna espacio nuevo, no aumenta la capacidad con solo 1 elemento o algo. Creo que lo dobla, pero no estoy tan seguro de eso. Argh, no sé exactamente cómo se llama esto en inglés. Probablemente algo así como "acumulación de tiempo/memoria" o "complejidad acumulativa":?No sé:/
NOTA: Elija lo que elija, le sugiero que preste atención en la función hash. Es lo más importante aquí. Un contenedor hash NO debe tener demasiados elementos con el mismo hash. Entonces, mi consejo es buscar una buena función hash y entonces esto no importará mucho.
esperanza de que ayudó a (:
EDIT: Yo te recomiendo este artículo - comparing std::vector and std::deque - es perfecto - se compara el uso de memoria (asignación, desasignación, crecimiento), uso de CPU, etc. que había recomiende site para tales artículos, no hay muchos, pero están muy bien escritos
Vector's OK, no necesariamente óptimo. Remove-from-middle no es eficiente, por lo que si sus cubos pueden agrandarse podría compararlo con 'list' y/o' deque'. Si sus cubos no pueden agrandarse, 'vector' puede sobreasignar. Los tres tienen búsqueda lineal. La estructura de nosotros que puede superar el tiempo de búsqueda lineal es otra tabla hash (o la misma tabla de nuevo), como en el doble hash. Sin un orden no hay nada en las bibliotecas estándar: todo lo que hacen es cosas con órdenes y secuencias puras. –
'deque' puede ser mejor que' vector', porque nunca tiene que reasignar y mover todo. El acceso es un poco más lento, push_back es potencialmente mucho más rápido, dependiendo de qué tan caros sean los elementos para copiar. 'list' normalmente hace más asignación de memoria que cualquiera, y puede ser más lento por esa razón. –