在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;
}
代码详解
-
Node结构体：我们定义了一个
Node结构体，它包含三个成员：存储数据的data，以及指向左右子节点的指针。 -
插入操作：
insert函数接受一个值，如果当前节点为空，则创建一个新节点；如果值小于当前节点的数据，则递归插入到左侧；如果大于，则递归插入到右侧。如果值已存在，什么都不做。 -
查找操作：
contains函数用于查找某个值是否存在，采用递归方式。 -
按序遍历：
inOrder函数用于中序遍历二叉树，以升序输出元素。 -
内存管理：
clear函数用于释放树的内存，防止内存泄漏。
总结
通过这个简单的实现，我们了解了如何用C++语言及基本数据结构来模拟一个set的功能。实际上，C++ STL中的set是基于红黑树实现的，这种树是一种自平衡的二叉搜索树，提供了更高效的性能。在实际开发中，尽量使用标准库提供的功能，只有在特定需求下才考虑自己实现。如果需要扩展，我们还可以添加更多功能，比如删除元素、查找最小值和最大值等。
