C++ std::set

集合作为一个比较重要的数据结构,具有不含重复元素的性质,在许多算法中实现去重操作时,都需要用到集合这个数据结构。在近来使用c++刷题,用集合踩过较多的坑以后,决定写篇东西记录一下标准库中的集合。

集合一般通过二分搜索树实现。集合内元素保持严格弱序性质

性质

  • Associative:元素不是靠决定位置访问的
  • Ordered:容器内元素保持严格顺序
  • Set:元素的值通过元素的键标识
  • Unique keys:元素没有相同的键

初始化

集合的初始化有两种形式

  1. 直接给出模板类型初始化集合set<template> s;
  2. 给出模板类型以及比较对象
    1
    
    set<template,Compare> s;
    

    其中Compare类为谓词类,需重载()运算符,在其中判断元素顺序

对于基本类型而言,方法1足以解决一起,但是对于自定义结构体,则需进行额外的工作,以帮助集合组织元素以及判断元素是否相同。

比较

额外的工作其实就是两个元素的比较,通过一下两种方式可以实现

  • 重载<运算符
  • 谓词类重载()运算符

元素的比较需满足对于两个相等的元素a,b有a<bb<a都不成立。以一个坐标点的结构体为例

1
2
3
4
5
6
7
struct Point{
    int x;
    int y
    bool operator <(const Point &p)const {
        return x==p.x?y<p.y:x<p.x;
    }
};

常用成员函数

  • insert(value):插入元素
  • find(value):查找元素并返回迭代器,不存在时返回set::end
  • erase:取出迭代器位置元素/某值元素
  • count:返回某元素的数量
  • empty/size:判断元素数量是否为0/返回元素数量