面向对象程序设计——set容器の简析

1.set的介绍

• 序列式容器和关联式容器

• 我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系，⽐如交换⼀下，他依旧是序列式容器。

• 顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

• 关联式容器也是⽤来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是⾮线性结构，两个位置有紧密的关联关系，交换⼀下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。set底层是红⿊树，红⿊树是⼀颗平衡⼆叉搜索树。set是key搜索场景的结构

• set的声明如下：

T就是set底层关键字的类型 • set默认要求T⽀持⼩于⽐较，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现仿函数传给第⼆个模版参数

• set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第三个参数

• ⼀般情况下，我们都不需要传后两个模版参数

• set底层是⽤红⿊树实现，增删查效率是，迭代器遍历是⾛的搜索树的中序，所以是有序的

2.set的增删查

2.1插入(insert)

插入接口的介绍

// 单个数据插⼊，如果已经存在则插⼊失败 
pair<iterator,bool> insert (const value_type& val);
// 列表插⼊，已经在容器中存在的值不会插⼊ 
void insert (initializer_list<value_type> il);
// 迭代器区间插⼊，已经在容器中存在的值不会插⼊ 
template <class InputIterator>
void insert (InputIterator first, InputIterator last);

插入接口的使用

set容器在插入后默认是升序存储的，并且无法插入重复的元素，但是可以使用仿函数来传参实现降序，也可以插入一段元素，通常使用ASCII码来进行比较大小

//插入
int main()
{//去重+默认升序排列set<int> s1;s1.insert(2);s1.insert(4);s1.insert(3);s1.insert(2);s1.insert(5);s1.insert(9);//迭代器遍历//set<int, greater<int>>::iterator it = s1.begin();auto it_s1 = s1.begin();while (it_s1 != s1.end()){//*it = 1;---->error//不可以修改cout << *it_s1 << " ";++it_s1;}cout << endl;//去重+使用仿函数降序排列set<int,greater<int>> s2;s2.insert(2);s2.insert(4);s2.insert(3);s2.insert(2);s2.insert(5);s2.insert(9);//迭代器遍历//set<int, greater<int>>::iterator it = s2.begin();auto it_s2 = s2.begin();while (it_s2 != s2.end()){cout << *it_s2 << " ";++it_s2;}cout << endl;//插⼊⼀段initializer_list列表值，已经存在的值插⼊失败set<int> s3;s3.insert({ 2,3,4,5,5,7,9,11 });for (auto e : s3){cout << e << " ";}cout << endl;//插入string类,通过ASCII码的大小来排序set<string> s4;s4.insert({ "zhangsan", "lisi", "wangwu" });for (auto e : s4){cout << e << " ";}cout << endl;return 0;
}

2.2查找(find)

在算法库中的find使用的是遍历查找，时间复杂度是O(N)

set自身的find是符合平衡二叉树的查找，时间复杂度O(logN)

// 算法库的查找 O(N) auto pos1 = find(s.begin(), s.end(), x); // set⾃⾝实现的查找 O(logN) auto pos2 = s.find(x);

查找接口的介绍

// 查找val，返回val所在的迭代器，没有找到返回end() 
iterator find (const value_type& val);
// 查找val，返回Val的个数 
size_type count (const value_type& val) const;

查找接口的使用

1. find接口直接删除

int main()
{//去重+默认升序排列set<int> s;s.insert(2);s.insert(4);s.insert(3);s.insert(2);s.insert(5);s.insert(9);//迭代器遍历//set<int, greater<int>>::iterator it = s.begin();auto it = s.begin();while (it != s.end()){//*it = 1;---->error//不可以修改cout << *it << " ";++it;}cout << endl;int x = 0;cout << "请输入你要查找的数字:";cin >> x;//如果查找不到就会返回迭代器的尾部/*auto pos = s.find(x);if (pos != s.end()){cout << x << "存在" << endl;}else{cout << x << "不存在" << endl;}*/return 0;
}

count函数间接查找

//使用count来间接查找//count可以统计元素出现的次数，如果出现0次就不存在，反之则存在if (s.count(x)){cout << x << "存在" << endl;}else{cout << x << "不存在" << endl;}

2.3删除(erase)

删除接口的介绍

// 删除⼀个迭代器位置的值 
iterator erase (const_iterator position);
// 删除val，val不存在返回0，存在返回1 
size_type erase (const value_type& val);
// 删除⼀段迭代器区间的值 
iterator erase (const_iterator first, const_iterator last);

