数据结构 - 集合

[TOC]

集合的定义

集合 是现代数学中一个重要的基本概念，维基百科对集合的定义如下：

简单来说，所谓的一个集合，就是将数个对象归类而分成为一个或数个形态各异的大小整体。 一般来讲，集合是具有某种特性的事物的整体，或是一些确认对象的汇集。构成集合的事物或对象称作元素或是成员。集合的元素可以是任何事物，可以是人，可以是物，也可以是字母或数字等。

实际上，集合 是由一组无序但彼此之间又有一定相关性的成员构成的组合。其示意图如下所示：

Set

集合的特性

集合中的元素具备以下一些特性：

• 无序性：一个集合中，每个元素的地位都是相同的，元素之间是无序的。

• 互异性：集合中不存在相同的两个元素，即每个元素都是独一无二的。

• 确定性：给定一个集合，任给一个元素，该元素或者属于或者不属于该集合，二者必居其一，不允许有模棱两可的情况出现。

注：对应于计算机编程中，当我们将集合作为一种数据结构时，我们关注最多的就是集合具备的 互异性。
当我们使用集合时，我们只需往里面扔数据，集合会自动帮我们剔除相同的数据，保证集合中不会存在相同的数据。

集合的表示

集合是一个数学概念，我们可以用相应的数学符号对其进行描述，比如：

• 假设是一个集合，其内存在元素、和，则可以表示为：
  其中：
  当元素属于集合时，记作：
  当元素不属于集合时，记作：

• 若集合不包含任何元素，则称之为空集。记作：

• 若两个集合的元素完全相同，则称这两个集合相等。记作：，，则

• 若集合中所有的元素，集合中都存在，则称集合是集合的子集。记作：，，则

• 若集合是集合的子集，即，且，则称是的真子集，记作：

集合的操作

当把集合应用到计算机编程中作为一种数据结构时，则对集合的操作与其他数据结构本质上没有任何区别：都是对数据进行 增删改查。

只不过对应于集合这种数据结构，其数据操作存在特异性，比如：

• 增：对于数据增加（即插入）操作，由于集合具备互异性，因此，插入数据前，需要确保集合中不存在相同的数据，否之，不进行插入。

• 删：与其他数据结构一样，直接对元素进行删除

• 改：与其他数据结构一样，直接对元素进行修改

• 查：与其他数据一样，查找相应元素

也就是说，集合的操作在插入数据时，与其他数据结构具备差异性。

集合间的运算

可以对集合和集合之间进行运算，集合之间的运算操作主要有如下几种：

• 并集：将两个集合进行相“加”，即将集合间的元素进行合并，得到一个新的集合：，，则

• 交集：将两个集合进行“与”操作，即将集合中相同的元素提取出来组成一个新的集合：，，则

• 差集：将两个集合进行相”减“，即将存在于集合，但不存在于集合中的元素提取出来组成一个新的集合：，，则，也可记作

代码实现

集合（Set） 的底层数据结构可以使用数组或链表，存储实际数据。
前面我们介绍过，集合作为一种数据结构，其数据存储一个最显著的特性就是 互异性，也就是说集合不会存储相同的数据，集合中每个数据都是独一无二的。针对这一个特点，如果选择数组作为底层结构的话，数组的优点是数据获取效率高，集合并没有硬性要求其数据获取效率（当然，如果可能的话，效率自然是越高越好），一个最重要的限制就是数组大小固定，因此在集合数据增多到一定量级时，需要对数组进行动态扩容，多了一些额外需要处理的操作，而使用链表，则不存在这个问题。

因此，下面我们使用基于链表的底层数据结构来实现集合，如下所示：

注：下文中的代码只是用于从底层原理对上层数据结构的实现，未经过严格的单元测试，可能存在严重漏洞，实现上不考虑性能，但着重于理解。

// 头文件：Set.h
#ifndef __SET_H__
#define __SET_H__

#include <iostream>
#include <list>

namespace YN {

    template<typename T>
    class Set {
    public:
        //      typedef typename std::list<T>::iterator iterator;
        //      typedef typename std::list<T>::const_iterator const_iterator;
        typedef std::list<T> base_container;
        typedef typename base_container::iterator iterator;
        typedef typename base_container::const_iterator const_iterator;
    private:
        std::list<T> datas;
    public: // 基本操作  
        // 增
        bool add(const T& data);
        // 删
        void remove(const T& data);
        // 改
        bool update(const T& data);
        // 查
        std::size_t size() const;
        bool contains(const T& data) const;
        const_iterator cbegin() const;
        const_iterator cend() const;

