Est-ce que std :: set stocke les objets de manière contiguë en mémoire?

16

Est-ce que std::setstocker des objets dans une mémoire contiguë comme std::vector?

Je n'ai pas pu trouver cela sur le web, cppreference ne mentionne pas de détails sur l'allocation de mémoire. Mais je ne vois pas pourquoi il ne pouvait pas utiliser de mémoire contiguë, d'où ma question.

c++ set stdset mfnx
la source
5
Lisez les set::insertexigences: en.cppreference.com/w/cpp/container/set/insert "... Aucun itérateur ou référence n'est invalidé ...." donc il ne peut pas se réallouer quand il a besoin de se développer comme il le std::vectorfait.
Richard Critten
Performance: vous devez mesurer (dépend de votre fonction de hachage) pour votre cas d'utilisation voir: channel9.msdn.com/Events/Build/2014/2-661 de 45:48
Richard Critten
4
Voir aussi boost :: flat_set .
Caleth
1
Voulez-vous dire «contigu» comme dans «lorsque l'ensemble est itéré, les objets sont stockés dans des emplacements de mémoire contigus», ou comme dans «tous les objets sont stockés dans un seul gros morceau de mémoire (mais dans un ordre arbitraire)»?
Pablo H
1
Généralement, lorsque vous vous demandez "le conteneur A est-il le même que le conteneur B", la réponse est "non", sinon il n'y aurait que le conteneur A (car quel serait le but d'avoir le conteneur B?). Cela ne s'applique pas aux adaptateurs de conteneurs bien sûr, mais ce std::setn'est pas une de ces choses, qui est la clé ici.
Courses de légèreté en orbite le

Réponses:

25

Est-ce que std :: set stocke des objets dans une mémoire contiguë comme std :: vector?

Il n'y a aucune garantie que ce soit le cas. En pratique également, cela ne peut pas en raison des exigences du conteneur. Par conséquent non, il ne stocke pas d'objets dans la mémoire contiguë.

Je ne vois pas pourquoi il ne pouvait pas utiliser de mémoire contiguë

Les références aux éléments de l'ensemble doivent rester valides lors de leur insertion ainsi que de leur effacement (sauf pour les références à l'élément effacé). Cette exigence est incompatible avec la mémoire contiguë.

Pour autant que je sache, un arbre de recherche équilibré est la seule structure de données qui peut être implémentée std::set.

eerorika
la source
Il pourrait créer de l'espace pour les nœuds d'arbre dans de gros morceaux contigus, au cas où cela signifierait l'OP. (Mais aucune invalidation d'itérateur n'interdit de insertcopier tous les nœuds dans un nouveau bloc plus grand pour le limiter à un seul bloc, au cas où le réallocation sur place échouerait ou (typique pour C ++) l'allocateur ne prend pas en charge un tel réallocation.)
Peter Cordes
15

Il n'est pas exclu explicitement, bien que certaines contraintes std::setrendent impossible l'utilisation de la mémoire contiguë.

Par exemple, set::inserta une complexité logarithmique tout en vector::insertnécessitant une complexité linéaire pour mélanger ses entrées. N'invalide set::insertpas non plus les itérateurs. Les deux exigences ne peuvent pas être réalisées avec une mémoire contingente.

idclev 463035818
la source