集合作为一个比较重要的数据结构,具有不含重复元素的性质,在许多算法中实现去重操作时,都需要用到集合这个数据结构。在近来使用c++刷题,用集合踩过较多的坑以后,决定写篇东西记录一下标准库中的集合。
集合一般通过二分搜索树实现。集合内元素保持严格弱序性质
性质
- Associative:元素不是靠决定位置访问的
- Ordered:容器内元素保持严格顺序
- Set:元素的值通过元素的键标识
- Unique keys:元素没有相同的键
初始化
集合的初始化有两种形式
- 直接给出模板类型初始化集合
set<template> s;
- 给出模板类型以及比较对象
1
set<template,Compare> s;
其中Compare类为谓词类,需重载
()
运算符,在其中判断元素顺序
对于基本类型而言,方法1足以解决一起,但是对于自定义结构体,则需进行额外的工作,以帮助集合组织元素以及判断元素是否相同。
比较
额外的工作其实就是两个元素的比较,通过一下两种方式可以实现
- 重载
<
运算符 - 谓词类重载
()
运算符
元素的比较需满足对于两个相等的元素a,b有a<b
和b<a
都不成立。以一个坐标点的结构体为例
|
|
常用成员函数
insert(value)
:插入元素find(value)
:查找元素并返回迭代器,不存在时返回set::end
erase
:取出迭代器位置元素/某值元素count
:返回某元素的数量empty/size
:判断元素数量是否为0/返回元素数量