Неупорядоченная итерация карты по значениям

У меня странная проблема, я не знаю, то ли я пропустил чтение документации, то ли мой компьютер делает что-то странное.

У меня есть unordered_map. Я хочу перебирать ведра unordered_map в порядке ведер. Эта часть важна, так как мне нужно, чтобы доступ был относительно случайным. Я искал cplusplus.com и нашел это. Код выглядит следующим образом:

// unordered_map::bucket
#include <iostream>
#include <string>
#include <unordered_map>
int main ()
{
  std::unordered_map<std::string,std::string> mymap = {
    {"us","United States"},
    {"uk","United Kingdom"},
    {"fr","France"},
    {"de","Germany"}
  };

  for (auto& x: mymap) {
    std::cout << "Element [" << x.first << ":" << x.second << "]";
    std::cout << " is in bucket #" << mymap.bucket (x.first) << std::endl;
  }

  return 0;
}

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

Element [us:United States] is in bucket #1
Element [de:Germany] is in bucket #2
Element [fr:France] is in bucket #2
Element [uk:United Kingdom] is in bucket #4

Однако вывод, который я получаю, вместо этого сортируется по типу значения, что странно

Element [de:Germany] is in bucket #2
Element [fr:France] is in bucket #3
Element [uk:United Kingdom] is in bucket #1
Element [us:United States] is in bucket #1

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

