Является ли порядок элементов в hash_map/unordered_map стабильным?

Гарантируется ли, что когда hash_map/unordered_map загружается с одними и теми же элементами, они будут иметь одинаковый порядок при повторении? По сути, у меня есть хэш-карта, которую я загружаю из файла и из которой я периодически передаю ограниченное количество элементов в подпрограмму, после чего освобождаю хэш-карту. После того, как элементы израсходованы, я повторно загружаю тот же файл в хэш-карту и хочу получить следующую партию элементов после точки, на которой я остановился в предыдущий раз. Точка, в которой я останавливаюсь, определяется ключом.


c++ hashmap stl unordered-map
person Alexander Vassilev    schedule 29.11.2012    source источник
comment
Не то, что я знаю, хотя это вероятно (если только ваш ключ не основан на значении указателя), потому что ни одна известная мне реализация не использует случайность.   -  person Matthieu M.    schedule 29.11.2012
comment
Я использую std::string в качестве ключа   -  person Alexander Vassilev    schedule 29.11.2012

Ответы (2)


arrow_upward
2
arrow_downward

Технически нет, не гарантируется их расположение в определенном порядке.

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

рассмотреть возможность

std::string name;
std::string value;

std::unordered_map <std::string, std::string> map1;
std::unordered_map <std::string, std::string> map2;

while (read_pair (name, value))
{
    map1[name] = value;
    map2[name] = value;
}

вы можете разумно ожидать, что пары имя-значение в map1 и map2 идут в одном и том же порядке.

person Community    schedule 29.11.2012
comment
Да, это моя точка зрения - меня не интересует сам порядок, но будет ли он таким же при следующей загрузке хэш-карты. Спасибо за ответ - person Alexander Vassilev; 29.11.2012
comment
Помимо того, что в целом полагаться на поведение, которое не гарантировано, — плохая идея, я думаю, важно отметить, что это зависит от того факта, что порядок вставки одинаков на обеих картах, что не обязательно сохраняться при перезагрузке файлов (поскольку порядок итерации, скорее всего, не будет соответствовать исходному порядку вставки). - person John Bartholomew; 29.11.2012
comment
@John Bartholomew: я не понял смысла порядка вставки - я вставляю элементы при анализе файла, поэтому всегда одно и то же. - person Alexander Vassilev; 29.11.2012
comment
@AlexanderVassilev: Джон, вероятно, думает о самом первом разе, когда вы вставляете элементы, до того, как карта будет сохранена на диск. Порядок на диске не будет соответствовать порядку, в котором они были вставлены в первый раз, даже если все детерминировано. Я бы сказал, что полное описание вашего вопроса ясно дает понять, что вы не заботитесь об этом в первый раз, но вопрос заголовка не исключает его, как и ваше первое предложение: когда hash_map/unordered_map загружается с теми же элементами а не одни и те же предметы в том же порядке. - person Steve Jessop; 29.11.2012
comment
Ну, я не сохраняю карту на диск. Я только загружаю его, файл не генерируется с карты. - person Alexander Vassilev; 29.11.2012

arrow_upward
2
arrow_downward

Нет, вы не можете безопасно сделать это. Во-первых, это не гарантируется стандартом, но даже если вы игнорируете стандарт и смотрите на реальные реализации, это плохая идея.

Большинство структур хеш-таблиц не являются независимыми от истории. То есть: состояние хеш-таблицы зависит не только от того, какие элементы в ней содержатся, но и от того, в каком порядке они были вставлены.

Вот конкретный пример:

#include <unordered_map>
#include <string>
#include <iostream>

static const char* const NAMES[] = {
    "joe",
    "bob",
    "alexander",
    "warren",
    "paul",
    "michael",
    "george",
    "david",
    "peter"
};
static const int NAME_COUNT = sizeof(NAMES)/sizeof(NAMES[0]);

static void print_umap(const std::unordered_map<std::string, int>& m) {
    for (const auto& item : m) {
        std::cout << "  " << item.first << "\n";
    }
}

int main(void) {
    std::unordered_map<std::string, int> a;
    std::unordered_map<std::string, int> b;
    std::unordered_map<std::string, int> c;

    for (int i = 0; i < NAME_COUNT; ++i) {
        a[NAMES[i]] = 0;
        b[NAMES[NAME_COUNT - 1 - i]] = 0;
    }

    for (const auto& item : a) {
        c[item.first] = 0;
    }

    std::cout << "a:\n";
    print_umap(a);
    std::cout << "\n\nb:\n";
    print_umap(b);
    std::cout << "\n\nc:\n";
    print_umap(c);
    return 0;
}

Когда я создаю это, используя clang и libc++ реализации стандартной библиотеки C++, я получаю следующий вывод:

a:
  peter
  george
  michael
  david
  paul
  bob
  warren
  alexander
  joe


b:
  joe
  alexander
  bob
  warren
  david
  paul
  michael
  george
  peter


c:
  joe
  alexander
  warren
  bob
  paul
  david
  michael
  george
  peter

Обратите внимание, что порядок в каждом случае разный. В этом нет ничего необычного для хеш-таблиц.

person John Bartholomew    schedule 29.11.2012
comment
Я согласен с этим, но в моем случае порядок вставки каждый раз гарантированно будет одинаковым. - person Alexander Vassilev; 29.11.2012