迭代通过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，还是定义了实现？
现实生活中的理由:我有一台带int密钥的std::map。在极少数情况下，我会使用键遍历所有大于具体int值的元素。是的，听起来std::vector会是更好的选择，但请注意我的“非常罕见的情况”。
编辑：我知道，std::map的元素是排序的..不需要指出它(对于这里的大多数答案)。我甚至把它写在我的问题里。
当我在容器中迭代时，我问的是迭代器和顺序。感谢@Kerrek SB的回答。
回答 6
Stack Overflow用户
发布于 2011-10-04 21:39:10
是的，这是有保证的。此外，*begin()提供最小的元素，*rbegin()提供最大的元素(由比较运算符确定)，表达式!compare(a,b) && !compare(b,a)为true的两个键值a和b被视为相等。默认比较函数为std::less<K>。
排序不是幸运的奖励特征，相反，它是数据结构的基本方面，因为排序用于确定两个键何时相同(根据上述规则)并执行有效的查找(本质上是二进制搜索，其元素数量具有对数复杂性)。
Stack Overflow用户
发布于 2011-10-04 22:18:09
我认为数据结构中存在混乱。
在大多数语言中，map只是一个AssociativeContainer:它将一个键映射到一个值。在“较新”的语言中，这通常是使用散列映射来实现的，因此不保证顺序。
然而，在C++中，情况并非如此：
std::map是C++11
中引入的基于哈希表的关联容器
std::map是一种排序的关联容器
因此，为了澄清对排序的保证。
C++03中的：
std::set，std::multiset、std::map和std::multimap保证根据std::multiset和std::multimap中的关键字(以及提供的标准)- 进行排序，该标准不会对等效元素(即比较相等的元素)施加任何排序保证
C++11中的：
std::set，容器、first)std::unordered_*容器和
容器保证按照键(和提供的标准)进行排序。在std::multiset和std::multimap中，标准要求等价的元素(那些比较相等的元素)按照它们的插入顺序排序(第一次插入的first)
std::unordered_*容器，顾名思义，就是没有排序的)。最值得注意的是，当修改容器时(在insertion/deletion).
上)，元素的顺序可能会改变
当标准说元素以某种方式排序时，这意味着：
- 迭代时，您会看到顺序定义为
- 的元素反向迭代时，您会看到顺序相反的元素
我希望这能澄清任何困惑。
Stack Overflow用户
发布于 2011-10-04 21:36:43
这是保证打印234还是定义它的实现？
是的，std::map是一个有序的容器，由带有提供的Comparator的Key排序。所以这是有保证的。
我希望go遍历所有元素，使用
，大于一个具体的int值。
这当然是有可能的。
https://stackoverflow.com/questions/7648756
复制相似问题
腾讯云开发者
