c++ - 如何确保 std::map 已订购？

Question

使用 std::map<int, ...>我如何确保在插入时迭代它会按照整数键的升序进行？

Answer 1

您无需执行任何操作。映射将根据键的值按升序排列。

在内部，映射执行键之间的比较以对其元素进行排序。默认情况下，它使用 std::less<KEY> ，相当于 bool operator<(int, int)对于整数。对于用户定义的类型，您必须选择:

1. 实现 bool operator<(const MyType&, const MyType&)在用户定义的类型之间实现严格的弱排序比较。如果您的类型具有自然顺序，请使用此选项

2. 提供一个实现严格弱排序的二元仿函数，您可以将其作为第三个模板参数传递给 map 。如果您的类型没有自然顺序，或者如果您想使用与 std::less<Key> 使用的顺序不同的顺序构建 map ，请使用此选项。通过 bool operator<(...)从第 1 点开始。

通常在幕后发生的事情是将 map 实现为自平衡二叉树，并使用严格的弱排序在 map 中放置新元素，并确定两个元素是否相等。顺便说一句，同样的逻辑适用于 std::set ，其中键和值是相同的。