Известен ли порядок итерации через std :: map (и гарантируется стандартом)? - PullRequest
Новая
       19

Известен ли порядок итерации через std :: map (и гарантируется стандартом)?

143 голосов
/ 04 октября 2011

Я имею в виду, что мы знаем, что элементы std::map отсортированы по ключам.Итак, допустим, ключи являются целыми числами.Если я выполняю итерацию с std::map::begin() до std::map::end() с использованием for, гарантирует ли стандарт, что я буду последовательно выполнять итерации по элементам с ключами, отсортированными по возрастанию?

Пример: 

std::map<int, int> map_;
map_[1] = 2;
map_[2] = 3;
map_[3] = 4;
for( std::map<int, int>::iterator iter = map_.begin();
     iter != map_.end();
     ++iter )
{
    std::cout << iter->second;
}

Гарантируется ли печать 234 или это определяется реализацией?

Реальная причина: у меня есть std::map с int ключами.В очень редких ситуациях я хотел бы пройтись по всем элементам, причем ключ больше конкретного значения int.Да, похоже, что std::vector будет лучшим выбором, но обратите внимание на мои "очень редкие ситуации".

EDIT : я знаю, что элементы std::mapотсортированы .. нет необходимости указывать на это (для большинства ответов здесь).Я даже написал это в своем вопросе.
Я спрашивал об итераторах и порядке, когда я перебираю контейнер.Спасибо @Kerrek SB за ответ.

Ответы [ 6 ]

159 голосов
/ 04 октября 2011

Да, это гарантировано.Более того, *begin() дает вам наименьший и *rbegin() наибольший элемент, определяемый оператором сравнения, и два ключевых значения a и b, для которых выражение !compare(a,b) && !compare(b,a) истинно, считаются равными.Функция сравнения по умолчанию - std::less<K>.

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

41 голосов
/ 04 октября 2011

Это гарантировано ассоциативными требованиями к контейнерам в стандарте C ++. Например. см. 23.2.4 / 10 в C ++ 11: 

The fundamental property of iterators of associative containers is that they
iterate through the containers in the non-descending order of keys where
non-descending is defined by the comparison that was used to construct them.
For any two dereferenceable iterators i and j such that distance from i to j is
positive,
  value_comp(*j, *i) == false

и 23.2.4 / 11 

For associative containers with unique keys the stronger condition holds,
  value_comp(*i, *j) != false.
27 голосов
/ 04 октября 2011

Я думаю, что в структурах данных есть путаница.

В большинстве языков map - это просто AssociativeContainer: он сопоставляет ключ со значением.В «более новых» языках это обычно достигается с помощью хэш-карты, поэтому порядок не гарантируется.

Однако в C ++ это не так:

  • std::mapявляется отсортированным ассоциативным контейнером
  • std::unordered_map является ассоциативным контейнером на основе хеш-таблицы, введенным в C ++ 11

Итак, для пояснениягарантии на заказ.

На С ++ 03:

  • std::set, std::multiset, std::map и std::multimap гарантированно будутПри заказе в соответствии с ключами (и предоставленным критерием)
  • в std::multiset и std::multimap, стандарт не накладывает никаких гарантий заказа на эквивалентные элементы (то есть те, которые сравниваются равными)

В C ++ 11:

  • std::set, std::multiset, std::map и std::multimap гарантированно заказываются в соответствии с ключами (и предоставленный критерий)
  • в std::multiset и std::multimap, Стандарт налагает , что эквивалентные элементы (те, которые сравниваются равными) упорядочены согласно ихПорядок вставки (сначала вставляется первым)
  • std::unordered_* Контейнеры, как следует из названия, не заказаны.В частности, порядок элементов может измениться при изменении контейнера (после вставки / удаления).

Когда в стандарте говорится, что элементы упорядочены таким образом, это означает, чточто:

  • при итерации вы видите элементы в порядке, определенном
  • при итерации в обратном порядке, вы видите элементы в обратном порядке

Я надеюсь, что это устранит любую путаницу.

4 голосов
/ 04 октября 2011

Гарантируется ли печать 234 или определена ее реализация?

Да, std::map - отсортированный контейнер, заказанный Key с поставляемым Comparator.Так что это гарантировано.

Я бы хотел пройти итерацию по всем элементам, причем ключ больше конкретного значения int.

Это, безусловно, возможно.*

3 голосов
/ 04 октября 2011

Да ... элементы в std::map имеют строгий слабый порядок, что означает, что элементы будут состоять из набора (т. Е. Не будет повторений «равных» ключей) и равенствапутем тестирования на любых двух ключах A и B определяется, что если ключ A не меньше, чем ключ B, а B не меньше, чем A, то ключ A равен ключу B.

При этомвы не можете правильно отсортировать элементы std::map, если слабый порядок для этого типа неоднозначен (в вашем случае, когда вы используете целые числа в качестве типа ключа, это не проблема).Вы должны быть в состоянии определить операцию, которая определяет общий порядок для типа, который вы используете для ключей в std::map, в противном случае у вас будет только частичный порядок для ваших элементов или poset, у которого есть свойство, где A может небыть сравнимым с B. В этом сценарии обычно происходит то, что вы сможете вставить пары ключ / значение, но у вас могут получиться дублирующие пары ключ / значение, если вы выполните итерацию по всей карте и / или обнаружите«отсутствующие» пары ключ / значение при попытке выполнить std::map::find() определенной пары ключ / значение на карте.

0 голосов
/ 11 мая 2019

begin () может дать наименьший элемент.Но это зависит от реализации.Это указано в стандарте C ++?Если нет, то делать такое предположение опасно.

...