【C++】set模拟实现

在C++中，set是一个非常常用的关联容器，可以用来存储唯一的元素，并且这些元素会自动按升序排列。在实际工作中，如果我们想要实现类似于set的数据结构，了解其底层实现原理是非常有必要的。下面，我们通过一种简单的方式来模拟set的实现。

基本思想

我们可以通过二叉搜索树（BST）来实现一个简单的set。在这个实现中，我们将支持插入、删除、查找和遍历操作。为了保持元素的唯一性，任何重复的插入都会被忽略。

代码实现

以下是一个简单的Set类的实现，它使用了二叉搜索树作为底层数据结构：

#include <iostream>

template <typename T>
class Set {
private:
    struct Node {
        T data;
        Node* left;
        Node* 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);
        } else if (value < node->data) {
            insert(node->left, value);
        } else if (value > node->data) {
            insert(node->right, value);
        }
        // 重复值不插入
    }

    bool contains(Node* node, T value) {
        if (node == nullptr) return false;
        if (value < node->data) return contains(node->left, value);
        else if (value > node->data) return contains(node->right, value);
        else return true; // 找到了
    }

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

    void clear(Node* node) {
        if (node != nullptr) {
            clear(node->left);
            clear(node->right);
            delete node;
        }
    }

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

    ~Set() {
        clear(root);
    }

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

    bool contains(T value) {
        return contains(root, value);
    }

    void printInOrder() {
        inOrder(root);
        std::cout << std::endl;
    }
};

int main() {
    Set<int> mySet;
    mySet.insert(5);
    mySet.insert(3);
    mySet.insert(7);
    mySet.insert(5); // 重复插入将会被忽略

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

    std::cout << "Contains 3? " << (mySet.contains(3) ? "Yes" : "No") << std::endl;
    std::cout << "Contains 6? " << (mySet.contains(6) ? "Yes" : "No") << std::endl;

    return 0;
}

代码详解

1. Node结构体：我们定义了一个Node结构体，它包含三个成员：存储数据的data，以及指向左右子节点的指针。

2. 插入操作：insert函数接受一个值，如果当前节点为空，则创建一个新节点；如果值小于当前节点的数据，则递归插入到左侧；如果大于，则递归插入到右侧。如果值已存在，什么都不做。

3. 查找操作：contains函数用于查找某个值是否存在，采用递归方式。

4. 按序遍历：inOrder函数用于中序遍历二叉树，以升序输出元素。

5. 内存管理：clear函数用于释放树的内存，防止内存泄漏。

总结

通过这个简单的实现，我们了解了如何用C++语言及基本数据结构来模拟一个set的功能。实际上，C++ STL中的set是基于红黑树实现的，这种树是一种自平衡的二叉搜索树，提供了更高效的性能。在实际开发中，尽量使用标准库提供的功能，只有在特定需求下才考虑自己实现。如果需要扩展，我们还可以添加更多功能，比如删除元素、查找最小值和最大值等。