STL——set(集合)

集合这个名词我们在数学中应该是用的最多的，通俗的讲，集合就是由一些不重复的数据构成的，比如{1，2，3}，就是一个有1，2，3三个元素的集合，在C++的标准模板库中也有这样的一种容器。

首先，如果我们要使用集合，就需要加上头文件：

#include<set>
using namespace std;

构造集合：

C++中直接构造一个set的语句为：set<T> s。这样我们定义了一个名为s的、存储T类型数据的集合，其中T是集合要存储的数据类型。初始化的时候s是空集合。比如set<int> aa，set<string> bbb等等。

插入元素：

C++中用insert()函数向集合中插入一个新的元素。注意如果集合中已经存在了某个元素，那这个插入不会产生任何的效果，集合中是不会出现重复元素的。

#include<set>
#include<string>
using namespace std;
int main()
{
    set<string> country;
    country.insert("China");
    country.insert("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");
    country.insert("America");
    country.insert("France");//{China,America,France}
    country.erase("France"); //删除了France这一元素
    return 0;
}

判断某个元素是否存在

C++中如果你想知道某个元素是否在集合中，可以直接使用count()函数。如果集合中存在我们需要的元素，返回1，否则返回0。

#include<iostream>
#include<set>
#include<string>
using namespace std;
int main()
{
    set<string> country;
    country.insert("China");
    country.insert("America");
    country.insert("France");//{China,America,France}
    country.insert("China"); //{China,America,France} 插入无效
    if(country.count("China"));
        cout<<"China in country"<<endl;
    return 0;
}

遍历元素（迭代器）

如果要访问集合中的每个元素，我们需要用到迭代器，迭代器就好像一根手指指向set中的某个元素（和指针有点像）。通过*（解引用）来获取迭代器指向的元素，通过＋+可以指向下一个元素，--指向上一个元素

迭代器的写法比较固定，set<T>::iterator it 就定义了一个指向set<T>这种集合的迭代器it，T是数据类型。其中::iterator是固定的写法。begin函数返回容器中起始元素的迭代器，end函数返回容器的尾后迭代器

#include<iostream>
#include<set>
#include<string>
using namespace std;
int main()
{
    set<string> country;
    country.insert("China");
    country.insert("America");
    country.insert("France");//{China,America,France}
    country.insert("China"); //{China,America,France} 插入无效
    for(set<string>::iterator it = country.begin() ; it != country.end() ; ++it)
    cout<<*it<<endl;
    return 0;

set总结

set的底层数据结构的实现为红黑树，效率很高，所以在竞赛的时候用的还是蛮多的

函数	功能	时间复杂度
insert	插入一个元素	O(log n)
erase	删除一个元素	O(log n)
count	统计某个元素的个数	O(log n)
size	获取元素个数	O(1)
clear	清空	O(n)