std::map 的排序

Question

对于 std::map，在迭代时，我能否始终相信 begin() 到 return 根据类型的比较运算符具有最小键的元素？

换句话说...

可以std::map<Key, SomeClass>::iterator smallestKeyIt = someMap.begin();给我映射中键值最小的对吗？

这是为 std::map 确定的顺序，还是我可以以某种方式配置它？我的理解是底层树结构在执行添加和删除元素等操作时保持有序。

Answer 1

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 中的第一个条目将具有最大的键。

Answer 2

can i always trust begin() to return the element with the smallest key according to comparison operators for the type?

是的。

Is this the ordering that is quaranteed for an std::map or can i configure it somehow?

是的。您可以通过指定比较器来配置比较的行为。（默认为std::less。）

来自cppreference：

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

std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as red-black trees.

std::map 的排序

The ordering of an std::map

c++

iterator

stdmap