C++小舜老师布置了一份挺好玩的作业：在C++中利用面对对象的思想实现一种数据类型——集合。（STL中自带了set数据类型，可参考其函数原型）

造轮子的作业最喜欢了，造轮子可谓是提高姿势水平的必经之路。（尽管这个轮子可能不太好用？）

由于数据结构与算法的知识空缺，也没有参考巨佬们的实现，可能使用了开销很大的实现方法。

下面略提一下实现思路，注释已经十分详细：
集合的第一大特点，集合中不能有重复的元素，考虑用add()函数，在每一次添加内容时检查是否有重复元素，检查时若采用线性查找，时间复杂度为O(n)，遂采用哈希表存储是否存在某个元素。STL中自带了map，底层用红黑树实现，查找复杂度为O(logN)。
关于输出交集、差集、并集和对称差集，全部采用哈希表的查找，逻辑上理解没有难度。
存储上采用动态存储，参考了《Thinking in C++》第四章的CStash。

需要注意的是类模板的使用：类模板在使用时如果采用了声明与实现分离的模式，在main函数中实例化时将发生链接错误，原因是链接时main函数找不到类中的实现，或者说其还没有被实例化。当编译器面对声明与实现分开的两份文件时会出现这种情况。
解决方法有像我这样直接include 实现cpp文件，不过好像不是很美观。
下面引用CSDN上的解决方法：

• 方法一：把  template 定义式放到其声明语句所在的头文件中。面对前例，我们可以在  myfirst.hpp  最后一行加入： #include "myfirst.cpp" 
• 方法二：在用到该template  的每一个 .C文件中  #include "myfirst.cpp"。
• 方法三：完全丢开  myfirst.cpp，把声明和定义全部放进  myfirst.hpp。

CppSet.h:

//
// Created by Zilin Xiao on 2019-05-08.
//
#include <iostream>
#include <cassert>
#include <map>

const int increment = 100;
using namespace std;

template <class itemtype>

class CppSet{
public:
    CppSet(); // at this time CppSet only supports single data type
    int add(const itemtype* item); // add an element into a set
    void* clear(); // remove all elements of a set
    void* fetch(int index);
    CppSet shallow_copy();
    int len(); // return the size of a set
    void print_set();
    CppSet difference(const CppSet& src); // return all elements included in this set but not in src
    CppSet intersection(const CppSet& src); // return all elements included in both this set and src
    bool isdisjoint(const CppSet& src); // return a bool value indicating
                                // whether this set and src have any same elements
    bool issubset(CppSet& src); // return a bool value indicating whether this set is a subset of src
    bool issuperset(CppSet& src); // return a bool value indicating whether this set is a superset of src
    CppSet symmetric_difference(CppSet& src); // return the symmetric difference of both sets
    CppSet Union(CppSet& src); // return the union of both sets
    friend ostream& operator <<(ostream&,CppSet&);
    itemtype&operator [](int i);

private:
    int size; // size of each element
    int quantity; // size of current storage space
    int next; // next empty space
    unsigned char* storage; // Dymatically allocated array of bytes
    map<itemtype,bool> flag; // whether an element is included in the set

    // functions for inflating are as below
    void inflate(int increase);
};

CppSet.cpp:

//
// Created by Zilin Xiao on 2019-05-09.
//

#include "CppSet.h"
using namespace std;

template <class itemtype>

CppSet<itemtype>::CppSet() {
    size = sizeof(itemtype);
    quantity = 0;
    storage = 0;
    next = 0;
}

template <class itemtype>

int CppSet<itemtype>::len() {
    return next;
}

template <class itemtype>
void CppSet<itemtype>::inflate(int increase) {
    assert(increase>0);
    int newQuantity = quantity + increase;
    int newBytes = newQuantity * size;
    int oldBytes = quantity * size;
    unsigned char* b = new unsigned char[newBytes];
    for (int i = 0; i < oldBytes; ++i) {
        b[i] = storage[i];
    }
    delete []storage;
    storage = b;
    quantity = newQuantity;
}

template <class itemtype>
int CppSet<itemtype>::add(const itemtype* item) {
//    for (int j = 0; j < next; ++j)
//        if (item == *fetch(j))
//            return -1;
//    linear complexity
    if (flag.find(*(itemtype*)item)!=flag.end())
        return -1;

    if(next>=quantity) // if full storage
        inflate(increment);

    flag[*(itemtype*)item] = true;

    int startBytes = next * size;
    unsigned char* e = (unsigned char *) item;
    for (int i = 0; i < size; ++i) {
        storage[startBytes + i] = e[i];
    }
    next++;
    return (next-1);
}


template <class itemtype>

void *CppSet<itemtype>::clear() {
    if (storage!=0){
        printf("Freeing storage...");
        delete []storage;
    } else
        return NULL;
}

template <class itemtype>

void* CppSet<itemtype>::fetch(int index) {
    assert(index >= 0);
    if(index>=next)
        return NULL; // indicating access out of boundary
    return &(storage[index*size]);
}