    public: // 集合操作
        // 并集 union  
        Set<T> operator+(const Set<T>& other);
        Set<T>& operator+=(const Set<T>& other);
        // 交集 intersect 
        Set<T> operator&&(const Set<T>& other);
        // 差集 difference
        Set<T> operator-(const Set<T>& other);
    };

}

#endif

// 源文件：Set.cpp
#include "Set.h"
#include <algorithm>

namespace YN {
    template<typename T>
    bool Set<T>::add(const T& data) {
        if (this->contains(data)) {
            return false;
        }
        this->datas.push_back(data);
        return true;
    }

    template<typename T>
    void Set<T>::remove(const T& data) {
        this->datas.remove(data);
    }

    template<typename T>
    bool Set<T>::update(const T& data) {
        if (this->contains(data)) {
            this->remove(data);
        }
        return this->add(data);
    }

    template<typename T>
    std::size_t Set<T>::size() const {
        return this->datas.size();
    }

    template<typename T>
    bool Set<T>::contains(const T& data) const {
        // 使用 std::find 的元素必须具备 operator== 操作符
        return std::find(this->datas.begin(), this->datas.end(), data) != this->datas.end();
    }

    template<typename T>
    typename Set<T>::const_iterator Set<T>::cbegin() const {
        return this->datas.cbegin();
    }

    template<typename T>
    typename Set<T>::const_iterator Set<T>::cend() const {
        return this->datas.cend();
    }

    /*
    * 集合操作：并集（union)
    * 行为：C = A + B
    * return: 一个新的集合
    */
    template<typename T>
    Set<T> Set<T>::operator+(const Set<T>& other) {
        // 创建一个新的集合
        Set<T> set;
        // 添加当前集合元素
        for (Set<T>::const_iterator it = this->cbegin(); it != this->cend(); ++it) {
            set.add(*it);
        }
        // 添加参数集合元素
        for (Set<T>::const_iterator it = other.cbegin(); it != other.cend(); ++it) {
            set.add(*it);
        }
        return set;
    }

    /*
    * 集合操作：并集（union）
    * 行为：A += B
    * return: 返回自身
    */
    template<typename T>
    Set<T>& Set<T>::operator+=(const Set<T>& other) {
        for (Set<T>::const_iterator it = other.cbegin(); it != other.cend(); ++it) {
            this->add(*it);
        }
        return *this;
    }

    /*
    * 集合操作：交集（intersect）
    * 行为：C = A && B
    */
    template<typename T>
    Set<T> Set<T>::operator&&(const Set<T>& other) {
        Set<T> set;
        for (Set<T>::const_iterator it = other.cbegin(); it != other.cend(); ++it) {
            // 如果当前集合包含该元素，就添加到交集中
            if (this->contains(*it)) {
                set.add(*it);
            }
        }
        return set;
    }

    /*
    * 集合操作：差集（difference）
    * 行为：C = A - B（即取出存在于 A，但不存在于 B 的元素）
    */
    template<typename T>
    Set<T> Set<T>::operator-(const Set<T>& other) {
        Set<T> set;
        for (Set<T>::const_iterator it = this->cbegin(); it != this->cend(); ++it) {
            // 集合 other 不包含当前元素
            if (!other.contains(*it)) {
                set.add(*it);
            }
        }
        return set;
    }
}

简单介绍下上述代码：

• 首先，上述代码将集合抽象为数据类型Set，其底层基于链表list

• 然后，我们为集合Set提供了 增删改查 操作，如下所示:

  // 增
  bool add(const T& data);
  // 删
  void remove(const T& data);
  // 改
  bool update(const T& data);
  // 查
  std::size_t size() const;           // 存储元素数量
  bool contains(const T& data) const; // 是否包含元素
  const_iterator cbegin() const;      // 迭代器起始
  const_iterator cend() const;        // 迭代器末尾
  

  其中：调用add添加数据时，会首先判断下添加的数据是否已包含在集合中，若包含则不进行添加，确保集合具备 互异性：

  template<typename T>
  bool Set<T>::add(const T& data) {
      if (this->contains(data)) {
          return false;
      }
      this->datas.push_back(data);
      return true;
  }
  

• 最后，我们还为集合添加了并集，交集和差集操作，这里我们将其行为映射到相应的操作符中，更契合代码设计：

  // 并集 union  
  Set<T> operator+(const Set<T>& other);
  Set<T>& operator+=(const Set<T>& other);
  
  // 交集 intersect 
  Set<T> operator&&(const Set<T>& other);
  
  // 差集 difference
  Set<T> operator-(const Set<T>& other);
  

以上，就完成了一个基本版的集合数据结构。

参考

• 集合 (数学)