Как элементы в std::unordered_set хранятся в памяти на С++?

Возясь с итераторами с типизированными каламбурами, я наткнулся на возможность сделать

std::vector<int> vec{ 3, 7, 1, 8, 4 };
int* begin_i = (int*)(void*)&*vec.begin();

std::cout << "1st: " << begin_i << " = " << *begin_i << std::endl;
begin_i++;
std::cout << "2nd: " << begin_i << " = " << *begin_i << std::endl;

Затем я попытался сделать то же самое с std::unordered_set:

std::unordered_set<int> set{ 3, 7, 1, 8, 4 };
for (auto& el : set)
{ // Display the order the set is currently in
    std::cout << el << ", ";
}
std::cout << '\n' <<std::endl;

int* begin_i = (int*)(void*)&*set.begin();

std::cout << "1st: " << begin_i << " = " << *begin_i << std::endl;
begin_i++;
std::cout << "2nd: " << begin_i << " = " << *begin_i << std::endl;

Но результат, который я получил, был:

4, 8, 1, 7, 3,

1st: [address] = 4
2nd: [address] = 0

Я предполагаю, что это потому, что элементы неупорядоченного набора расположены в разных частях памяти? Я был сбит с толку, учитывая, что я также напечатал порядок, в котором элементы были сохранены, используя цикл на основе диапазона.

Мой вопрос: как std::unordered_set хранит свои элементы в памяти? Что происходит, когда элемент добавляется в набор? Куда он попадает в памяти и как это отслеживается, если он не хранится в контейнере, похожем на массив, где элементы расположены один за другим?


c++ memory hash pointers type-punning
person Drake Johnson    schedule 12.12.2019    source источник
comment
Внутренне элементы в unordered_set не сортируются в каком-либо определенном порядке, а организованы в сегменты в зависимости от их хеш-значений, чтобы обеспечить быстрый доступ к отдельным элементам непосредственно по их значениям (в среднем с постоянной средней временной сложностью). cplusplus.com/reference/unordered_set/unordered_set   -  person Frederick Zhang    schedule 12.12.2019
comment
Начиная с C++17, элементы неупорядоченного множества должны храниться в вещах. называемые узлы. Стандарт не налагает требований на то, что представляет собой узел, но большинство реализаций будут рассматривать его как узел в связанном списке. Циклы на основе диапазона используют итератор контейнера, а итератор набора проходит по элементам набора, используя любой механизм, требуемый реализацией.   -  person Raymond Chen    schedule 12.12.2019
comment
@FrederickZhang Спасибо. Я уже читал страницу, которая вам понравилась, но все еще не совсем понимаю. Что такое ведра? Как они ускоряют что-либо? Как это выглядит в памяти?   -  person Drake Johnson    schedule 12.12.2019
comment
Детальное обсуждение дизайна неупорядоченного множества слишком широкое для этого сайта. Подробную информацию о том, как обычно реализуются хеш-таблицы, можно найти в книге по структурам данных. Неупорядоченный набор — это частный случай хеш-таблицы без связанного значения.   -  person Raymond Chen    schedule 12.12.2019
comment
Не очень полезным ответом было бы то, что это выбор реализации, как эти данные хранятся. Но общая идея std::unordered_* состоит в том, чтобы использовать хеш-таблицу под капотом, что позволяет осуществлять поиск в постоянном времени. Таким образом, соответствующие итераторы должны иметь мозги, чтобы можно было найти следующий элемент; итератор для std::unordered_* обычно не указатель. Когда вы делаете &*set.begin(), вы вызываете пользовательский operator *, который реализует интеллектуальный итератор, который дает указатель на элемент. Но следующий элемент может быть где угодно.   -  person cmaster - reinstate monica    schedule 12.12.2019

Ответы (3)


arrow_upward
3
arrow_downward

unordered_set реализован как хеш-таблица с использованием внешней цепочки.

В основном это означает, что у вас есть массив связанных списков (которые обычно называются «сегментами»). Таким образом, чтобы добавить элемент в unordered_set, вы начинаете с хеширования нового элемента, который вы вставляете. Затем вы берете этот хэш и уменьшаете его до диапазона текущего размера массива (который может/будет расширяться по мере добавления новых элементов). Затем вы добавляете новый элемент в конец этого связанного списка.

