红黑树下探玄机：C++ setmultiset 的幕后之旅

一、关联式容器

二、键值对

三、set

四、set的构造

五、set的iterator

六、set的Operations

七、multiset

一、关联式容器

序列式容器：

在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等
底层为线性序列的数据结构，里面存储的是元素本身

关式容器联：

也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高

二、键值对

键值对：用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息

使用场景：
现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义

pair的结构

template<class T1,class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;pair()
:first(T1())
,second(T2())
{}pair(const T1& a,const T2& b)
:first(a)
,second(b)
{}
};

三、set

T: set中存放元素的类型，实际在底层存储<value, value>的键值对
Compare：set中元素默认按照小于来比较
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

在使用set中，set相当于只存一个值，在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的，且set是按照一定次序存储元素的容器

在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序，set中的元素按一定次序排序，且元素唯一，元素不能在set中被修改 (元素总是const) ，只能被插入或删除，set在底层是用二叉搜索树(红黑树)实现的

注意记忆的点：

set中只放value，但在底层实际存放的是由<value, value>构成的键值对
set中插入元素时，只需要插入value即可，不需要构造键值对pair
set中的元素不可以重复(因此可以使用set进行去重)
使用set的迭代器遍历set中的元素，可以得到有序序列
set中的元素默认按照小于来比较
set中查找某个元素，时间复杂度为：log2(N)

四、set的构造

empty : set的无参的构造
range :使用一段迭代器区间构造
copy :拷贝构造

operator=

#include <iostream>
#include <set>using namespace std;int main()
{set<int> s1;int arr[] = { 9,8,7,6,5,4,3 };set<int> s2(arr, arr + sizeof(arr) / sizeof(arr[0]));set<int> s3(s2);s1 = s2;return 0;
}

五、set的iterator

返回第一个元素的iterator

返回最后一个元素的iterator

#include <iostream>
#include <set>
using namespace std;
int main()
{int arr[] = { 9,8,7,6,5,4,3 };set<int> s2(arr, arr + sizeof(arr) / sizeof(arr[0]));set<int>::iterator it = s2.begin();set<int>::iterator it1 = s2.end();while (it != it1){cout << *it << " ";it++;}return 0;
}

判断set是否为空

返回set的元素个数

single element : 插入一个key（val）返回一个键值对pair，在pair中第一个数据first是插入位置的迭代器，第二个位置是->是否插入成功，set中的key值不能重复且只能有一个，如果key值已经有了，那么返回的是原key位置的迭代器以及false，如果key值没有，那么返回的是新插入key位置的迭代器以及true，由于return不能返回两个值，所以如果想返回多个值，必须放在一个结构中进行返回，这里是放在了键值对pair中进行返回
with hint : 在一个迭代器位置插入一个key（val）,传入的这个iterator 位置对于编译器来说只是一个建议位置，实际插入数据还是根据其原有的二叉搜索树的逻辑 (有序) 进行插入
range : 是插入一段迭代器区间

#include <iostream>
#include <set>
using namespace std;
int main()
{int arr[] = { 9,8,7,6,5,4,3 };set<int> s2;s2.insert(arr, arr + sizeof(arr) / sizeof(arr[0]));set<int>::iterator it=s2.insert(s2.begin(), 2);cout << *it << endl;pair<set<int>::iterator, bool> pa = s2.insert(9);cout << *(pa.first) << " "<<pa.second << endl;return 0;
}

void erase : 删除某个 iterator
size_ t erase : 删除某个key值，返回值是删除的这个key值的个数 , 返回的个数这是为了后面的 multiset 做准备，因为multiset可以允许有多个相同的key值，而set和mulitset的关联性很大，所以为了接口的统一性将这里的删除值为key的erase的操作的返回值设置为了返回删除key值的个数，在set中当有这个key值的时候删除对应的节点成功返回1，当没有这个key值的时候删除对应节点失败返回 0
void erase : 删除一段迭代器区间

#include <iostream>
#include <set>
using namespace std;
int main()
{int arr[] = { 9,8,7,6,5,4,3 };set<int> s2;s2.insert(arr, arr + sizeof(arr) / sizeof(arr[0]));s2.erase(s2.begin());size_t ret = s2.erase(8);cout << ret << endl;s2.erase(s2.begin(), s2.end());return 0;
}

swap是交换两个set对象的数据

#include <iostream>
#include <set>
using namespace std;
int main()
{int arr[] = { 9,8,7,6,5,4,3 };set<int> s2;s2.insert(arr, arr + sizeof(arr) / sizeof(arr[0]));set<int> s3;s3.swap(s2);return 0;
}

清空set的所有元素

#include <iostream>
#include <set>
using namespace std;
int main()
{int arr[] = { 9,8,7,6,5,4,3 };set<int> s2;s2.insert(arr, arr + sizeof(arr) / sizeof(arr[0]));s2.clear();return 0;
}

六、set的Operations

