std::map 类

与 std::list 一样，std::map 使用元素之间的链接形成结构。std::map 独有的是，每个元素存储两块数据（键和值），排序是底层数据结构的固有属性：红黑树。以下代码显示了组成 std::map 的结构。

template<typename keyT, typename valT>
struct mapItem {
    mapItem<keyT, valT>* left;
    mapItem<keyT, valT>* parent;
    mapItem<keyT, valT>* right;
    keyT key;
    valT value;
};
template<typename keyT, typename valT>
struct map {
    DWORD irrelevant;
    mapItem<keyT, valT>* rootNode;
    int size;
}

红黑树是自平衡二叉搜索树，所以 std::map 也是。在 STL 的 std::map 实现中，树中的每个元素（或节点）有三个指针：left、parent 和 right。除了指针，每个节点还有一个键和一个值。节点根据键之间的比较排列在树中。节点的 left 指针指向键较小的节点，right 指针指向键较大的节点。parent 指向上层节点。树中的第一个节点叫做 rootNode，没有子节点的节点指向它。