Does map store elements as std::pair?

Question

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

Maddox

Why not just look at the implementation of your particular compiler. Not all vendors use the same template. The source code for templates is normally in the header file. – Fibrinolysin

From en.cppreference.com/w/cpp/container/map : "std::map is a sorted associative container that contains key-value pairs with unique keys.". In practical sense I would say: yes. In technical sense: no, std::map implementation just provides such iterator (but I'm not expert). I'm not sure what you're looking for? – Evelinaeveline

Answer 1

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).

Fruge

Here it is said that type of elements is std::map is std::pair<const X, Y>: https://mcmap.net/q/134365/-what-does-iterator-gt-second-mean. Is this then incorrect? – Maddox

@Maddox For for almost every use, the approximation that std::map stores objects of type std::pair is good enough. You insert and read data always as std::pair. In practice, data is stored in nodes, which contain std::pair (or just key and value as they are) and some pointers. – Fruge

But can we say that type of elements in std::map is std::pair? – Maddox

@Maddox Yes, the type of elements in std::map would be std::pair (and those are stored internally in unspecified node class). – Fruge

How does std::map::node_type store std::pair<K, T> yet the map is still able to expose pointers to std::pair<const K, T>? – Horseback

@Horseback It's a possibility, but gcc for example stores std::pair<const K, T> in map's node_type. I suppose an implementation could get away with storing std::pair<K, T> and casting it every time it's returned (possibly in some UB involving way), but I can't think of any advantage of using that over std::pair<const K, T> off the top of my head. – Fruge

Answer 2

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.

Palliasse

Answer 3

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.

Instil