STL整理之set

转载请注明出处，部分内容引自李煜东《算法竞赛进阶指南》

前置知识： $C++$ 、 $C$ 语言入门

$Set$ 是什么

$Set$ 是 $C++STL$ 中提供的容器， $set$ 是数学上的集合——具有唯一性，即每个元素只出现一次，而 $multiset$ 则是可重集，两者的内部实现是一棵红黑树，它们支持的函数基本相同

$Set$ 的相关操作

头文件

CPP

#include<set>

声明：

像这样：

CPP

set<类型>名称；

比如：

CPP

set<int>s;
set<vector<int> >s;		//vector中提供重载<
set<set<int> >s;	//平衡树嵌套，哈哈
multiset<double>s;

就像其他需要排序的数据类型一样，为一个结构体的

set

，需要重载小于号

CPP

struct node{
    ......;
};
set<node>s;
bool operator <(const node &ai,const node &bi)
{
	return ai.x>bi.x;
}

$set.size()$

统计

set

中元素个数，函数返回一个整形变量，表示

set

中元素个数，时间复杂度O(1)

CPP

用法：名称.size();
eg.
int num=s.size();

$set.empty()$

检查

set

是否为空，返回一个

bool

型变量，1表示

set

为空，否则为非空，时间复杂度

O(1)

CPP

用法：名称.empty();
eg.
if(s.empty())
	cout<<"Myset is Empty."<<endl;

$set.clear()$

清空

set

，无返回值

CPP

用法：名称.clear();
eg.
s.clear();

$set.count(x)$

set

或

multiset

中值为

x

的元素个数，时间复杂度为

O(log n+ans)

CPP

用法：名称.count(x)
eg.
if(!s.count(x))
	ans++;

迭代器

双向访问迭代器，不支持随机访问，支持星号解除引用，仅支持“++”，“--”这两个算术操作

引用和操作：

CPP

set<类型>::iterator it;
eg.
set<int>::iterator it=s.begin();
it++;
it--;

若把

it++

，则

it

将会指向“下一个”元素。这里的下一个是指在

key

从小到大排序的结果中，排在

it

下一名的元素。同理，若把

it--

，则

it

会指向排在上一个的元素

“++”，“--”操作的复杂度均为

O(log n)

遍历 $set$ 及访问其中的元素

CPP

//set
for(set<int>::iterator it=s.begin();it!=s.end();it++)
    cout<<*it<<endl;	//取出这个迭代器指向的元素
//set嵌套
for(set<set<int> >::iterator it=s.begin();it!=s.end();it++)
{
	//首先取出set中嵌套的set
    for(set<int>::iterator rit=(*it).begin();rit!=(*it).end();rit++)
        cout<<*rit<<' ';	//遍历这个set
    cout<<endl;
}

$set.begin()$

返回集合的首迭代器，即指向集合中最小元素的迭代器，时间复杂度为

O(1)

CPP

用法：名称.begin();
eg.
set<int>::iterator it=s.begin();

$set.end()$

返回集合的尾迭代器，众所周知，STL中区间都是左闭右开的，那么

end()

函数返回的迭代器即为指向集合中最大元素的下一个位置的迭代器，因此

--s.end()

才是指向集合中最大元素的迭代器，时间复杂度为

O(1)

CPP

用法：名称.end();
eg.
maxn=*(--s.end());		//取出最大元素

$set.insert(x)$

在

set

中插入元素，返回插入地址的迭代器和是否插入成功的

bool

并成的

pair

，时间复杂度为

O(log n)

PS：

set

在进行插入的时候是不允许有重复的键值的，如果新插入的键值与原有的键值重复则插入无效（

multiset

可以重复）

CPP

用法：名称.insert(set类型);
eg.
s.insert(3);

$set.erase($ 参数 $)$

删除，参数可以是元素或者迭代器，返回下一个元素的迭代器，时间复杂度为

O(log n)

，注意在

multiset

中

s.erase(x)

会删除所有值为

x

的元素

CPP

