首页 文章

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

提问于
浏览 次
133

我的意思是 - 我们知道 std::map 's elements are sorted according to the keys. So, let'表示键是整数 . 如果我使用 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 还是实现定义？

现实生活中的原因：我有一个 std::map 用 int 键 . 在非常罕见的情况下，我想用密钥迭代所有元素，而不是具体的 int 值 . 是的，听起来像 std::vector 会是更好的选择，但请注意我的"very rare situations" .

EDIT ：我知道， std::map 的元素是排序的......不需要指出它（对于这里的大多数答案） . 我甚至在我的问题中写了它 .
我在迭代容器时询问迭代器和顺序 . 谢谢@Kerrek SB的答案 .

c++ dictionary stl order standards

5 回答

  • 23

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

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

    回复于
  • 145

    这是由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.
    回复于
  • 38

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

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

    但是，在C中，情况并非如此：

    • std::map 是一个 sorted 关联容器

    • std::unordered_map 是C 11中引入的基于哈希表的关联容器

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

    In C++03:

    保证按照键（和提供的标准）订购

    • std::set ， std::multiset ， std::map 和 std::multimap
      _999842_和 std::multimap 中的
    • ，标准不对等效元素强加任何订单保证（即比较相等的那些）

    In C++11:

    保证按照键（和提供的标准）订购

    • std::set ， std::multiset ， std::map 和 std::multimap
      _999849_和 std::multimap 中的

    • ，标准规定等效元素（比较相等的元素）按其插入顺序排序（首先插入）

    • std::unordered_* 容器，顾名思义，未订购 . 最值得注意的是，当容器被修改时（插入/删除时），元素的顺序可能会改变 .

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

    • 迭代时，您会看到定义顺序的元素

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

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

    回复于
  • 4

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

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

    我想用密钥迭代所有元素，大于具体的int值 .

    这肯定是可能的 .

    回复于
  • 3

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

    话虽如此，如果该类型的弱排序不明确（在您的情况下，您使用整数作为键类型，这不是问题），您无法正确排序 std::map 的元素 . 您必须能够定义一个操作，该操作定义您用于 std::map 中的键的类型的总订单，否则您将只对您的元素或poset有一个部分订单，其中包含A可能无法比较的属性B.在这种情况下通常会发生的是，您将能够插入键/值对，但如果您遍历整个 Map ，并且/或检测到"missing"键，您可能会得到重复的键/值对/ value当您尝试在 Map 中执行特定键/值对的 std::map::find() 时 .

    回复于

相关问题