地图是否将元素存储为 std::pair？

Question

std::map 是否将元素存储为 std::pair？遍历 map 如下所示：

#include <map>
int main() {
    std::map<int, char> m;
    m[1] = 'A';
    m[2] = 'B';
    m[3] = 'C';

    std::map<int, char>::iterator it;
    for(it = m.begin(); it != m.end(); it++)
    {
       std::cout << "Key: "    << it->first;
       std::cout << " Value: " << it->second;
       std::cout << std::endl;
    } 
}

Answer 1

简单的答案是肯定的。

从 [map.overview] 开始，map 的 value_type 为：

using value_type = pair<const Key, T>;

[unord.map.overview] 也有相同的 value_type。

编辑：正如 Yksisarviven 所说，这些仍然需要存储在某种 node_type 中，这在 C++17 标准中是 未指定的。

Answer 2

不，std::map 不会 成对存储 数据，它只是将其公开为对。 虽然不禁止在底层存储中使用 std::pair。

在典型的红黑树实现中，您至少需要两个指针指向存储的键和值之上的子节点（可能还有一个指向父节点的指针，我不太记得 RB 树是如何工作的，抱歉） .底层存储类型是 std::map::node_type（自 C++17 起添加），在标准中未指定（a.k.a。特定于实现）。

注意有这个子句（来自cppreference）：

For all map containers (std::map, std::multimap, std::unordered_map, and std::unordered_multimap) whose key_type is K and mapped_type is T, the behavior of operations involving node handles are undefined if a user-defined specialization of std::pair exists for std::pair<K, T> or std::pair<const K, T>.

它表明将数据存储在 node-handle 类型中作为 std::pair 是标准绝对允许的（并且实现可能假设 std::pair 的行为与预期）。

Answer 3

从 std::map::extract 我会得出结论，它将它存储为 std::map::node_type。在实践中可能是特定于实现的。研究我的 GCC 9.3 实现收益：

  template<typename _Val>
    struct _Rb_tree_node : public _Rb_tree_node_base
    {
      typedef _Rb_tree_node<_Val>* _Link_type;

#if __cplusplus < 201103L
      _Val _M_value_field;

      _Val*
      _M_valptr()
      { return std::__addressof(_M_value_field); }

      const _Val*
      _M_valptr() const
      { return std::__addressof(_M_value_field); }
#else
      __gnu_cxx::__aligned_membuf<_Val> _M_storage;

      _Val*
      _M_valptr()
      { return _M_storage._M_ptr(); }

      const _Val*
      _M_valptr() const
      { return _M_storage._M_ptr(); }
#endif
    };

这意味着在我的实现中节点中包含一个 _Val = std::pair，即是的，它存储 std::pair，但包裹在一个节点中。

地图是否将元素存储为 std::pair？

Does map store elements as std::pair?

c++

stdmap

std-pair

internals