用法：名称.erase(参数);
eg.
set<int>::iterator it=s.begin();
s.erase(it);
s.erase(3);

$set.find(x)$

在

set

中查找值为

x

的元素，并返回指向该元素的迭代器，若不存在，返回

set.end()

，时间复杂度为

O(log n)

CPP

用法：名称.find(x);
eg.
if(s.find(x)!=s.end())
	cout<<"Have Found!"<<endl;

$set.lower$ $bound(x)/upper$ $bound(x)$

两个神奇的东西，决定把他们放在一块谈一谈

用法与

find

类似，但查找的条件略有不同，时间复杂度

O(log n)

s.lower

bound(x)

表示查找

>=x

的元素中最小的一个，并返回指向该元素的迭代器

s.upper

bound(x)

表示查找

>x

的元素中最小的一个，并返回指向该元素的迭代器

举个例子：

在

set

{

3,5,7,8,13,16

}中

对于在

set

中存在的元素，比如8

s.lower

bound(8)

返回8所在位置的迭代器

s.upper

bound(8)

返回13所在位置的迭代器

对于在

set

中不存在的元素，比如12

两个函数返回的则都是13所在位置的迭代器

特殊地，

对于比

set

中最大的元素大的元素，比如20

两个函数返回的都是

s.end()

文章操作

前置知识： $C++$ 、 $C$ 语言入门

$Set$ 是什么

$Set$ 是 $C++STL$ 中提供的容器， $set$ 是数学上的集合——具有唯一性，即每个元素只出现一次，而 $multiset$ 则是可重集，两者的内部实现是一棵红黑树，它们支持的函数基本相同

$Set$ 的相关操作

头文件

声明：

$set.size()$

$set.empty()$

$set.clear()$

$set.count(x)$

迭代器

双向访问迭代器，不支持随机访问，支持星号解除引用，仅支持“++”，“--”这两个算术操作

遍历 $set$ 及访问其中的元素

$set.begin()$

$set.end()$

$set.insert(x)$

$set.erase($ 参数 $)$

$set.find(x)$

$set.lower$ $bound(x)/upper$ $bound(x)$

举个例子：

特殊地，

相关推荐

评论

STL整理之set

文章操作

前置知识： C++C++C++、CCC语言入门

SetSetSet是什么

SetSetSet是C++STLC++STLC++STL中提供的容器，setsetset是数学上的集合——具有唯一性，即每个元素只出现一次，而multisetmultisetmultiset则是可重集，两者的内部实现是一棵红黑树，它们支持的函数基本相同

SetSetSet的相关操作

头文件

声明：

set.size()set.size()set.size()

set.empty()set.empty()set.empty()

set.clear()set.clear()set.clear()

set.count(x)set.count(x)set.count(x)

迭代器

双向访问迭代器，不支持随机访问，支持星号解除引用，仅支持“++”，“--”这两个算术操作

遍历setsetset及访问其中的元素

set.begin()set.begin()set.begin()

set.end()set.end()set.end()

set.insert(x)set.insert(x)set.insert(x)

set.erase(set.erase(set.erase(参数)))

set.find(x)set.find(x)set.find(x)

set.lowerset.lowerset.lowerbound(x)/upperbound(x)/upperbound(x)/upperbound(x)bound(x)bound(x)

举个例子：

特殊地，

相关推荐

评论

前置知识： $C++$ 、 $C$ 语言入门

$Set$ 是什么

$Set$ 是 $C++STL$ 中提供的容器， $set$ 是数学上的集合——具有唯一性，即每个元素只出现一次，而 $multiset$ 则是可重集，两者的内部实现是一棵红黑树，它们支持的函数基本相同

$Set$ 的相关操作

$set.size()$

$set.empty()$

$set.clear()$

$set.count(x)$

遍历 $set$ 及访问其中的元素

$set.begin()$

$set.end()$

$set.insert(x)$

$set.erase($ 参数 $)$

$set.find(x)$

$set.lower$ $bound(x)/upper$ $bound(x)$