有关查找区间的迭代器

首先了解一个概念就是迭代器区间通常都是左闭右开的一个范围区间，也就说[a,b)的一个类型，这里的lower_bound与upper_bound可以实现查找一个左闭右开的区间以供操作

// 返回⼤于等val位置的迭代器 
iterator lower_bound (const value_type& val) const;
// 返回⼤于val位置的迭代器 
iterator upper_bound (const value_type& val) const;

删除接口的使用

直接删除并判断是否删除成功

//删除
int main()
{set<int> s;s.insert({ 2,4,5,2,6,8,10,15 });for (auto e : s){cout << e << " ";}cout << endl;//删除最小的元素就删除排序后的首元素s.erase(s.begin());for (auto e : s){cout << e << " ";}cout << endl;//指定删除元素并判断是否删除成功//可以使用erase的返回值统计待删除元素出现的次数来判断是否删除成功int x = 0;cout << "输入你要删除的元素:";cin >> x;int num = s.erase(x);if (num){cout << "删除成功" << endl;for (auto e : s){cout << e << " ";}cout << endl;}else{cout << "删除失败" << endl;for (auto e : s){cout << e << " ";}cout << endl;}return 0;
}

迭代器删除

//删除
int main()
{set<int> s;s.insert({ 2,4,5,2,6,8,10,15 });for (auto e : s){cout << e << " ";}cout << endl;//指定删除元素并判断是否删除成功//可以使用erase的返回值统计待删除元素出现的次数来判断是否删除成功int x = 0;cout << "输入你要删除的元素:";cin >> x;//使用迭代器删除//如果未查找到则直接返回迭代器尾部auto pos = s.find(x);if (pos != s.end()){s.erase(x);cout << "删除成功" << endl;for (auto e : s){cout << e << " ";}cout << endl;}else{cout << "删除失败" << endl;for (auto e : s){cout << e << " ";}cout << endl;}return 0;
}

迭代器区间删除

//迭代器区间删除
int main()
{set<int> s;for (int i = 0; i < 10; i++){s.insert(i * 10);}for (auto e : s){cout << e << " ";}cout << endl;//删除30到60区间的数据//取出 >=30 的迭代器指针，包括30auto low = s.lower_bound(30);//取出 >60 的迭代器指针，不包括60auto up = s.upper_bound(60);s.erase(low, up);for (auto e : s){cout << e << " ";}cout << endl;return 0;
}

3.multiset和set的差异

multiset和set的使⽤基本完全类似，主要区别点在于multiset⽀持值冗余，那么 insert/find/count/erase都围绕着⽀持值冗余有所差异

小tips:中序第一个指的就是从根节点开始以左子树->根节点->右子树的顺序，当在左子树找到符合的值后继续从该值的左子树寻找，直到找不到为止，这时的节点就是中序的第一个

#include<iostream>
#include<set>
using namespace std;
int main()
{// 相⽐set不同的是，multiset是排序，但是不去重 multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };auto it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;// 相⽐set不同的是，x可能会存在多个，find查找中序的第⼀个 int x;cin >> x;auto pos = s.find(x);while (pos != s.end() && *pos == x){cout << *pos << " ";++pos;}cout << endl;// 相⽐set不同的是，count会返回x的实际个数 cout << s.count(x) << endl;// 相⽐set不同的是，erase给值时会删除所有的x s.erase(x);for (auto e : s){cout << e << " ";}cout << endl;return 0;
}

4.代码练习题

4.1两个数组的交集

题目来源：349.两个数组的交集，这里使用set容器充当去重与排序的作用

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> v;set<int> s1;set<int> s2;s1.insert(nums1.begin(),nums1.end());s2.insert(nums2.begin(),nums2.end());auto it1 = s1.begin();auto it2 = s2.begin();while(it1 != s1.end() && it2 != s2.end()){if(*it1 < *it2){it1++;}else if(*it1 > *it2){it2++;}else{v.push_back(*it1);it1++;it2++;}}return v;}
};

4.2环形链表II

题目来源：142.环形链表|| ，这里使用set存储的是链表每个节点，当插入到重复的节点时，该节点就是入环的第一个节点，此时直接返回即可

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head){set<ListNode*> L;ListNode* cur = head;while(cur){if(L.count(cur)){return cur;}else{L.insert(cur);}cur = cur->next;}return nullptr;}
};