我的意思是 - 我们知道 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 的回答。
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?
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 234 or is it implementation defined?
Real life reason: I have a std::map with int keys. In very rare situations, I'd like to iterate through all elements, with key, greater than a concrete int value. Yep, it sounds like std::vector would be the better choice, but notice my "very rare situations".
EDIT: I know, that the elements of std::map are 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.
发布评论
评论（7）
是的，这是有保证的。此外，
*begin()为您提供最小元素和*rbegin()最大元素（由比较运算符确定）以及两个键值a 和b，其中表达式!compare(a,b) && !compare(b,a)为 true 时被认为是相等的。默认比较函数是std::less。排序并不是一个幸运的奖励功能，而是数据结构的一个基本方面，因为排序用于确定两个键何时相同（根据上述规则）并执行有效的查找（本质上是一个二进制）搜索，其元素数量具有对数复杂度）。
Yes, that's guaranteed. Moreover,
*begin()gives you the smallest and*rbegin()the largest element, as determined by the comparison operator, and two key valuesaandbfor which the expression!compare(a,b) && !compare(b,a)is true are considered equal. The default comparison function isstd::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).
C++ 标准中的关联容器要求保证了这一点。例如，参见 C++11 中的 23.2.4/10：
和 23.2.4/11
This is guaranteed by Associative container requirements in the C++ standard. E.g. see 23.2.4/10 in C++11:
and 23.2.4/11
我认为数据结构存在混乱。
在大多数语言中，
map只是一个 AssociativeContainer：它将键映射到值。在“较新”的语言中，这通常是使用哈希映射来实现的，因此无法保证顺序。然而，在 C++ 中，情况并非如此：
std::map是一个排序关联容器std::unordered_map是一个基于哈希表的C++11 中引入了关联容器，以便澄清排序的保证。
在 C++03 中：
std::set、std::multiset、std::map和 < code>std::multimap 保证根据std::multiset和std::multimap中的键（以及提供的标准）进行排序，该标准不对等效元素强加任何顺序保证（即，比较相等的）在 C++11 中：
std::set、std::multiset、std::map< 键（以及提供的标准）进行排序std::multimap保证根据std::multiset和std::multimap 中的，标准强制等效元素（比较相等的元素）根据其插入顺序（先插入先插入）排序std::unordered_*容器，顾名思义，不是订购了。最值得注意的是，当容器被修改（插入/删除时）时，元素的顺序可能发生变化。当标准说元素以某种方式排序时，这意味着：
我希望这可以消除任何混乱。
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.In C++, however, this is not so:
std::mapis a sorted associative containerstd::unordered_mapis a hash-table based associative container introduced in C++11So, in order to clarify the guarantees on ordering.
In C++03:
std::set,std::multiset,std::mapandstd::multimapare guaranteed to be ordered according to the keys (and the criterion supplied)std::multisetandstd::multimap, the standard does not impose any order guarantee on equivalent elements (ie, those which compare equal)In C++11:
std::set,std::multiset,std::mapandstd::multimapare guaranteed to be ordered according to the keys (and the criterion supplied)std::multisetandstd::multimap, the Standard imposes that 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 may change when the container is modified (upon insertion/deletion).When the Standard says that elements are ordered in a way, it means that:
I hope this clears up any confusion.
是的，
std::map是一个排序容器，按Key和提供的Comparator排序。所以是有保证的。这当然是可能的。
Yes,
std::mapis a sorted container, ordered by theKeywith the suppliedComparator. So it is guaranteed.That is surely possible.
是的...
std::map中的元素具有严格的弱排序，这意味着元素将由一个集合组成（即，“相等”的键不会重复） ")，相等性是通过对任意两个键 A 和 B 进行测试来确定的，如果键 A 不小于键 B，并且 B 不小于 A，则键 A 等于键 B。也就是说，您无法正确对 a 的元素进行排序
std::map如果该类型的弱排序不明确（在您的情况下，您使用整数作为键类型，这不是问题）。您必须能够定义一个操作，该操作定义您在std::map中用于键的类型的总顺序，否则您将只有元素或偏序集的部分顺序，其中 A 可能无法与 B 进行比较。在这种情况下通常会发生的情况是，您将能够插入键/值对，但如果您迭代，最终可能会得到重复的键/值对整个地图，和/或检测“丢失”的键/值当您尝试对映射中的特定键/值对执行std::map::find()时。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.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 yourstd::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 astd::map::find()of a specific key/value pair in the map.为了完整起见，我想提一下，如果您的容器包含指针，则每个新程序运行时的迭代顺序可能会有所不同，因为ASLR。因此，尽管一次运行中的顺序是确定性的，但多次运行中的顺序不是。
这对于正确性是否重要取决于特定的程序。
For completeness sake I'd like to mention that if your container includes pointers, the iteration order may differ in each new program run due to ASLR. So even though the order in one run is deterministic, the order across multiple runs is not.
Whether this is important for correctness depends on particular program.
begin() 可能会给出最小的元素。但这取决于实施。 C++标准中有规定吗？如果不是，那么做出这个假设是危险的。
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.