在C++标准中，遍历std::map的顺序是否是已知的并且有保证的？

Question

我的意思是 - 我们知道 std::map 的元素是根据键进行排序的。所以，假设键是整数。如果我使用 for 从 std::map::begin() 迭代到 std::map::end()，标准是否保证我会按照升序顺序连续迭代元素的键？

---

例子：

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，还是由实现定义？

---

真实的原因：我有一个以int为键的std::map。在非常罕见的情况下，我想遍历所有键大于某个具体int值的元素。是的，听起来std::vector可能是更好的选择，但请注意我的“非常罕见的情况”。

---

编辑：我知道，std::map的元素是有序的，不需要再指出来（对于大多数回答来说）。我甚至在问题中写了这一点。
我问的是关于迭代器和遍历容器时的顺序。谢谢@Kerrek SB的回答。

- Kiril Kirov

---

如果你不知道的话：在实际应用中，你可以使用 map::upper_bound 来找到开始迭代的位置。 - Steve Jessop

我知道这个，也知道我要开始迭代的确切位置。我只是想知道顺序是否有保证。 - Kiril Kirov

如果您的键（数字索引）在整个范围内变化巨大，那么稀疏向量就不太合适。我正在使用类似的解决方案，其中数值索引表示三维空间中的笛卡尔y坐标。在这种情况下使用向量会增加我的内存占用量，达到几个GB。因此，我认为向量在这里并非万能药。 - Coder Guy

我不理解这个问题，并且我将通过一个思维实验来解释原因。如果您已经知道元素是有序的，那么迭代怎么可能不是有序的呢？如果顺序不适用于迭代，那么顺序到底意味着什么？还有其他哪些情况下顺序很重要，可以被检测到等等？（答案由Konstantin给出。） - underscore_d

这实际上是一个非常有趣的现象 :) 理解数据结构的人不会理解这个问题，但是将std::map视为“列表”的人会理解为什么会问这个问题。（当然，std::map不是一个列表）。实际上，@underscore_d的评论很中肯 :) - starriet

Answer 1

是的，这是有保证的。此外，*begin() 给出最小元素，*rbegin() 给出最大元素，按照比较操作符确定，对于两个关键值 a 和 b，如果表达式 !compare(a,b) && !compare(b,a) 为真，则它们被视为相等。默认的比较函数是 std::less<K>。

排序不是幸运的额外功能，而是数据结构的基本方面，因为排序用于确定何时两个键相同（按照上述规则）并执行高效查找（本质上是二分查找，在元素数量的对数复杂度下进行）。

- Kerrek SB

---

std::map 是使用二叉树实现的，因此在技术上不执行二分查找。 - jupp0r

将一段范围作为二叉搜索树进行结构化是实现二分查找的特定方法。 "二分查找"是一个抽象的概念，而不是特定的实现。无论您是通过在数组中跳过偏移量还是遵循链接节点，这些都只是“将范围二分”的具体方式，没有影响。 - Kerrek SB

我知道这是一篇旧帖子，但要明确“高效查找”是相对的。从技术上讲，std::unordered_map 的查找时间更为高效，为O(1)。std::map 的优势在于键排序，而不是查找。 - Adam Johnston

@AdamJohnston：一般情况下，使用适当的密钥位分布，你是正确的。但请记住，O(1)不能保证，在最坏的情况下，它会退化为O(n)。相比之下，对于std::map中的任何类型的键，O(log n)都是保证的。 - Dredok

Answer 2

这是由C++标准中的关联容器要求保证的。例如，请参见C++11中的23.2.4/10：

迭代关联式容器的基本属性是它们按键的非降序遍历容器，其中“非降序”由用于构造它们的比较定义。对于任何两个可以解引用的迭代器i和j，使得从i到j的距离为正数，

value_comp(*j, *i) == false 并且23.2.4/11

对于具有唯一键的关联容器，更强的条件成立，

value_comp(*i, *j) != false.

- Konstantin Oznobihin

Answer 3

我觉得数据结构中存在一些混淆。

在大多数语言中，map通常是一个关联容器：它将键映射到值。在“新一代”的语言中，通常使用哈希表来实现这一点，因此不能保证顺序。

但是，在C++中情况并非如此：

• std::map是一个有序的关联容器
• std::unordered_map是基于哈希表的关联容器，引入于C++11

因此，为了澄清排序方面的保证：

在C++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_*容器正如其名称所示，是无序的。特别地，当对容器进行修改（插入/删除）时，元素的顺序可能会发生变化。

当标准表示元素以某种方式有序时，这意味着：

• 在迭代时，您会按照定义的顺序看到元素

在反向迭代时，您可以看到元素的相反顺序

我希望这能消除任何困惑。

- Matthieu M.

---

这与我的问题无关，抱歉 :) 我知道哪些是有序的，哪些不是。我正在询问当我迭代元素时的顺序。 - Kiril Kirov

一个有序关联容器的“定义”是，在迭代元素时它们是按顺序排列的。 - Matthieu M.

嗯，我想你是对的，但我不知道那个，这正是我所问的 :) - Kiril Kirov

Answer 4

这个代码保证输出234还是实现定义的？

是的，std::map 是一个有序容器，按照提供的 Comparator 排序后，以 Key 为顺序。所以这是可以保证的。

我想要遍历所有元素，并且只取大于某个整数值的键值对。

这是完全可以实现的。

- jpalecek

Answer 5

是的，std::map中的元素具有严格的弱序，这意味着元素将由一组组成（即相等的键不会重复），并且通过测试任何两个键A和B来确定相等性，如果键A不小于键B且B不小于A，则键A等于键B。

话虽如此，如果该类型的弱序模糊不清，则无法正确排序std::map的元素（在您的情况下，使用整数作为键类型不是问题）。您必须能够定义一个操作，以对您在std::map中用于键的类型定义总顺序，否则您的元素仅具有部分顺序或poset属性，其中A可能无法与B进行比较。在这种情况下，通常会发生的情况是您可以插入键/值对，但如果您遍历整个映射，则可能会得到重复的键/值对，并/或者在尝试执行特定键/值对的std::map::find()时检测到“缺失”的键/值对。

- Jason

---

和其他答案一样，这并没有真正回答我的问题，不过还是谢谢。 - Kiril Kirov

Answer 6

为了完整起见，我想提到，如果您的容器包含指针，由于ASLR，每个新程序运行时迭代顺序可能会有所不同。因此，即使一个运行中的顺序是确定的，多个运行之间的顺序也是不确定的。

这是否对正确性很重要取决于特定的程序。

- yugr

Answer 7

begin() 可能会返回最小的元素。但这取决于具体实现。在 C++ 标准中是否有规定？如果没有，那么做出这种假设是危险的。

- pyang