遍历 std: : map 的顺序是否已知(并由标准保证) ？

我的意思是，我们知道 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还是定义实现？

现实生活中的原因: 我有一个 std::map与 int键。在非常罕见的情况下，我希望使用键迭代所有大于具体 int值的元素。是的，听起来 std::vector会是更好的选择，但请注意我的“非常罕见的情况”。

编辑 : 我知道，std::map的元素已经排序了。.没有必要指出它(对于这里的大多数答案)。我甚至把它写在了我的问题里。
当我在一个容器中进行迭代时，我问的是迭代器和顺序。谢谢@Kerrek SB 的回答。

105862 次浏览
小开

是保证打印234还是定义它的实现？

是的，std::map是一个已排序的容器，由 Key和提供的 Comparator一起订购。所以它是有保证的。

我想用键迭代所有大于具体 int 值的元素。

这当然有可能。

小开

是的... ... std::map中的元素有一个严格的弱序，这意味着元素将由一个集合组成(即，不会有“相等”的键的重复) ，相等性是通过测试任意两个键 A 和 B 来确定的，如果键 A 不小于键 B，B 不小于 A，那么键 A 就等于键 B。

也就是说，如果 std::map类型的弱顺序不明确(在您的例子中，您使用整数作为键类型，这不是问题) ，那么您就无法对该类型的元素进行正确的排序。您必须能够定义一个操作，定义 std::map中键使用的类型的总顺序，否则您将只有元素或偏序集的部分顺序，这个偏序集具有属性，其中 A 可能不能与 B 相比。在这个场景中通常会发生的情况是，您将能够插入键/值对，但是如果您遍历整个映射，并且/或者当您试图在映射中执行特定键/值对的 std::map::find()时，检测到“缺失”键/值对，那么您可能会得到重复的键/值对。

小开
最佳答案

是的，我保证。此外，由比较运算符确定，*begin()给出最小的元素，*rbegin()给出最大的元素，表达式 !compare(a,b) && !compare(b,a)为真的两个关键值 a和 b被认为是相等的。默认的比较函数是 std::less<K>。

排序不是一个幸运的额外功能，而是数据结构的一个基本方面，因为排序用于确定两个键是否相同(根据上述规则) ，并执行有效的查找(本质上是一个二进制搜索，在元素数量上具有对数复杂性)。

小开

我认为数据结构中存在混淆。

在大多数语言中，map仅仅是一个 AssociativeContainer: 它将一个键映射到一个值。在“较新”的语言中，这通常是通过散列映射实现的，因此不保证顺序。

然而，在 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_*容器不是订购的。最值得注意的是，在修改容器时(在插入/删除时) ，元素 梅的顺序会发生变化。

当标准说元素以某种方式排列时，它的意思是:

  • 在迭代时，您将按照定义的顺序看到元素
  • 当反向迭代时，可以看到元素的顺序是相反的

希望这能解释清楚。

小开

C + + 标准中的关联容器需求保证了这一点。例如，见 C + + 11中的23.2.4/10:

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.
小开

Start ()可以给出最小的元素。但这取决于执行情况。是否在 C + + 标准中指定？如果答案是否定的，那么做出这种假设就是危险的。

小开

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

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


提交答案