Порядок заказа std :: map

Question

Для std::map могу ли я всегда доверять begin(), чтобы вернуть элемент с наименьшим ключом в соответствии с операторами сравнения для типа при повторении?

Другими словами ...

Будет std::map<Key, SomeClass>::iterator smallestKeyIt = someMap.begin(); дать мне пару в карте с наименьшим ключом?

Является ли это заказом, гарантированным для std::map, или я могу его каким-то образом настроить? Я понимаю, что структура подстилающего дерева сохраняется при выполнении операций, таких как добавление и удаление элементов.

Answer 1

Могу ли я всегда доверять begin(), чтобы вернуть элемент с наименьшим ключом в соответствии с операторами сравнения для типа?

Да.

Является ли это заказом, гарантируемым для std :: map, или я могу его каким-то образом настроить?

Да. И вы можете настроить поведение сравнения, указав компаратор. (По умолчанию один std::less.)

От cppreference:

template< 
    class Key, 
    class T, 
    class Compare = std::less<Key>, 
    class Allocator = std::allocator<std::pair<const Key, T> > 
> class map; 

станд :: карта отсортированный ассоциативный контейнер, который содержит ключ-значение пары с уникальными ключами. Ключи сортируются с использованием сравнения . Операции поиска, удаления и вставки имеют логарифмическую сложность. Карты обычно реализуются как red-black trees.

Answer 2

std::map определяется как:

template< 
    class Key, 
    class T, 
    class Compare = std::less<Key>, 
    class Allocator = std::allocator<std::pair<const Key, T> > 
> class map; 

Вы можете использовать специализированные Compare для настройки записи из более map упорядочены. Например, если вы используете:

std::map<int, double, std::greater<int>> myMap; 

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