Does map store elements as std::pair?

user_7101138 0
Viewed 1093

Does std::map store elements as std::pair? Iterating over map looks like this:

#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;
    } 
}
std-pair internals stdmap c++
3 Answers

No, std::map doesn't store data as pairs, it just exposes it as pairs. Although it's not forbidden to use std::pair in underlying storage.

In typical red-black tree implementation you need at least two pointers to children nodes on top of key and value stored (and probably a pointer to parent node, I don't really remember how RB tree worked, sorry). The underlying storage type is std::map::node_type (added since C++17), which is unspecified in standard (a.k.a. implementation specific).

Note that there is this clause (from 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>.

It suggests that storing data in node-handle type as std::pair is definitely allowed by standard (and implementation may assume that std::pair behaves exactly as expected).

user_79768050

The simple answer is yes.

From [map.overview], a map has a value_type of:

using value_type = pair<const Key, T>;

[unord.map.overview] has the same value_type as well.

Edit: as Yksisarviven states, these still needs to be stored inside a node_type of some sort, which is unspecified in the C++17 standard.

user_106860480

From std::map::extract I would conclude that it stores it as std::map::node_type. What that might be in practice is implementation specific. Researching my GCC 9.3 implementation yields:

  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
    };

This means in my implementation there is a _Val = std::pair contained in the node, i.e. yes, it stores std::pair, but wrapped in a node.

user_47709560
Related