集合(Set)
集合
集合是由一些不重复的数据组成的。比如{1,2,3}就是一个有1,2,3三个元素的集合,集合有三个特性:
1.确定性
给定一个集合,任给一个元素,该元素或者属于或者不属于该集合,二者必居其一,不允许有模棱两可的情况出现
2.互异性
一个集合中,任何两个元素都认为是不相同的,即每个元素只能出现一次。有时需要对同一元素出现多次的情形进行刻画,可以使用多重集,其中的元素允许出现多次 。
3.无序性
一个集合中,每个元素的地位都是相同的,元素之间是无序的。集合上可以定义序关系,定义了序关系后,元素之间就可以按照序关系排序。但就集合本身的特性而言,元素之间没有必然的序 。
在C++中我们常用的集合是set
引用set
库
C++中set的实现在一个<set> 的头文件中
,在代码开头引入这个头文件,并加上using namespace std
#include <set>
using namespace std;
构造一个集合
构造 set
集合语句为:set <T> s
。这样我们就定义了一个名为s
的、存储T
类型数据的集合,T
是集合储存的数据类型。初始的时候s
空集合。
插入元素
C++中用insert()
函数向集合中插入一个新的元素。 注意如果插入的元素集合中已经存在了,则插入无效,因为集合有“确定性”
#include <set>
#include <string>
using namespace std;
int main() {
set<string> country; // {}
country.insert("China"); // {"China"}
country.insert("America"); // {"China", "America"}
country.insert("France"); // {"China", "America", "France"}
country.insert("China"); // {"China", "America", "France"}
return 0;
}
删除元素
C++中用erase
函数在集合中删除一个已经存在的元素。 注意如果想要删除的元素在集合中不存在,则删除无效
#include <set>
#include <string>
using namespace std;
int main() {
set<string> country; // {}
country.insert("China"); // {"China"}
country.insert("America"); // {"China", "America"}
country.insert("France"); // {"China", "America", "France"}
country.erase("America"); // {"China", "France"}
country.erase("England"); // {"China", "France"}
return 0;
}
判断元素是否存在
C++中如果你想知道某个元素是否在集合中出现,你可以直接用count()
函数。如果集合中存在我们要查找的元素则返回 1 ,否则会返回 0。
#include <set>
#include <string>
#include <stdio.h>
using namespace std;
int main() {
set<string> country; // {}
country.insert("China"); // {"China"}
country.insert("America"); // {"China", "America"}
country.insert("France"); // {"China", "America", "France"}
if (country.count("China")) {
cout << "China belong to country" << endl;
}
return 0;
}
遍历元素
C++通过迭代器可以访问j集合中的每个元素,迭代器就好像手指指向set
中的某个元素。通过操作这个手指,我们可以改变它指向的元素,通过*
(解引用运算符,不是乘号的意思) 操作可以获取迭代器指向的元素。通过++
操作让迭代器指向下一个元素,同样--
操作让迭代器指向上一个元素。
迭代器的写法比较固定,std <T>::iterator it
就定义了一个指向 set<T>
这种集合的迭代器it
,T
是任意的数据类型。其中::iterator
是固定的写法。
begin
函数返回容器中起始元素的迭代器,end
函数返回容器的尾后迭代器。
如果你不了解迭代器,你只需先记住用法。
#include <set>
#include <string>
#include <iostream>
using namespace std;
int main() {
set<string> country; // {}
country.insert("China"); // {"China"}
country.insert("America"); // {"China", "America"}
country.insert("France"); // {"China", "America", "France"}
for (set<string>::iterator it = country.begin(); it != country.end(); it++) {
cout << *it << endl;
}
return 0;
}
注意,在C++中遍历set
是从小到大的,也就是说set
会帮我们排序的。
清空
C++中调用clear()
函数就可以清空set
,同时会清空set
的内存 。
set小结
在set
中插入、删除、查找某个元素的时间复杂度都是O(logn),并且内部元素有序。
函数 | 功能 | 时间复杂度 |
---|---|---|
insert | 插入一个元素 | O(logn) |
erase | 删除一个元素 | O(logn) |
count | 统计集合中某个元素的个数 | O(logn) |
size | 获取元素个数 | O(1) |
clear | 清空 | O(n) |
set和结构体
set
经常会和结构体来使用,用set
来储存结构体和vector
有些区别。 因为set
在存储数据时会按照默认的数据类型比较规则进行自动排序,而我们自己定义的结构体,set
不知道此类型的比较方式,因此我们要用一种方式来告诉系统怎么比较这个结构体的大小,其中一种方法为运算符重载,我们需要重新定义小于符号。
下面的代码定义了一个重载了小符号的结构体:
struct Node {
int x, y;
bool operator<(const Node &rhs) const {
if (x == rhs.x) {
return y < rhs.y;
} else {
return x < rhs.x;
}
}
};
operator<
表示我们要重载运算符<
,可以看成是一个函数名。rhs
是“right hand side”的简称,有有操作数的意思,这里我们定义为一个const
引用。因为该运算符重载在结构体内部,左操作数就当前调用operator <
的对象。
特别注意,不要漏掉最后的const
。const
函数表示不能对其数据成员进行修改操作,并且const
对象不能调用非const
成员函数,只允许调用const
成员函数。
上面的重载规定了排序方式为,优先按照x
从小到大排序,如果x
相同那么y
再按照从小到大排序。经过了<
的运算符的重载的结构体,我们就可以比较Node
对象的大小了,因此就可以保存在set
了。