移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——13.map&&set（模拟实现）

在 C++ 中，map 和 set 是非常常用的 STL（标准模板库）容器，它们在存储数据时提供了高效的查找、插入和删除操作。不过，了解它们的内部实现原理有助于我们更深入地掌握 C++。本文将通过模拟实现 map 和 set 的基本功能，给出代码示例并进行详细说明。

一、set 的实现

set 是一种不允许重复元素的集合，通常基于红黑树或其他自平衡二叉搜索树来实现。这里，我们用简单的二叉搜索树进行模拟实现。

#include <iostream>

template<typename T>
class Set {
private:
    struct Node {
        T data;
        Node *left, *right;

        Node(T value) : data(value), left(nullptr), right(nullptr) {}
    };

    Node *root;

    void insert(Node *&node, T value) {
        if (node == nullptr) {
            node = new Node(value);
            return;
        }
        if (value < node->data) {
            insert(node->left, value);
        } else if (value > node->data) {
            insert(node->right, value);
        }
        // 如果 value == node->data，则不插入，保持集合的唯一性
    }

    void inorder(Node *node) {
        if (node) {
            inorder(node->left);
            std::cout << node->data << " ";
            inorder(node->right);
        }
    }

public:
    Set() : root(nullptr) {}

    void insert(T value) {
        insert(root, value);
    }

    void display() {
        inorder(root);
        std::cout << std::endl;
    }
};

在以上代码中，我们定义了一个简单的 Set 类，包含了插入元素和中序遍历（用于显示元素顺序）的方法。关键在于 insert 方法的逻辑，确保不插入重复的元素。

二、map 的实现

map 是一对键值对的集合，允许通过键高效地查找对应的值。我们同样可以用二叉搜索树来模拟实现。每个节点存储一个键值对。

#include <iostream>
#include <utility>

template<typename K, typename V>
class Map {
private:
    struct Node {
        K key;
        V value;
        Node *left, *right;

        Node(K k, V v) : key(k), value(v), left(nullptr), right(nullptr) {}
    };

    Node *root;

    void insert(Node *&node, K key, V value) {
        if (node == nullptr) {
            node = new Node(key, value);
            return;
        }
        if (key < node->key) {
            insert(node->left, key, value);
        } else if (key > node->key) {
            insert(node->right, key, value);
        } else {
            // 如果 key 已存在，更新值
            node->value = value;
        }
    }

    V* find(Node *node, K key) {
        if (node == nullptr) return nullptr;
        if (key < node->key) {
            return find(node->left, key);
        } else if (key > node->key) {
            return find(node->right, key);
        } else {
            return &node->value; // 找到了，返回值的地址
        }
    }

public:
    Map() : root(nullptr) {}

    void insert(K key, V value) {
        insert(root, key, value);
    }

    V* find(K key) {
        return find(root, key);
    }
};

在 Map 类中，插入元素时会根据键的大小关系将数据放置在树的相应位置。同样，我们实现了一个 find 方法来查找键对应的值。

使用示例

int main() {
    Set<int> mySet;
    mySet.insert(5);
    mySet.insert(3);
    mySet.insert(8);
    mySet.insert(5); // 重复插入，不会生效

    std::cout << "Set contains: ";
    mySet.display(); // 应该输出: 3 5 8

    Map<std::string, int> myMap;
    myMap.insert("apple", 1);
    myMap.insert("banana", 2);
    myMap.insert("orange", 3);
    myMap.insert("apple", 4); // 更新值

    std::string key = "apple";
    int *value = myMap.find(key);
    if (value) {
        std::cout << key << ": " << *value << std::endl; // 输出: apple: 4
    } else {
        std::cout << key << " not found." << std::endl;
    }

    return 0;
}

总结

以上是对 C++ 中 set 和 map 的基本模拟实现。虽然代码相对简单，功能也未必完整，但这提供了对其内部机制的基本认识。真实的 STL 实现会更加复杂，涉及内存管理、迭代器、异常处理等，深入研究可以帮助我们写出更高效和安全的代码。