set定义

set翻译为集合,是一个内部自动有序且不含重复元素的容器。在考试中,有可能出现需
要去掉重复元素的情况,而且有可能因这些元素比较大或者类型不是int型而不能直接开散列
表,在这种情况下就可以用set来保留元素本身而不考虑它的个数。当然,上面说的情况也可
以通过再开一个数组进行下标和元素的对应来解决,但是set提供了更为直观的接口,并且加
入set之后可以实现自动排序,因此熟练使用set可以在做某些题时减少思维量。

如果要使用set,需要添加set头文件,即#incldue< set >。除此之外,还需要在头文件下
面加上一句:“using namespace std;”,这样就可以在代码中使用set 了。

单独定义一个set:

set<typename> name;

其定义的写法其实和vector基本是一样的,或者说其实大部分STL都是这样定义的。这
里的typename依然可以是任何基本类型,例如int、double, char、结构体等,或者是STL标
准容器,例如vector、set、queue等。

和前面vector中提到的一样,如果typemime是一个STL容器,那么定义时要记得在 >> 符号之间加上空格,因为一些使用C++11之前标准的编译器会把它视为移位操作,导致编译
错误。下面是一些简单的例子:

set<int> name;
set<double> name;
set<char> name;
set<node> name;//node是结构体的类型

set数组的定义和vector相同:

set<typename> Arrayname[arraySize];

例如:

set<int> a[100];

这样Arrayname[0] - Arrayname[arraySize-1]中的每一个都是一个set容器。

set容器内元素的访问:

set只能通过迭代器(iterator)访问:

set<typename>::iterator it;

typename就是定义set时填写的类型,下面是typename为int和char的举例:

set<int>::iterator it;
set<char>::iterator it;

这样就得到了迭代器it,并且可以通过*it来访问set里的元素。

由于除开vector和string之外的STL容器都不支持(it+i)的访问方式,因此只能通过以下方式枚举:

#include<iostream>
#include<set>

using namespace std;

//常用函数:insert()
//insert(x)可将x插入set容器中,并自动递增排序和去重,时间复杂度O(logN)
int main()
{
	set<int> st;
	
	st.insert(3);//insert(x)将x插入set中
	st.insert(5);
	st.insert(2);
	st.insert(3);
	
	for(set<int>::iterator it = st.begin(); it != st.end(); it++)
	{
		cout << *it << endl;
	}
	return 0;
}

输出结果:

2
3
5

set常用函数

(1)insert()

insert(x)可将x插入set容器中,并自动递增排序和去重,时间复杂度O(logN)

示例在上面。

(2)find()

find(value)返回set中对应值为value的迭代器,时间复杂度为O(logN)

#include<iostream>
#include<set>

using namespace std;

int main()
{
	set<int> st;
	for(int i = 1; i <= 3; i++)
	{
		st.insert(i);
	}
	
	set<int>::iterator it = st.find(2); //在set中查找2,返回其迭代器
	cout << *it << endl;
	
	return 0; 
}

输出结果:

2

(3)erase()

erase()有两种用法:删除单个元素,删除一个区间内所有的元素。

删除单个元素的值有两种方法:

1、st.erase(it),it为所需要删除元素的迭代器,时间复杂度为O(1)

#include<iostream>
#include<set>

using namespace std;

int main()
{
	set<int> st;
	
	st.insert(100);
	st.insert(200);
	st.insert(100);
	st.insert(300);
	
	st.erase(st.find(100)); //利用find()函数找到100,然后用erase删除它 
	st.erase(st.find(200)); //利用find()函数找到200,然后用erase删除它 
	
	for(set<int>::iterator it = st.begin(); it != st.end(); it++)
	{
		cout << *it << endl;
	}
	
	return 0; 
} 

输出结果:

300

2、st.erase(value),value为所需要删除元素的值,时间复杂度为O(logN)

#include<iostream>
#include<set>

using namespace std;

int main()
{
	set<int> st;
	
	st.insert(100);
	st.insert(200);
	
	st.erase(100);
	
	for(set<int>::iterator it = st.begin(); it != st.end(); it++)
	{
		cout << *it << endl;
	}
	
	return 0; 
} 

输出结果:

200

删除一个区间内的所有元素:

st.erase(first,last),first为所需删除区间的起始迭代器,而last则为所需删除区间的末尾迭代器的下一个地址。

#include<iostream>
#include<set>

using namespace std;

int main()
{
	set<int> st;
	
	st.insert(20);
	st.insert(10);
	st.insert(40);
	st.insert(30);
	
	set<int>::iterator it = st.find(30);
	
	st.erase(it,st.end());//删除元素30至set末尾之间的元素,即30和40 
	
	for(it = st.begin(); it != st.end(); it++)
	{
		cout << *it << endl;
	}
	
	return 0; 
}  

输出结果:

10
20

(4)size()

size()用来获取set内元素的个数,时间复杂度为O(1)

#include<iostream>
#include<set>

using namespace std;

int main()
{
	set<int> st;
	
	st.insert(2);
	st.insert(5);
	st.insert(4);
	
	cout << st.size() << endl;//输出set内的元素个数 
	
	return 0; 
}  

输出结果:

3

(5)clear()

clear()用来清空set中所有元素,复杂度为O(N)

#include<iostream>
#include<set>

using namespace std;

int main()
{
	set<int> st;
	
	st.insert(2);
	st.insert(4);
	st.insert(5);
	
	st.clear();
	
	cout << st.size() << endl;
	
	return 0; 
}  

输出结果:

0

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