迭代通过std :: map的顺序是否已知(并由标准保证)?

我的意思是 – 我们知道std::map的元素是根据键来sorting的。 所以,假设键是整数。 如果我使用for来从std::map::begin()迭代到std::map::end() ,那么标准保证我将通过带有键的元素迭代,按照升序sorting?


例:

 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将是更好的select,但注意到我的“非常罕见的情况下”。


编辑 :我知道, std::map的元素是sorting..没有必要指出(大部分的答案在这里)。 我甚至写在我的问题。
当我迭代一个容器时,我正在询问迭代器和顺序。 谢谢@Kerrek SB的答案。

是的,这是有保证的。 此外, *begin()给你最小的*rbegin()最大的元素,由比较运算符决定,还有两个关键值ab ,expression式!compare(a,b) && !compare(b,a)是正确的被认为是平等的。 默认的比较函数是std::less<K>

sorting不是一个幸运的奖金function,而是它是数据结构的基本方面,因为sorting是用来确定两个键是相同的(通过上述规则),并执行有效的查找(本质上是一个二进制search,其元素数量具有对数复杂性)。

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

我认为数据结构是混乱的。

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

但在C ++中,情况并非如此:

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

所以,为了澄清订货的保证。

在C ++ 03中:

  • std::setstd::multisetstd::mapstd::multimap保证按照键(和提供的标准)sorting,
  • std::multisetstd::multimap ,标准没有对等价元素(即比较相等的元素)施加任何顺序保证,

在C ++ 11中:

  • std::setstd::multisetstd::mapstd::multimap保证按照键(和提供的标准)sorting,
  • std::multisetstd::multimap ,标准规定等价元素(比较相等的元素)根据它们的插入顺序sorting(首先插入)
  • std::unordered_*容器,顾名思义,没有sorting。 最值得注意的是,当容器被修改(插入/删除时)元素的顺序可能会改变。

当标准规定元素以某种方式排列时,这意味着:

  • 迭代时,您可以按照定义的顺序查看元素
  • 当反向迭代时,您会看到相反顺序的元素

我希望这可以消除任何混乱。

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

是的, std::map是一个已sorting的容器,由Key提供的Comparator进行sorting。 所以这是保证。

我想要遍历所有元素,用键,大于一个具体的int值。

这当然是可能的。

是的… std::map的元素具有严格的弱sorting,这意味着元素将由一个集合组成(即不会有重复的“相等”的键),并且确定相等性通过testing任何两个键A和B,如果键A不小于键B,并且B不小于A,则键A等于键B.

也就是说,如果这个types的弱顺序是不明确的,那么你不能正确地对std::map的元素进行sorting(在你的情况下,你使用整数作为键types,这不是问题)。 您必须能够定义一个操作,该操作定义了您在std::map用于键的types的总顺序,否则您将只有部分顺序为您的元素或poset,其中A的属性不能与B进行比较。在这种情况下通常会发生的情况是,您将能够插入键/值对,但是如果遍历整个地图,则可能会出现重复的键/值对,和/或当您尝试在std::map::find()执行特定键/值对的std::map::find() ,检测“缺less”键/值对。