YeungYeah 的乱写地

C++ std::set

 Posts  

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

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

性质

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

初始化

集合的初始化有两种形式

  1. 直接给出模板类型初始化集合 set<template> s;
    • 集合的排序与去重通过传入的 template 类型的比较运算符进行
  2. 给出模板类型以及比较对象，此时通过比较对象进行元素的比较以进行元素
    • 通过传入重载 () 运算符的谓词类来进行元素顺序的判断，初始化来进行比较
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    struct comp
{
    bool operator()(struct song left,struct song  right)  //重载（）运算符
    {

        if(left.m_id == right.m_id)     //根据 id 去重
            return false;
        else
        {
            if(left.m_hot != right.m_hot)
            {
                return left.m_hot < right.m_hot;      //降序
            }
            else
            {
                return left.m_id > right.m_id;
            }

        }
    }

};
set<template,comp> s;
    • 通过传入函数或 lambda 对象，来进行比较判断。使用这种方法时必须要把函数或 lambda 参数也作为构造函数的参数传入进行初始化，否则程序在插入元素时会出现 crash
    1
2

    auto comp = [](song x, song y){ return x.m_id != y.m_id && ((x.m_hot != y.m_hot && x.m_hot > y.m_hot) ||(x.m_hot==y.m_hot && x.m_id > y.m_id)); };
std::set<song, decltype(comp)> mySet(comp);

对于基本类型而言，方法 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/返回元素数量

相关文章：