¿Std :: set almacena objetos contiguos en la memoria?

16

¿ std::setAlmacena objetos en memoria contigua como std::vector?

No he podido encontrar esto en la web, cppreference no menciona detalles sobre la asignación de memoria. Pero no puedo ver por qué no podría usar memoria contigua, de ahí mi pregunta.

c++ set stdset mfnx
fuente
55
Lea los set::insertrequisitos: en.cppreference.com/w/cpp/container/set/insert "... No se invalidan los iteradores ni las referencias ...", por lo que no puede reasignarse cuando necesita expandirse como lo std::vectorhace.
Richard Critten el
Rendimiento: debe medir (depende de su función de hashing) para su caso de uso, consulte: channel9.msdn.com/Events/Build/2014/2-661 de 45:48
Richard Critten
44
Ver también boost :: flat_set .
Caleth
1
¿Te refieres a 'contiguo' como en "a medida que se itera el conjunto, los objetos se almacenan en ubicaciones de memoria contiguas" o como en "todos los objetos se almacenan en una gran porción de memoria (pero en orden arbitrario)"?
Pablo H
1
En general, cuando te encuentras preguntando "¿es el contenedor A lo mismo que el contenedor B", la respuesta es "no", de lo contrario solo habría un contenedor A (porque ¿cuál sería el propósito de tener el contenedor B?). Esto no se aplica a los adaptadores de contenedor , por supuesto, pero std::setno es una de esas cosas, que es la clave aquí.
Carreras de ligereza en órbita el

Respuestas:

25

¿Std :: set almacena objetos en memoria contigua como std :: vector?

No hay garantía de que lo haga. También en la práctica, no puede debido a los requisitos del contenedor. Por lo tanto, no, no almacena objetos en la memoria contigua.

No puedo ver por qué no podría usar memoria contigua

Las referencias a elementos del conjunto deben seguir siendo válidas después de su inserción, así como de su borrado (a excepción de las referencias al elemento borrado). Este requisito es incompatible con la memoria contigua.

Hasta donde yo sé, un árbol de búsqueda equilibrado es la única estructura de datos que puede implementar std::set.

eerorika
fuente
Podría crear espacio para los nodos de los árboles a partir de grandes bloques contiguos, en caso de que eso sea lo que quería decir el OP. (Sin embargo, ninguna invalidación de iterador descarta insertcopiar todos los nodos en un nuevo bloque más grande para limitarlo a un solo bloque, en caso de que realloc falle en el lugar o (típico para C ++) el asignador no es compatible con tal realloc.)
Peter Cordes
15

No se excluye explícitamente, aunque ciertas restricciones std::setimpiden el uso de memoria contigua.

Por ejemplo, set::inserttiene complejidad logarítmica mientras que vector::insertrequiere complejidad lineal para barajar sus entradas. Tampoco set::insertinvalida los iteradores. Ambos requisitos no pueden cumplirse con memoria distinguida.

idclev 463035818
fuente