C++简单集合类的实现方法

什么是集合类？

集合类是数据结构中的一种，用来存储一组相同类型的数据项。集合类可以快速的对其中的数据进行添加、删除、查找、排序等操作。在C++中，STL中的集合类就是其中之一。

集合类实现原理

在实现一个集合类时，我们可以使用数组、链表、哈希表等数据结构。不过，在这里我们使用了一个常用的数据结构：红黑树。

红黑树是一种自平衡二叉搜索树，常用于实现Map和Set等集合类。它保证了每个节点的左右子树高度相差不超过1，从而使得树的深度不会过深，查询的效率高。同时，红黑树的插入和删除操作比较简单，保证了代码的可维护性。

集合类实现步骤

1. 定义集合类
   ```cpp
   template
   class SimpleSet;

template
class SimpleSetIterator;

template
class SimpleSet {
private:
struct Node {
T key;
Node left;
Node right;
bool color; // 记录节点颜色，0为黑色，1为红色
};

     Node* root;
     int count;

  public:
     SimpleSet();
     ~SimpleSet();

     bool insert(const T& key);
     bool remove(const T& key);
     bool contains(const T& key);
     int size() const;

     void clear();

     SimpleSetIterator<T>* iterator();

};
``
其中，SimpleSet是集合类的主要实现，SimpleSetIterator`是集合类的迭代器，用来遍历集合中的所有元素。

1. 实现构造函数和析构函数
   ```cpp
   template
   SimpleSet::SimpleSet() : root(nullptr), count(0) {}

template
SimpleSet::~SimpleSet() {
clear();
}
``
构造函数和析构函数都比较简单，构造函数初始化了根节点和元素数量，析构函数调用了clear()`函数进行内存的释放。

1. 实现插入和删除操作
   ```cpp
   template
   bool SimpleSet::insert(const T& key) {
   bool flag = false; // flag表示是否插入成功
   Node newNode = new Node {key, nullptr, nullptr, 1};
   if (root == nullptr) { // 根节点为空
   root = newNode;
   root->color = 0; // 根节点为黑色
   count++;
   flag = true;
   } else {
   Node curr = root;
   Node* parent = nullptr;
   while (curr != nullptr && curr->key != key) {
   parent = curr;
   if (curr->key > key) curr = curr->left;
   else curr = curr->right;
   }

    if (curr == nullptr) {  // 插入到叶子节点
       if (parent->key > key) parent->left = newNode;
       else parent->right = newNode;
       newNode->color = 1;  // 新节点为红色
       count++;
       flag = true;
    }
   

   }
   return flag;
   }

template
bool SimpleSet::remove(const T& key) {
bool flag = false;
Node curr = root;
Node parent = nullptr;

  while (curr != nullptr && curr->key != key) {
     parent = curr;
     if (curr->key > key) curr = curr->left;
     else curr = curr->right;
  }

  if (curr == nullptr) {  // 未找到要删除的节点
     return flag;
  } else if (curr->left != nullptr && curr->right != nullptr) {  // 被删除的节点同时具有左右孩子
     Node* temp = curr->right;
     while (temp->left != nullptr) temp = temp->left;
     curr->key = temp->key;  // 把右子树中的最小值替换为当前节点
     curr = temp;  // 记录当前节点，变为左子树中的情况
     parent = curr;
  }

  Node* child;
  if (curr->left != nullptr) child = curr->left;
  else child = curr->right;

  if (curr->color == 0 && child != nullptr) {  // 黑色叶子节点，判断其孩子色是否为红
     if (child->color == 1) {
        child->color = 0;  // 孩子节点变为黑色
        flag = true;
     } else {
        flag = fixUp(child, parent);  // 修正红黑树，返回是否删除节点
     }
  } else if (curr->color == 1 && child != nullptr) {  // 带一个红色孩子节点的黑色节点
     child->color = 0;  // 把孩子节点变为黑色
     flag = true;
  } else if (curr->color == 0 && child == nullptr) {  // 黑色叶子节点无孩子节点
     flag = fixUp(curr, parent);  // 修正红黑树，返回是否删除节点
  } else {  // 带一个空孩子节点的黑色节点
     flag = true;
  }

  if (flag) {  // 删除当前节点，更新元素数量和父节点指针
     if (parent == nullptr) root = child;
     else if (parent->left == curr) parent->left = child;
     else parent->right = child;
     if (child != nullptr) child->color = 0;  // 处理删除节点的颜色和父节点指针
     count--;
     delete curr;
  }

  return flag;

}
```
插入操作先判断根节点是否为空，然后使用循环判断要插入的值在红黑树中的位置。如果找到，则不再插入；否则，将新节点插入到叶子节点上，并保证红黑树的性质。这里要注意：插入节点的颜色必须为红色，否则会破坏红黑树的平衡性。

删除操作则比较复杂。删除一个节点后，红黑树需要进行颜色调整和结构调整。具体的实现方式是：对于红色节点的删除操作会让树保持平衡，不需做其他调整；而对于黑色节点的删除则可能导致红黑树的平衡被破坏，需要进行一些复杂调整。

1. 实现查找和遍历操作
   ```cpp
   template
   bool SimpleSet::contains(const T& key) {
   Node* curr = root;
   while (curr != nullptr && curr->key != key) {
   if (curr->key > key) curr = curr->left;
   else curr = curr->right;
   }

   if (curr == nullptr) return false;
   else return true;
   }

template
int SimpleSet::size() const {
return count;
}

template
void SimpleSet::clear() {
while (root != nullptr) {
remove(root->key);
}
}

template
SimpleSetIterator SimpleSet::iterator() {
SimpleSetIterator iter = new SimpleSetIterator(root);
return iter;
}
``
查找操作使用循环遍历查找要查找的节点，如果找到就返回true；如果遍历到末尾都未能找到，则说明该节点不存在，返回false`。

遍历操作需要使用迭代器来进行实现，这里使用了前序遍历方式，包含了元素的递增排序。

示例说明

示例一：插入操作

SimpleSet<int> mySet;
mySet.insert(1);
mySet.insert(5);
mySet.insert(3);
mySet.insert(4);

以上代码演示了如何插入4个数字到集合中。插入操作会将数字逐个插入到集合中，如果在集合中已经有相同的数字，则不再重复插入。插入操作被设计成bool类型，如果插入成功则返回true，否则返回false。

示例二：遍历操作

SimpleSetIterator<int>* iter = mySet.iterator();
while (iter->hasNext()) {
   cout << iter->next() << " ";
}

以上代码演示了如何遍历集合中的所有数字。需要先创建一个迭代器，然后调用hasNext()函数检查是否还有下一个元素，如果有则调用next()函数取出下一个元素。遍历的顺序是按数字大小递增排序的。