从零带你封装 C++ STL 的 map 和 set ——红黑树底层实现全解析

// 颜色枚举，红黑树的"身份证"
enum Color { 
    RED,    // 红色成员
    BLACK   // 黑色成员
};

// 节点：红黑树的基本单元
template <typename T>
struct RBTreeNode {
    T data;               // 数据
    Color color;          // 颜色标记
    RBTreeNode* parent;   // 父节点指针
    RBTreeNode* left;     // 左孩子
    RBTreeNode* right;    // 右孩子

    // 新成员默认是红色的
    RBTreeNode(const T& value) : 
        data(value), 
        color(RED), 
        parent(nullptr), 
        left(nullptr), 
        right(nullptr) {}
};

// 左旋：想象成一个节点向左侧"倒下"
void rotateLeft(RBTreeNode* x) {
    RBTreeNode* y = x->right;  // 找到要"顶替"的节点
    x->right = y->left;         // 调整关系
    
    // 一系列复杂的指针重连接...
    if (y->left != nullptr)
        y->left->parent = x;
    
    // 更新根节点或父节点的子节点
    if (x->parent == nullptr)
        root = y;
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;
    
    y->left = x;
    x->parent = y;
}

template <typename Key, typename Value>
class MyMap {
private:
    RBTree<std::pair<Key, Value>> tree;

public:
    // 插入操作
    void insert(const std::pair<Key, Value>& kvPair) {
        tree.insertUnique(kvPair);
    }

    // 牛逼的下标访问
    Value& operator[](const Key& key) {
        // 如果没有就自动创建
        return tree.findOrInsert(key);
    }
};

template <typename T>
class MyIterator {
private:
    T* ptr;  // 底层指针

public:
    // 构造函数
    MyIterator(T* p) : ptr(p) {}

    // 解引用操作符
    T& operator*() {
        return *ptr;
    }

    // 前置++操作符
    MyIterator& operator++() {
        ++ptr;
        return *this;
    }

    // 比较操作符
    bool operator!=(const MyIterator& other) {
        return ptr != other.ptr;
    }
};

// 词频统计
std::map<std::string, int> wordCount;

// 添加元素
wordCount["hello"] = 10;
wordCount["world"] = 20;

// 遍历
for (const auto& pair : wordCount) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

template <typename Key, typename Value>
class MyMap {
private:
    // 内部红黑树
    RBTree<std::pair<const Key, Value>> tree;

public:
    // 插入操作
    void insert(const std::pair<Key, Value>& kvPair) {
        tree.insertUnique(kvPair);
    }

    // 下标访问操作符
    Value& operator[](const Key& key) {
        // 如果键不存在，自动创建
        return tree.findOrInsert(key);
    }

    // 迭代器支持
    auto begin() { return tree.begin(); }
    auto end() { return tree.end(); }
};

// 去重
std::set<int> uniqueNumbers;
uniqueNumbers.insert(1);
uniqueNumbers.insert(2);
uniqueNumbers.insert(1);  // 不会重复插入

// 查找
auto it = uniqueNumbers.find(2);
if (it != uniqueNumbers.end()) {
    std::cout << "找到元素" << std::endl;
}

std::map<std::string, int> wordFrequency;

void countWords(const std::string& text) {
    std::istringstream iss(text);
    std::string word;
    
    while (iss >> word) {
        wordFrequency[word]++;
    }
}

template <typename Key, typename Value>
class LRUCache {
private:
    std::map<Key, Value> cache;
    std::list<Key> lruList;
    size_t capacity;

public:
    void put(const Key& key, const Value& value) {
        if (cache.size() >= capacity) {
            // 移除最近最少使用的元素
            cache.erase(lruList.front());
            lruList.pop_front();
        }
        
        cache[key] = value;
        lruList.push_back(key);
    }
};