Хранит ли std :: set объекты непрерывно в памяти?

Хранит ли std::setобъекты в непрерывной памяти как std::vector?

Я не смог найти это в Интернете, cppreference не упоминает подробности о распределении памяти. Но я не понимаю, почему он не может использовать непрерывную память, поэтому мой вопрос.

c++ set stdset mfnx
источник

Прочитайте set::insertтребования: en.cppreference.com/w/cpp/container/set/insert "... Никакие итераторы или ссылки не признаны недействительными ....", поэтому он не может перераспределить, когда ему нужно расширить, как это std::vectorделает.

Ричард Криттен

Производительность: вам нужно измерить (зависит от функции хеширования) для использования случая смотрите: channel9.msdn.com/Events/Build/2014/2-661 от 45:48

Ричард Critten

Смотрите также boost :: flat_set .

Caleth

Вы имеете в виду «непрерывный», как в «как итерация набора, объекты хранятся в смежных местах памяти», или как «все объекты хранятся в одном большом фрагменте памяти (но в произвольном порядке)»?

Пабло Х

Как правило, когда вы задаетесь вопросом: «Является ли контейнер A тем же, что и контейнер B», ответом является «нет», в противном случае был бы только контейнер A (потому что для чего нужен контейнер B?). Это не относится к контейнерным адаптерам, конечно, но std::setэто не одна из тех вещей, которая является ключевой здесь.

Гонки легкости на орбите

Ответы:

Хранит ли std :: set объекты в непрерывной памяти, такие как std :: vector?

Нет никаких гарантий, что это так. Также на практике это невозможно из-за требований контейнера. Поэтому нет, он не хранит объекты в непрерывной памяти.

Я не могу понять, почему он не мог использовать непрерывную память

Ссылки на элементы набора должны оставаться действительными при вставке в него, а также при удалении (за исключением ссылок на стертый элемент). Это требование несовместимо с непрерывной памятью.

Насколько я знаю, сбалансированное дерево поиска является единственной структурой данных, которую можно реализовать std::set.

eerorika
источник

Это может вырезать пространство для узлов дерева из больших смежных кусков, в случае, если это то, что имел в виду OP. (Но никакая аннулирование итератора не исключает insertкопирования всех узлов в новый больший блок, чтобы ограничить его только одним блоком, в случае сбоя realloc на месте или (типично для C ++) распределитель не поддерживает такой realloc.)

Питер Корд

Это не исключено явно, хотя определенные ограничения std::setне позволяют использовать непрерывную память.

Например, set::insertимеет логарифмическую сложность, в то время как vector::insertтребует линейной сложности, чтобы перемешать свои записи. Также set::insertне делает недействительными итераторы. Оба требования не могут быть реализованы с постоянной памятью.

idclev 463035818
источник