数据结构 - 集合

[TOC]

集合的定义

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

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

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

Set

集合的特性

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

无序性：一个集合中，每个元素的地位都是相同的，元素之间是无序的。
互异性：集合中不存在相同的两个元素，即每个元素都是独一无二的。
确定性：给定一个集合，任给一个元素，该元素或者属于或者不属于该集合，二者必居其一，不允许有模棱两可的情况出现。

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

集合的表示

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

假设 $S$ 是一个集合，其内存在元素 $1$ 、 $2$ 和 $3$ ，则可以表示为： $S = \{1,2,3\}$
其中：
当元素 $a$ 属于集合 $S$ 时，记作： $a \in S$
当元素 $a$ 不属于集合 $S$ 时，记作： $a \notin S$
若集合不包含任何元素，则称之为空集。记作： $S=\emptyset$
若两个集合的元素完全相同，则称这两个集合相等。记作： $A=\{1,2,3\}$ ， $B=\{1,2,3\}$ ，则 $A=B$
若集合 $A$ 中所有的元素，集合 $B$ 中都存在，则称集合 $A$ 是集合 $B$ 的子集。记作： $A=\{1,2\}$ ， $B=\{1,2,3\}$ ，则 $A \subset B$
若集合 $A$ 是集合 $B$ 的子集，即 $A \subset B$ ，且 $A \neq B$ ，则称 $A$ 是 $B$ 的真子集，记作： $A \subseteq B$

集合的操作

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

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

增：对于数据增加（即插入）操作，由于集合具备互异性，因此，插入数据前，需要确保集合中不存在相同的数据，否之，不进行插入。
删：与其他数据结构一样，直接对元素进行删除
改：与其他数据结构一样，直接对元素进行修改
查：与其他数据一样，查找相应元素

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

集合间的运算

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

并集：将两个集合进行相“加”，即将集合间的元素进行合并，得到一个新的集合： $A=\{1\}$ ， $B=\{2,3\}$ ，则 $A \cup B = \{1,2,3\}$
交集：将两个集合进行“与”操作，即将集合中相同的元素提取出来组成一个新的集合： $A=\{1,2\}$ ， $B=\{2,3\}$ ，则 $A \cap B = \{2\}$
差集：将两个集合进行相”减“，即将存在于集合 $A$ ，但不存在于集合 $B$ 中的元素提取出来组成一个新的集合： $A=\{1,2,3\}$ ， $B=\{1,3\}$ ，则 $A \setminus B = \{2\}$ ，也可记作 $A-B = \{2\}$

代码实现

集合（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);

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

参考

集合 (数学)