for ( unsigned int i = 0; i < b.bucket_count(); ++i) {

    for ( hash_table::const_local_iterator image_iterator = 
    b.begin(i);image_iterator!= b.end(i); ++image_iterator ){

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

Любая помощь будет оценена по достоинству. Я не могу понять это!

[EDIT] С моим кодом моя unordered_map на самом деле является unordered_map, где точка — это простой класс, который имеет только две переменные-члены и не имеет вспомогательных функций.

Когда я запускаю цикл выше на своей карте, вот мой вывод. Я связал текстовый файл, так как он довольно длинный здесь Еще больше меня смущает то, что в моем классе Point нет операторов сравнения. Может ли это быть причиной моего заказа на вставку?


person Michael Honaker    schedule 22.11.2018    source источник
comment
Обратите внимание, что ваш вывод также сортируется по типу ключа, а также последовательно по корзине, но начинается с #2 с арифметикой по модулю.   -  person François Andrieux    schedule 22.11.2018
comment
Насколько мне известно, порядок элементов при переборе std::unordered_map не указан. Я понимаю, почему вы можете ожидать, что он будет заказывать их по ведрам, но я не знаю ничего, что гарантировало бы это. Очевидно, это не то, что здесь происходит.   -  person François Andrieux    schedule 22.11.2018
comment
Как вы определили идентификаторы сегментов для ожидаемого результата?   -  person François Andrieux    schedule 22.11.2018
comment
@FrançoisAndrieux Я переключил ключи, чтобы они были не в порядке, но они все равно выводились так же. Я также смущен тем, почему я получил другой результат, чем документация, которую я нашел.   -  person Michael Honaker    schedule 22.11.2018
comment
Непонятно, о какой документации вы говорите. Порядок повторения unordered_map не указан, поэтому не должен указываться в какой-либо документации.   -  person François Andrieux    schedule 22.11.2018
comment
Где вы нашли документацию, определяющую порядок? На моей платформе вывод отличается от вашего вывода.   -  person Jabberwocky    schedule 22.11.2018
comment
Это просто совпадение. Я могу воспроизвести с указанными вами ключами, но измените их на "a", "b", "c", d и вывод больше не сортируется (либо по ключу, либо по сегменту). Неупорядоченная карта неупорядочена.   -  person Igor Tandetnik    schedule 22.11.2018
comment
Какую платформу и какой компилятор вы используете? Возможно, есть разница в реализации.   -  person Darkproduct    schedule 22.11.2018
comment
@FrançoisAndrieux Я имею в виду несколько веб-сайтов / руководств, на которых они расположены в порядке ведра. Вот несколько примеров здесь и здесь и здесь. Даже если это не так, как я могу перебирать ведра в одном цикле for   -  person Michael Honaker    schedule 22.11.2018
comment
@IgorTandetnik Это был просто пример. Когда я запускаю свой на гораздо большем наборе и вывожу значения, они идут по порядку. Единственная разница в том, что моя unordered_map использует тип ключа с плавающей запятой.   -  person Michael Honaker    schedule 22.11.2018
comment
@Darkproduct g++ 7.3.0 без дополнительных команд, так что просто g++ main.cpp -o main.out   -  person Michael Honaker    schedule 22.11.2018
comment
@MichaelHonaker Это легко возможно, потому что реализация стандартной библиотеки может использовать функцию идентификации в качестве хэша для целых чисел (и, возможно, делает что-то подобное для чисел с плавающей запятой). Неупорядоченная карта от int к чему-то будет иметь сегменты, отсортированные по ключу, если std::hash<int> — это просто функция идентификации.   -  person Max Langhof    schedule 22.11.2018
comment
Не было бы намного проще просто использовать что-то вроде (это)[stackoverflow.com/questions/158836/random-element-in-a-map]   -  person Darkproduct    schedule 22.11.2018
comment
@MichaelHonaker Я не вижу ни на одном из этих связанных сайтов ничего, что требовало бы порядка вывода. Это примерные результаты, и результаты могут отличаться. Этот даже выходит из способ явно сказать ПРИМЕЧАНИЕ: для unordered_map выходные строки могут быть в любом порядке.   -  person François Andrieux    schedule 22.11.2018
comment
@FrançoisAndrieux посмотрите на мое редактирование исходного вопроса. В большом наборе данных мой находится в определенном порядке, который меня смущает.   -  person Michael Honaker    schedule 22.11.2018
comment
@Darkproduct Моя единственная проблема заключается в том, что он должен быть основан на процентах, т. Е. Если он печатает 1% от 10000 элементов, он должен распечатать только 100 значений. Используя random, есть шанс, что он может распечатать все 10000   -  person Michael Honaker    schedule 22.11.2018
comment
@MichaelHonaker Я не уверен, что полностью понимаю ваше редактирование, но вам нужно только сравнение равенства и специализация std::hash, которая будет использоваться в качестве ключа. Он никогда не использует operator< на клавишах.   -  person François Andrieux    schedule 22.11.2018
comment
@MichaelHonaker Суть в том, что вы не можете полагаться на порядок элементов unordered_map. Порядок не указан, но это не означает случайный. Таким образом, даже странно хорошо упорядоченная последовательность может быть законным порядком.   -  person François Andrieux    schedule 22.11.2018
comment
@FrançoisAndrieux извините за путаницу. если вы посмотрите на файл, который я связал, выходные данные отсортированы по значениям, хотя мой класс значений не имеет никакого сравнения, то есть мой компьютер не может даже узнать, какой объект Point больше другого. Что меня смущает, так это то, что он не выводится ни в каком порядке, кроме сортировки по значению. Почему мой компьютер переключается с сегмента 51534 на сегмент 536493? Это не имеет смысла   -  person Michael Honaker    schedule 22.11.2018
comment
@MichaelHonaker Тогда кажется, что все, что хеширует ваши ключи, создает хэши, которые сортируются в том же порядке, в котором вы ожидаете, что ваши ключи будут отсортированы. Редактировать: поскольку ваш тип ключа, по-видимому, является типом, созданным пользователем, посмотрите на предоставленный std::hash, и вы, вероятно, поймете, почему ваши хэши ключей отсортированы.   -  person François Andrieux    schedule 22.11.2018
comment
@FrançoisAndrieux Я отредактировал свой комментарий. Уточняющий вопрос: должен ли итератор выполнять итерацию от корзины 1 до корзины 10000. Потому что моя программа прыгает по корзинам без видимой причины   -  person Michael Honaker    schedule 22.11.2018
comment
@MichaelHonaker Есть очень много способов сказать, что порядок не указан. Если вы не найдете документацию, в которой прямо говорится, что корзины будут повторяться последовательно, то любые ожидания, что это так, необоснованны. Неудивительно, что программа прыгает по корзинам, она не должна быть последовательной. Unspecified означает, что не указано, чтобы быть последовательным. В вашем случае похоже, что итерация выполняется в порядке ключа, который может выбрать реализация,   -  person François Andrieux    schedule 22.11.2018


Ответы (1)


В std::unordered_map ведро для конкретного элемента полностью определяется хеш-значением, вычисленным для ключа, std::unordered_map используется в качестве соответствующей специализации std::hash в качестве хэш-функции по умолчанию, которая определяется реализацией и даже не гарантируется, что она будет одинаковой при выполнении различных программ. . см. std::hash.

Как сказал @François Andrieux в разделе комментариев, порядок итерации std::unordered_map не указан, поэтому вы не можете ожидать одинакового поведения итерации на всех машинах, например, вывод на моем компьютере:

Element [de:Germany] is in bucket #0
Element [fr:France] is in bucket #3
Element [uk:United Kingdom] is in bucket #4
Element [us:United States] is in bucket #4
person Jans    schedule 22.11.2018
comment
Посмотрите на мою правку. Меня смущает, почему он упорядочен таким образом, хотя оператора сравнения нет. - person Michael Honaker; 22.11.2018
comment
Верно, .. но вы не можете ожидать, что угадаете, что это такое, пока не попробуете ... это то, что я имел в виду, исправлено ... спасибо - person Jans; 22.11.2018