Подтвердить что ты не робот

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

Что я имею в виду - мы знаем, что элементы 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 за ответ.

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

Ответ 2

Это гарантируется ассоциативными требованиями к контейнерам в стандарте С++. Например. см. 23.2.4/10 в С++ 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.

Ответ 3

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

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

В С++, однако, это не так:

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

Итак, чтобы уточнить гарантии при заказе.

В С++ 03:

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

В С++ 11:

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

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

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

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

Ответ 4

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

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

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

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

Ответ 5

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

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

Ответ 6

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