Стандарт С++ 11 требует, чтобы две итерации через константу unordered_container посещали элементы в том же порядке?

for (auto&& i : unordered_container)
{ /* ... */ }

for (auto&& i : unordered_container)
{ /* .. */ }

Требуется ли стандарту, чтобы обе эти петли посещали элементы в одном порядке (при условии, что контейнер немодифицирован)?

Мой анализ этого вопроса...

Я прочитал стандарт и, насколько я могу сказать, ответ "нет"...

Поскольку итераторы контейнеров пересылаются вперед, существует язык, для которого требуется a==b подразумевать, что ++a==++b для форвардных итераторов. Это означает, что две итерации пройдут один и тот же путь, если оба они начнут в одном и том же месте. Это сводит вопрос к другому вопросу о том, требует ли стандарт container.begin() == container.begin(). Я не мог найти какой-либо язык, требующий этого.

Ответ 1

Контейнеры должны реализовать operator==(). То есть мы можем сделать:

container c;
c == c;

Это отношение должно работать так же, как:

std::distance(a.begin(), a.end()) == std::distance(b.begin(), b.end()) &&
std::equal(a.begin(), a.end(), b.begin());

Важная часть здесь - вызов std::equal(). Для этого вызова требуется, чтобы два независимых вызова container.begin() выдавали одну и ту же последовательность значений. Если это не так, то c == c будет ложным, и это не имеет никакого смысла, потому что == - отношение эквивалентности.

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

Цитирование:

С++ 2011 Таблица 96 - Требования к контейнеру

Ответ 2

Я думаю, что заключение @Sharth верное, но (для любого, кто заботится о более новых стандартах) уже устарел (и, возможно, никогда не отражал реальность - см. ниже).

Более свежие черновики стандарта (например, n3797) изменили требования, очевидно, намеренно устраняя требование упорядочения. В частности, он говорит (§23.2.5/12):

Два неупорядоченных контейнера a и b сравнивают одинаковые значения, если a.size() == b.size() и для каждой группы эквивалентных ключей [Ea1, Ea2), полученных из a.equal_range(Ea1), существует группа с эквивалентными ключами [ Eb1, Eb2), полученный из b.equal_range(Ea1), так что distance(Ea1, Ea2) == distance(Eb1, Eb2) и is_permutation(Ea1, Ea2, Eb1) возвращает true.

У меня также относительно низкая уверенность в том, что реализации действительно соответствуют требованиям стандарта 2011 года. В частности, неупорядоченные контейнеры обычно реализуются как хеш-таблицы со связанными списками для разрешения конфликтов. Поскольку ожидается, что эти связанные списки будут короткими, они не обязательно сортируются (особенно, поскольку элементы, хранящиеся в неупорядоченных контейнерах, не обязаны определять операции, которые будут использоваться для сортировки, например operator<). В этом случае довольно сложно использовать связанные списки для хранения одних и тех же элементов, но в порядке, зависящем от порядка, в котором они были вставлены.

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

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

Итак, пока вы имеете дело с одним и тем же контейнером, неизмененный, в зависимости от итерации в том же порядке, может быть безопасным. Два контейнера, которые имеют одинаковое содержимое, могут не так хорошо работать (и даже в тех случаях, когда они претендуют на реализацию на С++ 11, вы, вероятно, не можете ожидать, что он будет отвечать более жестким требованиям, чем содержат более новые черновики).

Ответ 3

Я читал о стандарте, что это не гарантируется. 23.2.5, пункт 6, гласит:

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

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

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

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

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

Ответ 4

Неупорядоченные контейнеры возвращают итераторы вперед (которые определены в § 24.2.5), и те имеют это свойство: a == b implies ++a == ++b. Это, по-видимому, так долго, что unordered_container.begin() == unordered_container.begin() истинно, что порядок обхода будет одинаковым.

Мне не удалось найти какой-либо язык, требующий unordered_container.begin() == unordered_container.begin(), который привел меня к условному ответу "нет", порядок обхода не обязательно должен быть одним и тем же.