C++ 从零开始封装 Map 与 Set：实现与优化

// 迭代器 // T 表示数据类型 Ref 为引用 Ptr 为指针
template<class T, class Ptr, class Ref>
struct RBTreeIterator {
    typedef RBTreeNode<T> Node;
    typedef _RBTreeIterator<T, Ref, Ptr> Self;
    Node* _node;
    _RBTreeIterator(Node* node) :_node(node) {}
    Ref operator*() { return _node->_data; }
    Ptr operator&() { return &_node->_data; }
    bool operator!= (const Self& s) { return _node != s._node; }
    bool operator== (const Self& s) { return _node == s._node; }
};

迭代器的访问 ++ 和 --

++ 中序遍历的顺序是先遍历左边再遍历当前节点最后是右子树。

Self& operator++() {
    if (_node->_right) {
        Node* cur = _node->_right;
        while (cur->_left) {
            cur = cur->_left;
        }
        _node = cur;
    } else {
        Node* cur = _node;
        Node* parent = _node->_parent;
        while (parent && cur == parent->_right) {
            cur = parent;
            parent = cur->_parent;
        }
        _node = parent;
    }
    return *this;
}

倒中序遍历 右 根 左 逻辑取反即可。

Self& operator--() {
    if (_node == nullptr) {
        Node* rightMost = _root;
        while (rightMost && rightMost->_right) {
            rightMost = rightMost->_right;
        }
        _node = rightMost;
    } else if (_node->_left) {
        Node* cur = _node->_left;
        while (cur->_right) {
            cur = cur->_right;
        }
        _node = cur;
    } else {
        Node* cur = _node;
        Node* parent = _node->_parent;
        while (parent && cur == parent->_left) {
            cur = parent;
            parent = cur->_parent;
        }
        _node = parent;
    }
    return *this;
}

这里特殊情况是因为我们设置的容器迭代器 end() 为空指针（STL 库是加了个哨兵位节点）不可以再访问了所以特殊处理一下。

3、高级容器设计——Map 与 Set 的模块化封装

3.1 泛型支持增强——RBTree 模板参数设计优化

我们先来看之前写的红黑树的节点代码：

// 节点结构体
template<class K, class V>
struct RBTreeNode {
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    pair<K, V> _kv;
    color _col;
    RBTreeNode(pair<K, V> kv) :_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv) {}
};

在实现 Map 和 Set 的封装时，我们发现当前的设计使得每个红黑树的节点都存储了一个固定的数据类型 pair<K, V>。这种做法虽然对 Map 的实现来说非常直接，但当我们尝试为 Set 封装时，问题就显现出来了：Set 中的节点只需要存储键 K，而不是键值对 pair<K, V>。这意味着如果我们照这种方式实现 Set，我们就不得不重复编写一份类似的红黑树代码来处理不同的数据结构。

为了更好地封装 Map 和 Set，我们可以借鉴 STL 源码中的设计理念。STL 中通过模板编程和类型特化的方式，使得同一个数据结构能够支持不同类型的容器，而不需要重复编写代码。

STL 设计思路解析

首先，最底层的红黑树节点结构体只使用了一个模板参数 Value，该参数决定了节点中存储的数据类型。上层的红黑树根据提供的 Value 类型来选择具体的数据存储结构。

红黑树的关键模板参数

在红黑树的实现中，存在三个关键的模板参数：

1. Key：表示键的类型，主要用于查找操作（如 Find 函数）。
2. Value：表示存储的数据类型。在 Map 中，Value 是 pair<K, V>，而在 Set 中，Value 则只有键 K。
3. KeyOfValue：这是一个仿函数，用于从 Value 中提取 Key。

统一封装：如何实现 Map 与 Set 的共享底层红黑树

通过巧妙的模板设计，红黑树底层实现可以根据不同的需求使用不同的数据结构来存储：

• 对于 Map，底层红黑树将 Key 和 pair<K, V> 作为模板参数传入。
• 对于 Set，红黑树只需要 Key 作为模板参数。

//-------------------------------------------
//------ 红黑树实现 -----------------
//-------------------------------------------
enum color { Black, Red };

// 节点结构体
template<class T>
struct RBTreeNode {
    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;
    T _data;
    color _col;
    RBTreeNode(T data) :_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(Red) {}
};

// 迭代器
template<class T , class Ref , class Ptr>
struct _RBTreeIterator {
    typedef RBTreeNode<T> Node;
    typedef _RBTreeIterator<T, Ref, Ptr> Self;
    Node* _node;
    _RBTreeIterator(Node* node) :_node(node) {}
    Ref operator*() { return _node->_data; }
    Ptr operator&() { return &_node->_data; }
    bool operator!= (const Self& s) { return _node != s._node; }
    Self& operator++() { /* ... */ return *this; }
    Self& operator--() { /* ... */ return *this; }
};

