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

Question

我的意思是 - 我们知道这些std::map元素是根据键排序的.所以,让我们说键是整数.如果我从迭代std::map::begin()来std::map::end()使用for,不标准的保证,我会通过与键的元素,按升序排序结果迭代？

---

例:

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的答案.

Answer 1

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

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

Answer 2

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

Answer 3

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

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

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

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

所以,为了澄清订购的保证.

在C++ 03中:

• std::set,std::multiset,std::map和std::multimap,保证按照键进行排序(并供应的标准)
• in std::multiset和std::multimap,该标准没有对等效元素强加任何订单保证(即那些比较相等的元素)

在C++ 11中:

• std::set,std::multiset,std::map和std::multimap,保证按照键进行排序(并供应的标准)
• in std::multiset和std::multimap,标准规定等效元素(比较相等的元素)按照它们的插入顺序排序(首先插入)
• std::unordered_*顾名思义,容器没有订购.最值得注意的是,当容器被修改时(插入/删除时),元素的顺序可能会改变.

当标准说元素以某种方式排序时,它意味着:

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

我希望这可以解决任何困惑.

Answer 4

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

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

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

那肯定是可能的。