end () итератор в ассоциативных контейнерах

Question

Работает ли этот код на всех стандартных совместимых компиляторах C ++ (он работает с g ++)?Почему (пожалуйста, дайте ссылку на c ++ 11, если это возможно)?Как насчет std :: unordered_map и ассоциативных контейнеров в целом?

std::map<std::string, std::string> map;

std::map<std::string, std::string>::iterator i(map.end());

map.insert({"bla", ""});
map.insert({"hah", ""});

assert(map.end() == i);

Answer 1

Похоже, вы ищете цитаты из стандарта, касающиеся признания недействительным интегратора:

Для set, multiset, map and multimap

Элементы вставки не должны влиять на действительность итераторов и ссылки наконтейнер, и члены стирания должны сделать недействительными только итераторы и ссылки на стертые элементы.

Для unordered_set, unordered_map, unordered_multiset, and unordered_multimap

Элементы вставки не должны влиять на действительность итераторов, если(N + n)

Таким образом, для map вставка не делает недействительным итератор end, однако для unordered_map это произойдет, если число элементов, добавленных к существующему числу элементов, превысит bucket_count * max_load_factor.

Answer 2

Для карты да - практически ничего, кроме удаления упомянутого объекта, делает недействительным итератор в карте.

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

Это, правда, не гарантировано. В частности, ваши вставки могут вызвать перефразирование, [Правка: здесь я более или менее предполагаю, что ваши две вставки предназначены в качестве заполнителя для некоторого произвольного числа вставок. Вы можете выяснить, происходит ли повторное хеширование для определенного коэффициента загрузки, количества вставок и т. Д., Но вы, как правило, этого не хотите - в зависимости от того, что это приводит к хрупкому коду], а перефразировка делает недействительными итераторы (§23.2.5 / 8). Хотя (как упомянуто выше) итератор, возвращаемый end(), часто является «специальным», стандарт не требует этого, поэтому после вставок то, что вы ранее получили из end, может быть недействительным, поэтому практически ничего не требуется для это (включая сравнение, равное чему-либо, в частности).

Answer 3

Из стандартного раздела C ++ 03 23.1.2 Ассоциативные контейнеры [lib.associative.reqmts] , точка 8 состояния:

Элементы вставки не должны влиять на действительность итераторов и ссылок на контейнер, а элементы стирания должны сделать недействительными только итераторы и ссылки на стертые элементы.

Из стандартного раздела C ++ 11 23.2.4 Ассоциативные контейнеры [ассоциативные.reqmts] , точка 9 состояния:

Элементы вставки не должны влиять на действительность итераторов и ссылок на контейнер, а также на удаление члены должны делать недействительными только итераторы и ссылки на стертые элементы.

Исходя из этого, assert() в размещенном коде будет true.

EDIT:

Эти цитаты не верны для unordered контейнеров: см. Ответ от Джесси .

Answer 4

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

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

Answer 5

Код использует расширенные списки инициализаторов здесь:

map.insert({"bla", ""}); // the {"bla", ""}

Это функция C ++ 11, следовательно, не будет работать на компиляторах не-C ++ 11.

Работа над компиляторами:

• GCC 4.4.1 и все более поздние версии

Не работает:

• Digital Mars C ++
• Borland C ++ (не совсем обычный, но все же проверенный)
• Visual C ++
• Очевидно, что большинство компиляторов, которые не поддерживают C ++ 11