c++ - 将 Balanced BST 扩展到 C++ STL Map

Question

出于练习目的，我实现了平衡二叉搜索树(红黑树)。这是我目前已实现的底层节点和方法的数据结构的标题:

#ifndef BST_H
#define BST_H
template <typename T>
class treeNode {
public:
    treeNode *left;
    treeNode *right;
    T key;
    treeNode(T key)
        : key(key)
        , left(nullptr)
        , right(nullptr) {
    }
};

template <typename T>
class BST {
public:
    BST() {
        root = nullptr;
        nodes = 0;
    }

    BST(BST const& rhs);

    BST& operator = (BST rhs) {
        this->swap(rhs);
    }

    BST& operator = (BST&& rhs) {
        this->swap(rhs);
    }

    ~BST() {
        clear(root);
    }

    void swap(BST& other) {
        std::swap(root, other.root);
        std::swap(nodes, other.nodes);
    }

    void clear(treeNode<T>* node) {
        if(node) {
            if(node->left) clear(node->left);
            if(node->right) clear(node->right);
            delete node;
        }
    }

    bool isEmpty() const {
        return root == nullptr;
    }
    void inorder(treeNode<T>*);
    void traverseInorder();

    void preorder(treeNode<T>*);
    void traversePreorder();

    void postorder(treeNode<T>*);
    void traversePostorder();

    void insert(T const& );

    void remove(T const& );

    treeNode<T>* search(const T &);

    treeNode<T>* minHelper(treeNode<T>*);
    treeNode<T>* min();

    treeNode<T>* maxHelper(treeNode<T>*);
    treeNode<T>* max();

    size_t size() const;

    void sort();
    treeNode<T>* inOrderSuccessor(treeNode<T>*);
    bool isBST(treeNode<T>*) const;
    bool isBST() const;

private:
    treeNode<T> *root;
    size_t nodes;
};
#endif

我打算实现 C++ STL map(我已经使用 Hashtable 实现了 STL unordered_map)，其底层数据结构是红黑树 AFAIK。如何将我的树扩展为键值通用类型映射？

不需要任何类型的源代码。一些直觉就足够了。谢谢:)

Answer 1

凭直觉:T可能会是 pair<const key_type,mapped_type> .我假设您目前使用 node.key < another_node.key进行比较。那不行，因为 map 应该只使用该对的第一部分。您可以添加 Compare仿函数作为模板参数(与您必须为 map 类采用的方式类似)添加到您的树中，使其可用于实现 STL 兼容映射。

您可以选择设计您的树，使键和值类分开而不是合并。下面是模板定义的示例代码:

template<class Key, class Value, class Comp=std::less<Key>>
class BST {
    Compare comp;
public:
    BST(const Comp& comp = Comp()): comp(comp)
//...

// usage
if(comp(node.key, another_node.key)) {
    // node is considered to be strictly before another_node

您可以使用 std::less作为树的其他用户的合理默认参数，但 map 实现应转发为 map 提供的比较器。

一个完全兼容 STL 的容器也应该支持自定义分配器，为了使之成为可能，内部树结构也必须如此。