Как для std::map, так и для std::tr1::unordered_map я вижу из стандарта, что:
Ссылки на элементы в контейнере unordered_map остаются действительными во всех случаях, даже после перефразирования.
Как они это делают (с точки зрения реализации)? Сохраняют ли они все записи в виде связанного списка, а затем хеш-таблица просто хранит указатели на элементы?
Да, связанные списки задействованы, хотя и не совсем так, как вы предлагаете.
Стандарт 2011 года гласит (23.2.5, пункт 8): «Элементы неупорядоченного ассоциативного контейнера организованы в сегменты. Ключи с одинаковым хэш-кодом появляются в одном сегменте».
Внутри каждой корзины элементы находятся в связанном списке (отдельный список для каждой корзины, а не один большой список для всего контейнера). При повторном хешировании контейнера элементы будут назначены новым сегментам, но указатели на каждый элемент останутся действительными. Связный список в каждом новом сегменте собирается из указателей на существующие элементы, которые попадают в этот сегмент.
Итераторы аннулируются повторным хешированием, поскольку итератору необходимо удерживать указатели как на элемент, так и на его корзину (чтобы его можно было перейти от последнего элемента одной корзины к первому элементу следующей). Указатель элемента остается действительным, поэтому существующие указатели и ссылки на элемент по-прежнему действительны, но указатель сегмента становится недействительным из-за повторного хеширования, поэтому итератор нельзя использовать.
(Именно поэтому неупорядоченные контейнеры поддерживают только прямые итераторы, а не двунаправленные итераторы, поддерживаемые упорядоченными ассоциативными контейнерами. Элементы каждого сегмента находятся в односвязном списке, поэтому вы не можете пройти через них назад.)
