STL专题-set 集合

本文最后更新于：2021年3月4日 下午

STL中set集合、multiset集合、unordered_set的用法。

set——集合

头文件 #include <map>

  • set，是一种关联式容器，底层使用平衡的搜索树——红黑树实现，插入删除操作时仅仅需要指针操作节点即可完成，不涉及到内存移动和拷贝，所以效率比较高。容器中的数据不能重复，即每个数据都是唯一的，并且会对存进去的数据进行自动升序排序。
  • 此外不能够通过set的迭代器修改set元素的值，因为其本身就是键值，任意改变会破坏set的组织结构。
  • 构造set集合的主要目的是为了快速检索，去重与排序。

set函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
set<T> st; //默认构造函数：

set(const set &st); //拷贝构造函数

set& operator=(const set &st); //重载等号操作符

size(); //返回容器中元素的数目

empty(); //判断容器是否为空

swap(st); //交换两个集合容器

insert(elem); //在容器中插入元素，返回值是对组pair<set<T>::iterator,bool>，bool表示是否插入成功

clear(); //清除所有元素

erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。

erase(beg, end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。

erase(elem); //删除容器中值为elem的元素。

find(key); //查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();

count(key); //统计key的元素个数,set容器为0或者1，multiset可能会大于1

set基本操作

创建set对象

1
2
3
4
5
6
7
set<int> a;	//set<类型> 对象名

set<int,myComp> a;//set<类型，比较结构体或类> 对象名，

set<const set&> //set自带拷贝构造函数

set<类型> a(first,last);//使用[first,last)所指的对象。
  • set容器默认是从小到大进行排序，set<int,myComp> a;可通过这种方式来修改其默认的排序规则。具体实现看：自定义排序那一小节。
  • 对于自定义数据类型的set，必须在模板参数列表这里指定自定义的排序规则，否则编译器不知道该怎么插入。

添加元素 insert

insert(value); 将某一值插入set中，返回值是 pair<set<int>::iterator,bool> ，即返回插入的位置的迭代器以及是否插入成功。

重复的值是不会被插入的，返回的位置是原先元素的位置，同时bool值为false。

find函数

find(const key_type &key)函数用于查找与key值相同的元素，并返回其位置的迭代器。而如果没有找到将会返回end()指向的迭代器。

迭代器

关联式容器不支持iterator+n的操作，n为1也不行，只能使用iter++这种操作。

顺序遍历

1
2
3
4
5
6
set<int> a;
set<int>::iterator iter = a.begin();
for(;iter!=a.end();iter++)
{
    cout<<*iter<<endl;
}

逆序遍历

1
2
3
4
5
6
set<int> a;
set<int>::reverse_iterator iter = a.rbegin();
for(;iter!=a.rend();iter++)
{
    cout<<*iter<<endl;
}

注意迭代器的写法，反向遍历使用reverse_iterator来定义迭代器，函数使用rbegin()与rend()方法！

pair对组

  1. pair对组可以创建成对出现的数据，可以用其来返回一对数据。
  2. pair有两种创建方式，使用默认构造创建或者使用make_pair()函数创建。
  3. 使用.first访问第一个数据，.second访问第二个数据。
1
2
3
4
5
6
7
8
9
10
11
12
13
void test2() {

	//pair对组

	pair<string, int> person1("莫扎特",29);

	cout << person1.first << " " << person1.second << endl;//莫扎特 29

	pair<string, int> person2 = make_pair("哈利波特",33);

	cout << person2.first << " " << person2.second << endl;//哈利波特 33

}

自定义排序

  • 对于自定义数据类型，必须指定其排序规则，否则无法插入。

set容器在判定已有元素a和新插入元素b是否相等时有以下两个步骤。

  1. 将a作为做操作数，b作为右操作数，调用比较函数，并返回比较值。

  2. 将b作为做操作数，a作为右操作数，再调用比较函数，并返回比较值。

也就是说，假设有f(x,y)比较函数，先进行f(a,b)然后再进行f(b,a)，返回两个bool值。

如果返回值都是false，则认为a、b是相等的，b不会被插入。如果第一个是true，第二个是false，则b要排在a后面，繁殖b要排在a前面。如果返回值都是true，则可能发生未知行为。

  1. 自定义比较结构体，重载()操作符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct cmp{	//定义比较类也可以
    bool operator()(const int a,const int b)
    {
        return a>b;//类似于sort算法，这样的‘>’是从大到小
    }
};

int a[] = {1,2,2,45,44,25,35,14,03};
set<int,cmp> i_set(a,a+9);

//遍历
for(set<int>::iterator iter = i_set.begin();iter!=i_set.end();iter++)
{
     cout<<*iter<<" ";
}

//输出结果：45 44 35 25 14 3 2 1
  1. 重载<操作符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Student
{
public:
	Student(string name, int id) :m_name(name), m_id(id) {}
	
	//末尾必须加const，否则二进制“ < ” : 没有找到接受“const _Ty”类型的左操作数的运算符(或没有可接受的转换)
	bool operator<(const Student & another) const	

	{
		if (m_id == another.m_id) return false;
		//表明根据id进行去重
		else return m_id < another.m_id;
		//否则按照id从小到大进行排序
	}

	string m_name;
	int m_id;
};

void test4() {

	Student s0("扶苏", 5);
	Student s1("西施",1);
	Student s2("范蠹", 2);
	Student s3("韩信", 2);
	Student s4("刘邦", 4);

	set<Student> s;

	s.insert(s0);
	s.insert(s1);
	s.insert(s2);
	s.insert(s3);
	s.insert(s4);

	for (set<Student>::iterator it = s.begin(); it != s.end(); it++)
		cout << (*it).m_name << " -- " << (*it).m_id << endl;
}

输出结果：

1
2
3
4
西施 -- 1
范蠹 -- 2
刘邦 -- 4
扶苏 -- 5

可以看到，重复id会被清除，然后按照从小到大的顺序排序。

set与multiset

二者均使用头文件<set>。

但是二者的insert()函数返回值不同，set返回一个对组pair<set<T>::iterator,bool>，而multiset则直接返回插入位置的迭代器。

  • 如果不允许插入重复数据可以利用set。
  • 如果需要插入重复数据利用multiset。

unordered_set 无序集合

头文件：#include <unordered_set>

底层实现：哈希表，插入结果是无序的，而set则会自动排序。

常用api：insert/find/erase，find找到返回迭代器，找不到返回end()。

insert/find/erase的平均复杂度是O(1)，但是最坏复杂度是O(N)的

蓝桥杯真题——错误票据

题目描述：

某涉密单位下发了某种票据，并要在年终全部收回。每张票据有唯一的ID号。全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。

因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。你的任务是通过编程，找出断号的ID和重号的ID。

假设断号不可能发生在最大和最小号。

要求程序首先输入一个整数N(N<100)表示后面数据行数。

接着读入N行数据。

每行数据长度不等，是用空格分开的若干个（不大于100个）正整数（不大于100000）

每个整数代表一个ID号。

要求程序输出1行，含两个整数m n，用空格分隔。

其中，m表示断号ID，n表示重号ID

输入：
要求程序首先输入一个整数N(N<100)表示后面数据行数。

接着读入N行数据。

每行数据长度不等，是用空格分开的若干个（不大于100个）正整数（不大于100000）

每个整数代表一个ID号。

输出：

要求程序输出1行，含两个整数m n，用空格分隔。

其中，m表示断号ID，n表示重号ID

样例输入

2
5 6 8 11 9
10 12 9

样例输出

7 9

问题分析

题目意思很清楚，将会给出一连串被打乱的数字，数字连续，只是有一个数字重复了两次，这个可以使用set中的insert方法，它会返回一个pair(pair中是迭代器与bool值)，通过bool值来进行去重。（见上方insert函数）而找断号的数据进行从头开始遍历判断即可。

另:题目要求输入n行，每行数据不等，采用while(scanf(“%d”,&a)!=EOF)来进行收集数据好一些。

详细参见：蓝桥杯——一些零碎的注意事项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//测试环境 Code::Blocks 17.12
//本代码已经通过了蓝桥杯练习系统的测试
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <set>
using namespace std;
	
int main()
{
    int n,nums;
    int duan,chong;//断的数，重复的数
    cin>>n;//等待输入几行，对于while(scanf("%d",&nums)!=EOF)这种方法来说此数据无意义。
    set<int> i_set;
    set<int>::iterator iter;
    while(scanf("%d",&nums)!=EOF)
    {
        if(i_set.insert(nums).second == false) chong = nums;
    }
    int first = *(i_set.begin());
    int ends = *(--i_set.end());
    iter = i_set.begin();
    for(int i = first;i!=ends;i++)
    {
        if(i == (*iter)-1)
        {
            duan = i;
            break;
        }
        else iter++;
    }
    cout<<duan<<" "<<chong<<endl;
    return 0;
}
C/C++
C++ 蓝桥杯 STL

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！