Таким образом, в зависимости от значения, полученного хэшем, два последовательно вставленных элемента могут (и часто будут) вставлены в связанные списки в совершенно разных частях таблицы. Тогда узел в связанном списке обычно будет выделяться динамически, поэтому даже два последовательных элемента в одном и том же связанном списке могут находиться по совершенно не связанным адресам.

Однако, как я отметил в более раннем ответе, в стандарте указано гораздо больше, чем кажется большинству людей. осознать. Как я отметил там, может быть (едва ли) возможно нарушить ожидание и все еще (вроде) соответствовать требованиям стандарта, но даже в лучшем случае сделать это будет довольно сложно. Для большинства практических целей вы можете предположить, что это что-то вроде вектора связанных списков.

Почти то же самое относится и к unordered_multiset — единственное фундаментальное отличие состоит в том, что вы можете иметь несколько элементов с одним и тем же ключом, а не только один элемент с определенным ключом.

Аналогично, есть также unordered_map и unordered_multimap, которые снова очень похожи, за исключением того, что они разделяют сохраняемые вещи на ключ и значение, связанное с этим ключом, и когда они выполняют хеширование, смотрят только на часть ключа, а не на ценностная часть).

person Jerry Coffin    schedule 12.12.2019

arrow_upward
1
arrow_downward

Вместо того, чтобы прямо ответить на вопрос, я хотел бы обратиться к трюку с «каламбуром». (Я взял это в кавычки, потому что предоставленный код не демонстрирует каламбур. Возможно, код был соответствующим образом упрощен для этого вопроса. В любом случае *vec.begin() дает int, поэтому &*vec.begin() является int*. Дальнейшее приведение к void*, а затем обратно к int* является сетью без операции.)

Свойство, которое использует ваш код, это

*(begin_i       + 1) == *(vec.begin() + 1)  // Using the initial value of begin_i
*(&*vec.begin() + 1) == *(vec.begin() + 1)  // Without using an intermediary

Это свойство непрерывного итератора, связанного с непрерывный контейнер. Это контейнеры, которые хранят свои элементы в соседних ячейках памяти. Непрерывными контейнерами в стандартной библиотеке являются string, array и vector; это единственные стандартные контейнеры, для которых ваш трюк гарантированно сработает. Попробовать это на deque, вероятно, сначала покажется, что это сработает, но попытка потерпит неудачу, если к &*begin() будет добавлено достаточное количество. Другие контейнеры имеют тенденцию к динамическому размещению элементов по отдельности, поэтому между адресами элементов не должно быть никакой связи; элементы связаны между собой указателями, а не позицией/индексом.

Чтобы не игнорировать заданный вопрос:

Неупорядоченный набор просто необходим для организации элементов в сегменты. Нет никаких требований к тому, как это сделать, кроме требования, чтобы все элементы с одинаковым значением хеш-функции помещались в одно и то же ведро. (Это не означает, что все элементы в одном сегменте имеют одинаковое хеш-значение.) На практике каждый сегмент, вероятно, реализуется как list, а контейнер сегментов, вероятно, представляет собой vector просто потому, что повторное использование кода — это круто. В то же время это деталь реализации, так что может очень сильно от компилятора к компилятору, и даже от версии компилятора к версии компилятора. Нет никаких гарантий.

person JaMiT    schedule 12.12.2019

arrow_upward
-1
arrow_downward

То, как std::unordered_set хранит свою память, определяется реализацией. Стандарту все равно, пока он удовлетворяет требованиям.

В версии VS он хранит их внутри std::list (быстрый доступ обеспечивается за счет создания и управления дополнительными данными) - поэтому каждый элемент также имеет указатели на prev, а next хранится через new (по крайней мере, это то, что я помню из std::list).

person ALX23z    schedule 12.12.2019
comment
Начиная с C++17, элементы неупорядоченного набора должны храниться в узлах (которые возвращаются методом extract). - person Raymond Chen; 12.12.2019
comment
@RaymondChen проблема в том, что тип не указан. Вы можете получить его, но не можете использовать его переносным способом. Какой смысл обращаться к ним, если это так? - person ALX23z; 12.12.2019
comment
Вы можете вставить узел в другую коллекцию. Это в значительной степени единственное, что вы можете сделать с ним, но это что-то. - person Raymond Chen; 12.12.2019