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;
}