C++ 迭代 std::map 的顺序是否已知（并由标准保证）？

Is the order of iterating through std::map known (and guaranteed by the standard)?

提问by Kiril Kirov

What I mean is - we know that the std::map's elements are sorted according to the keys. So, let's say the keys are integers. If I iterate from std::map::begin()to std::map::end()using a for, does the standard guarantee that I'll iterate consequently through the elements with keys, sorted in ascending order?

我的意思是 - 我们知道std::map的元素是根据键排序的。所以，假设键是整数。如果我从迭代std::map::begin()来std::map::end()使用for，不标准的保证，我会通过与键的元素因此迭代，按升序排序？

---

---

Example:

例子：

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;
}

Is this guaranteed to print 234or is it implementation defined?

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

---

---

Real life reason: I have a std::mapwith intkeys. In very rare situations, I'd like to iterate through all elements, with key, greater than a concrete intvalue. Yep, it sounds like std::vectorwould be the better choice, but notice my "very rare situations".

现实生活中的原因：我有一个std::map带int钥匙的。在非常罕见的情况下，我想使用大于具体int值的键遍历所有元素。是的，这听起来std::vector是更好的选择，但请注意我的“非常罕见的情况”。

---

---

EDIT: I know, that the elements of std::mapare sorted.. no need to point it out (for most of the answers here). I even wrote it in my question.
I was asking about the iterators and the order when I'm iterating through a container. Thanks @Kerrek SB for the answer.

编辑：我知道， 的元素std::map已排序.. 无需指出（对于此处的大多数答案）。我什至在我的问题中写了它。
我在遍历容器时询问了迭代器和顺序。感谢@Kerrek SB 的回答。

回答by Kerrek SB

Yes, that's guaranteed. Moreover, *begin()gives you the smallest and *rbegin()the largest element, as determined by the comparison operator, and two key values aand bfor which the expression !compare(a,b) && !compare(b,a)is true are considered equal. The default comparison function is std::less<K>.

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

The ordering is not a lucky bonus feature, but rather, it is a fundamental aspect of the data structure, as the ordering is used to determine when two keys are the same (by the above rule) and to perform efficient lookup (essentially a binary search, which has logarithmic complexity in the number of elements).

排序不是幸运的奖励功能，而是数据结构的一个基本方面，因为排序用于确定两个键何时相同（通过上述规则）并执行有效的查找（本质上是一个二进制搜索，其元素数量具有对数复杂性）。

回答by Konstantin Oznobihin

This is guaranteed by Associative container requirements in the C++ standard. E.g. see 23.2.4/10 in C++11:

这是由 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

and 23.2.4/11

和 23.2.4/11

For associative containers with unique keys the stronger condition holds,
  value_comp(*i, *j) != false.

回答by Matthieu M.

I think there is a confusion in data structures.

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

In most languages, a mapis simply an AssociativeContainer: it maps a key to a value. In the "newer" languages, this is generally achieved using a hash map, thus no order is guaranted.

在大多数语言中， amap只是一个 AssociativeContainer：它将键映射到值。在“较新”的语言中，这通常是使用哈希映射来实现的，因此不保证顺序。

In C++, however, this is not so:

然而，在 C++ 中，情况并非如此：

• std::mapis a sortedassociative container
• std::unordered_mapis a hash-table based associative container introduced in C++11

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

So, in order to clarify the guarantees on ordering.

因此，为了澄清订购的保证。

In C++03:

在 C++03 中：

• std::set, std::multiset, std::mapand std::multimapare guaranteed to be ordered according to the keys (and the criterion supplied)
• in std::multisetand std::multimap, the standard does not impose any order guarantee on equivalent elements (ie, those which compare equal)

• std::set, std::multiset,std::map和std::multimap保证根据键（和提供的标准）进行排序
• 在std::multisetand 中std::multimap，标准不对等价元素（即比较相等的元素）强加任何顺序保证

In C++11:

在 C++11 中：

• std::set, std::multiset, std::mapand std::multimapare guaranteed to be ordered according to the keys (and the criterion supplied)
• in std::multisetand std::multimap, the Standard imposesthat equivalent elements (those which compare equal) are ordered according to their insertion order (first inserted first)
• std::unordered_*containers are, as the name imply, not ordered. Most notably, the order of elements maychange when the container is modified (upon insertion/deletion).

• std::set, std::multiset,std::map和std::multimap保证根据键（和提供的标准）进行排序
• 在std::multisetand 中std::multimap，标准规定等效元素（比较相等的元素）根据它们的插入顺序（先插入）进行排序
• std::unordered_*顾名思义，容器不是有序的。最值得注意的是，当容器被修改时（插入/删除时），元素的顺序可能会改变。

When the Standard says that elements are ordered in a way, it means that:

当标准说元素以某种方式排序时，这意味着：

• when iterating, you see the elements in the order defined
• when iterating in reverse, you see the elements in the opposite order

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

I hope this clears up any confusion.

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

回答by jpalecek

Is this guaranteed to print 234 or it's implementation defined?

这是否保证打印 234 或它的实现定义？

Yes, std::mapis a sorted container, ordered by the Keywith the supplied Comparator. So it is guaranteed.

是的，std::map是一个已排序的容器，按Key提供的Comparator. 所以是有保证的。

I'd like go iterate through all elements, with key, greater than a concrete int value.

我想遍历所有元素，键值大于具体的 int 值。

That is surely possible.

那肯定是可能的。

回答by Jason

Yes ... the elements in a std::maphave a strict weak-ordering, meaning that the elements will be composed of a set (i.e., there will be no repeats of keys that are "equal"), and equality is determined by testing on any two keys A and B, that if key A is not less than key B, and B is not less than A, then key A is equal to key B.

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

That being said, you cannot properly sort the elements of a std::mapif the weak-ordering for that type is ambiguous (in your case, where you are using integers as the key-type, that is not a problem). You must be able to define a operation that defines a total order on the type you are using for the keys in your std::map, otherwise you will only have a partial order for your elements, or poset, which has property where A may not be comparable to B. What will typically happen in this scenario is that you'll be able to insert the key/value pairs, but you may end up with duplicate key/value pairs if you iterate through the entire map, and/or detect "missing" key/value pairs when you attempt to perform a std::map::find()of a specific key/value pair in the map.

话虽如此，std::map如果该类型的弱排序不明确（在您的情况下，您使用整数作为键类型，这不是问题），您将无法正确排序 a 的元素。您必须能够定义一个操作，该操作定义您std::map用于 . B. 在这种情况下通常会发生的是，您将能够插入键/值对，但如果您遍历整个地图和/或检测到“丢失”，最终可能会得到重复的键/值对当您尝试std::map::find()在映射中执行特定键/值对时的键/值对。

回答by pyang

begin() may give the smallest element. But it is implementation depended. Is it specified in the C++ standard? If not, then it is dangerous to make this assumption.

begin() 可以给出最小的元素。但它取决于实现。它是否在 C++ 标准中指定？如果不是，那么做出这个假设是危险的。