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

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

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.