// K 为键值 T 为储存的结构 map 则为 pair set 则为 key KeyOfValue 是取出 Key 的方式
template<class K, class T , class KeyOfValue>
class RBTree {
public:
    typedef _RBTreeIterator<T, T&, T*> Iterator;
    typedef RBTreeNode<T> Node;
    Iterator begin() { /* ... */ }
    Iterator end() { /* ... */ }
    pair<Iterator,bool> insert(const T& data) { /* ... */ }
    Iterator find(const K& key) { /* ... */ }
private:
    RBTreeNode<T>* _root = nullptr;
};

注意比较方式统一改成类似 kot(_data) < kot(node.data) 的样子哦！！！因为 map 与 set 的取出 key 的方式不同！！！**

3.2 Set 容器构建——面向集合操作的优化设计

Set 封装的实现

对于 Set 封装，关键是要根据红黑树的底层实现要求提供相应的模板参数和仿函数。

1. 模板参数传递：Set 需要满足 K 和 V 的模板参数传递。
2. 底层红黑树的实例化：在 Set 类中，我们实例化一个底层红黑树，传入对应的模板参数 K、const K，以及 SetOfT 仿函数。
3. 迭代器的实现：在 Set 类中，我们还需要实现一个迭代器。

仿函数实现：我们需要实现一个仿函数，用于从存储的模板参数 V 中提取出 Key。

struct SetKeyOfT {
    const K& operator()(const K& key) { return key; }
};

namespace xc {
    template<class K>
    class set {
        struct SetKeyOfT {
            const K& operator()(const K& key) { return key; }
        };
    public:
        typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
        typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;
        iterator begin() { return _t.Begin(); }
        iterator end() { return _t.End(); }
        const_iterator begin()const { return _t.Begin(); }
        const_iterator end()const { return _t.End(); }
        pair<iterator,bool> insert(const K&key) { return _t.insert(key); }
        iterator find(const K& key) { return _t.find(key); }
    private:
        RBTree<K, const K, SetKeyOfT> _t;
    };
}

3.3 Map 容器构建——高效键值存储的封装实现

Map 封装的实现

对于 Map 封装，关键是要根据红黑树的底层实现要求提供相应的模板参数和仿函数。

1. 模板参数传递：Map 需要满足 K 和 V 的模板参数传递。
2. 底层红黑树的实例化：在 Map 类中，我们实例化一个底层红黑树，传入对应的模板参数 K、pair<const K, V>，以及 MapOfT 仿函数。
3. 迭代器的实现：在 Map 类中，我们还需要实现一个迭代器。

仿函数实现：我们需要实现一个仿函数，用于从存储的 pair<const K, V> 中提取出 Key。

struct MapKeyOfT {
    const K& operator()(const pair<K, V>& kv) { return kv.first; }
};

namespace xc {
    template<class K, class V>
    class map {
        struct MapKeyOfT {
            const K& operator()(const pair<K, V>& kv) { return kv.first; }
        };
    public:
        typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
        typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;
        iterator begin() { return _t.begin(); }
        iterator end() { return _t.end(); }
        const_iterator begin()const { return _t.begin(); }
        const_iterator end()const { return _t.end(); }
        pair<iterator, bool> insert(const pair<K, V>& kv) { return _t.insert(kv); }
        iterator find(const K& key) { return _t.find(key); }
        V& operator[](const K& key) { 
            pair<iterator, bool> ret = insert({ key, V() }); 
            return ret.first->second; 
        }
    private:
        RBTree<K, pair<const K, V>, MapKeyOfT> _t;
    };
}

测试示例

void test_map() {
    xc::map<string, string> dict;
    dict.insert({ "sort", "排序" });
    dict.insert({ "left", "左边" });
    dict.insert({ "right", "右边" });
    dict["left"] = "左边，剩余";
    dict["insert"] = "插入";
    dict["string"];
    xc::map<string, string>::iterator it = dict.begin();
    while (it != dict.end()) {
        it->second += 'x';
        cout << it->first << ":" << it->second << endl;
        ++it;
    }
    cout << endl;
    for (auto &kv : dict) {
        cout << kv.first << ":" << kv.second << endl;
    }
    cout << endl;
}

int main() {
    test_map();
    return 0;
}

可以看到我们实现了 map 的关键重载函数 []。

map 和 set 从零建立起来不仅需要二叉搜索树的知识还需要 AVL 树和红黑树的使用！！！甚至还需要对于模版的更深理解！！！