YeungYeah 的乱写地

C++ std::set

 Posts  

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

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

性质

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

初始化

集合的初始化有两种形式

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

    set<template,Compare> s;

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

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

比较

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

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

元素的比较需满足对于两个相等的元素a，b有a<b和b<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/返回元素数量

相关文章：