find是查找一个元素的iterator，如果没有查找到那么返回end()iterator
set的底层是红黑树，在二叉搜索数的基础上进行了平衡，所以成员函数find的查找效率高为O(logN)，，库里也有find，由于库里的是给出区间遍历查找，时间复杂度为O(N) ，所以单独提供了find

#include <iostream>
#include <set>
using namespace std;
int main()
{int arr[] = { 9,8,7,6,5,4,3 };set<int> s2;s2.insert(arr, arr + sizeof(arr) / sizeof(arr[0]));cout << *(s2.find(9)) << endl;return 0;
}

count是返回key值对应的个数，同样是为了和multiset保持接口的一致性，multiset允许多个key值存在，所以当myltiset调用count的时候可能key值对应的个数会有多个，为了set和multiset接口的统一性，我们给set也提供一个count接口，count接口在set中可以用于判空

#include <iostream>
#include <set>
using namespace std;
int main()
{int arr[] = { 9,8,7,6,5,4,3 };set<int> s2;s2.insert(arr, arr + sizeof(arr) / sizeof(arr[0]));cout << s2.count(7) << endl;return 0;
}

lower_bound是下界（>=）的意思，即寻找比给定key值等于大于的值的位置的迭代器，有等于优先是等于，其次是大于，如果找不到那么返回end()

upper_bound（>）是上界的意思，即寻找比给定key值大的值的位置的迭代器，如果找不到那么返回end()

lower_bound和upper_bound通常是搭配使用，用于寻找指定区间的迭代器（前闭区间，后开区间），通常要使用erase或insert插入一段区间，对区间进行操作，那么就会用到这两个函数

erase:

#include <iostream>
#include <set>
using namespace std;
int main()
{int arr[] = { 9,8,7,6,5,4,3 };set<int> s2;s2.insert(arr, arr + sizeof(arr) / sizeof(arr[0]));set<int>::iterator it1 = s2.lower_bound(5);// >=5set<int>::iterator it2 = s2.upper_bound(6);// >6// erase: [5 ,6 ) ,删除掉 5 和6  s2.erase(it1, it2);for (auto e : s2){cout << e << endl;}return 0;
}

equal_range的意思是相等的范围，即去寻找和key值相等序列的开头和结尾位置的迭代器，同理，这里同样是为了和multiset保持接口的一致性，即multiset中可以有多个相同的key值，即使用equal_range去找key值会找到的是一段序列
返回的pair中第一个iterator 是和key值相等序列的开头位置的iterator , 第二个是结尾位置的迭代器
如果给equal_range的key值，在set中没有，那么会返回比key值大的位置的迭代器作为开头位置的迭代器和结尾位置的迭代器进行返回，举例set数据序列为1，5，7，那么传入查找3作为key值进行查找，3没有，那么就会找比key值3大的值的迭代器即5位置的迭代器作为开头和结尾位置的迭代器，那么就会返回[5,5)，那么由于成员函数对序列区间进行操作是前闭区间后开区间，那么[5,5)这个序列就相当于不存在的区间，如果比key值（key值不存在set的数据序列中）大的位置的值都没有那么会返回end()作为开头和结尾的位置的迭代器即[end(),end())，即如果给equal_range的key值不存在，那么equal_range会返回一个不存在的区间

七、multiset

multiset与set 的唯一不同是multiset中可以有多个相等的key值
multiset的其它性质和set类似

#include <iostream>
#include <set>
using namespace std;
int main()
{int arr[] = { 9,8,7,6,5,4,3,8,7,6,5,4,3,8 };multiset<int> s2;s2.insert(arr, arr + sizeof(arr) / sizeof(arr[0]));for (auto e : s2){cout << e <<" ";}cout << endl;return 0;
}

multiset的count

#include <iostream>
#include <set>
using namespace std;
int main()
{int arr[] = { 9,8,7,6,5,4,3,8,7,6,5,4,3,8 };multiset<int> s2;s2.insert(arr, arr + sizeof(arr) / sizeof(arr[0]));cout << s2.count(9);cout << endl;cout << s2.count(7) << endl;return 0;
}

multiset的erase

与set不同的是，multiset删除key值，如果key值有多个，那么会将多个相同的key值同时删除

#include <iostream>
#include <set>
using namespace std;
int main()
{int arr[] = { 9,8,7,6,5,4,3,8,7,6,5,4,3,8 };multiset<int> s2;s2.insert(arr, arr + sizeof(arr) / sizeof(arr[0]));s2.erase(4);for (auto e : s2){cout << e << " ";}return 0;
}

multiset的find

与set不同的是，multiset的find的key值可能会有对应的多个相等的key值，那么find会返回迭代器遍历（中序遍历）中的第一个key值位置的迭代器

#include <iostream>
#include <set>
using namespace std;
int main()
{int arr[] = { 9,8,7,6,5,4,3,8,7,6,5,4,3,8 };multiset<int> s2;s2.insert(arr, arr + sizeof(arr) / sizeof(arr[0]));set<int>:: iterator it = s2.find(7);//找到第一个7cout << *(it) << endl;it++;cout << *(it) << endl;//是按有序的排列，第一个7后面也是7  ，说明是第一个7return 0;
}