c++ - map 是否将元素存储为 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

不，std::map不以对的形式存储数据，它只是以对的形式公开它。 虽然不禁止使用std::pair在底层存储中。

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

请注意，有此子句(来自 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>.

它建议将数据以节点句柄类型存储为 std::pair标准绝对允许(并且实现可能假设 std::pair 的行为完全符合预期)。