template <class itemtype>
CppSet<itemtype> CppSet<itemtype>::difference(const CppSet& src) { // elements included in A
    CppSet<itemtype> difference;
    for (int i = 0; i < next; ++i) {
        if (src.flag.find(*(itemtype *)fetch(i))==src.flag.end()){
            difference.add((itemtype *)fetch(i));
        }
    }
    return difference;
}

template <class itemtype>
CppSet<itemtype> CppSet<itemtype>::intersection(const CppSet& src){
    CppSet<itemtype> intersection;
    for (int i = 0; i < next; ++i) {
        if (src.flag.find(*(itemtype *)fetch(i))!=src.flag.end()){
            intersection.add((itemtype *)fetch(i));
        }
    }
    return intersection;
}

template <class itemtype>
bool CppSet<itemtype>::isdisjoint(const CppSet &src) {
    for (int i = 0; i < next; ++i) {
        if(src.flag.find(*(itemtype *)fetch(i))!=src.flag.end())
            return false;
    }
    return true;
}

template <class itemtype>
bool CppSet<itemtype>::issubset(CppSet &src){
    for (int i = 0; i < next; ++i) {
        if (src.flag.find(*(itemtype *)fetch(i))!=src.flag.end())
            continue;
        else
            return false;
    }
    return true;

}

template <class itemtype>
bool CppSet<itemtype>::issuperset(CppSet &src) {
    return src.issubset(*this);     //  if A is a subset of B, then B is a superset of A
}

template <class itemtype>
CppSet<itemtype> CppSet<itemtype>::symmetric_difference(CppSet &src) {
    // elements that are only included in A or B
    CppSet<itemtype> symmetric_difference;
    map<itemtype,bool> flag_for_sd;
    for (int i = 0; i < next; ++i) {
        if (src.flag.find(*(itemtype *)fetch(i))!=src.flag.end()) { // A's elements included in B
            flag_for_sd[*(itemtype *)fetch(i)]= true;   // exists in both sets, set a flag to avoid repeat access
            continue;
        }
        else{
            symmetric_difference.add((itemtype *)fetch(i));
        }
    }
    for (int j = 0; j < src.len(); ++j) {
        if (!flag_for_sd[*(itemtype *)(fetch(j))]) // find no match
            if (flag.find(*(itemtype *)(src.fetch(j)))==flag.end()){
                symmetric_difference.add((itemtype *)src.fetch(j));
            }
    }
    return symmetric_difference;
}

template <class itemtype>
CppSet<itemtype> CppSet<itemtype>::Union(CppSet &src) {
    CppSet<itemtype> Union;
    for (int i = 0; i < next; ++i)
        Union.add((itemtype *)fetch(i));
    for (int j = 0; j < src.len(); ++j)
        Union.add((itemtype *)(src.fetch(j)));
    return Union;
}

template <class itemtype>
void CppSet<itemtype>::print_set() {
    for (int i = 0; i < next; ++i)
        cout<<"Index:"<<i<<" Content:"<<*(itemtype *)(fetch(i))<<endl;
    cout<<"-------------"<<endl;
}

template<class itemtype>
CppSet<itemtype> CppSet<itemtype>::shallow_copy(){
    return *this;
}

template<class itemtype>
ostream &operator<<(ostream &output, CppSet<itemtype> &set) {
    for (int i = 0; i < set.len(); ++i) {
        output<<"Index:"<<i<<" Content:"<<*(itemtype *)(set.fetch(i))<<endl;
    }
    return output;
}

template<class itemtype>
itemtype &CppSet<itemtype>::operator[](int i) {
    return *(itemtype *)(fetch(i));
}

CppSettest.cpp:

//
// Created by Zilin Xiao on 2019-05-10.
//
#include "CppSet.cpp"

int main(){
    CppSet<float> set1,set2;
    for (float i = 0; i < 10; ++i)
        set1.add(&i);
    for (float j = 0; j < 7; ++j) {
        set2.add(&j);
    }
    printf("set1 length:%d, set2 length:%d\n",set1.len(),set2.len());
    cout<<"Indexing Testing..."<<set1[0]<<endl;
    CppSet<float> set3(set2);
    CppSet<float> set4 = set2.shallow_copy();
    set3.print_set();
    set4.print_set();
    CppSet<float> intersection = set1.intersection(set2);
    CppSet<float> difference = set1.difference(set2);
    CppSet<float> Union = set1.Union(set2);
    CppSet<float> sym = set1.symmetric_difference(set2);
    printf("Intersection:\n");
    intersection.print_set();
    printf("Difference:\n");
    difference.print_set();
    printf("Union:\n");
    Union.print_set();
    printf("Symmetric Difference:\n");
    sym.print_set();
    set1.clear();
    set2.clear();
    intersection.clear();
    difference.clear();
    Union.clear();
    return 0;
}