set的基本用法 和 底层简单了解

在前面，已经了解过搜索二叉树了，也了解了一点红黑树的内容（不太了解的可以先查看前面的内容哦）；现在我们了学习一下，底层以红黑树实现，遍历以搜索树的中序实现的set/multset；

序列式容器和关联式容器
 

我们先来了解一下，什么是序列式容器？什么是关联式容器？

序列式容器：

• STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器
• 逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系；（比如交换⼀下，他依旧是序列式容器）
• 顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

关联式容器：

• 关联式容器有map/set系列和unordered_map/unordered_set系列。
• 关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，比如交换⼀下，他的存储结构就被破坏了。
• 顺序容器中的元素是按关键字来保存和访问的。
   

set类的介绍

• set的声明如下，T就是set底层关键字的类型（可以把T 当作key）

• set默认要求T支持小于比较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数

• set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第三个参数。⼀般情况下，我们都不需要传后两个模版参数。
• set底层是⽤红⿊树实现，增删查效率是 ，迭代器遍历是⾛的搜索树的中序，所以是有序的。O(logN)
• 前⾯部分我们已经学习了vector/list等容器的使⽤，STL容器接⼝设计，⾼度相似，所以这⾥我们就可以直接看⽂档进行了解，然后挑较重要的接⼝进⾏研究；set - C++ Reference (cplusplus.com)

set的构造和迭代器

1. set的⽀持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是⼆叉搜索树，迭代器遍历⾛的中序；
2. ⽀持迭代器就意味着⽀持范围for，set的iterator和const_iterator都不⽀持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。

// empty (1) ⽆参默认构造
explicit set (const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
// range (2) 迭代器区间构造
template <class InputIterator>
set (InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& = allocator_type());
// copy (3) 拷⻉构造
set (const set& x);
// initializer list (5) initializer 列表构造
set (initializer_list<value_type> il,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
// 迭代器是⼀个双向迭代器
iterator -> a bidirectional iterator to const value_type
// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

set的增删查
 

这里需要注意的地方，

• pair，这是一个类似于模板函数的东西，现在先简单了解一下，map时才能更深入的理解
• erase 和 count 当它们 的参数都是 value 时，返回值是 是运行后的对应value的个数；（虽然看着返回值不是1就是0，但这两个接口主要是为了于multiset对接。 ） 

• iterator find (const value_type& val); 不是遍历查找，是利用搜索树，时间复杂度是O （logN）   （set自带的find 比 std::find  O(N) 效率要高；） 
• iterator lower_bound (const value_type& val) const;返回的是 小与等于 val的值的迭代器
• iterator upper_bound (const value_type& val) const；返回的 大于 val的值的迭代器；
• lower_bound与 upper_bound设计的很巧妙，因为我们都知道，删除earse 删除的内容是参数 的左闭右开；lower返回小于等于 upper返回大于正好能满足；

• insert也能实现下列的构造 利用initializer_list 的插入；无非就是对有名参数，无名参数不同还有对临时对象的理解；

主要需要了解的接口：

// 单个数据插⼊，如果已经存在则插⼊失败
pair<iterator,bool> insert (const value_type& val);
// 列表插⼊，已经在容器中存在的值不会插⼊
void insert (initializer_list<value_type> il);
// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
template <class InputIterator>
void insert (InputIterator first, InputIterator last);
// 查找val，返回val所在的迭代器，没有找到返回end()
iterator find (const value_type& val);
// 查找val，返回Val的个数
size_type count (const value_type& val) const;
// 删除⼀个迭代器位置的值
iterator erase (const_iterator position);
// 删除val，val不存在返回0，存在返回1
size_type erase (const value_type& val);
// 删除⼀段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);// 返回⼤于等val位置的迭代器
iterator lower_bound (const value_type& val) const;
// 返回⼤于val位置的迭代器
iterator upper_bound (const value_type& val) const

multiset和set的差异

 multiset和set的使⽤基本完全类似，主要区别点在于multiset⽀持值冗余，那么insert/find/count/erase都围绕着⽀持值冗余有所差异，具体参看下⾯的样例代码理解。

int main()
{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给值时会删除所有的xs.erase(x);for (auto e : s){cout << e << " ";} cout << endl;return 0;
}

这里实现主要注意的点就是erese了，mltiset的erase 是删除全部的value； 

 还有multiset的find，相⽐set不同的是，x可能会存在多个，find查找中序的第⼀个；

若要手动实现的话，可以用递归 也可以使用 循环的方法；

或许现在看来若把相同的值都放到右子树看起来十分方便，是一流是相同值；但是后面学到旋转就知道，旋转后还是需要递归，循环方法找中序第一个值

set的降维打击

数据结构初阶阶段，我们通过证明⼀个指针从头开始走⼀个指针从相遇点开始走，会在入口点相遇，理解证明都会很嘛烦。这⾥我们使用set查找记录解决非常简单方便，这里体现了set在解决⼀些问题时的价值，完全是降维打击。

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/linked-list-cycle-ii/数据结构初阶阶段：

 

class Solution {
public:ListNode *detectCycle(ListNode *head) {struct ListNode* slow = head;struct ListNode* fast = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;if(slow == fast){while(head != fast){head = head->next;fast = fast->next;}return head;}}return NULL;}
};

降维打击

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* cur = head;set<ListNode*> s1;while(cur){auto ret = s1.insert(cur);if(ret.second == false)return cur;cur = cur->next;}return NULL;}
};