【C++指南】你真的了解map和set吗？【上】
【C++指南】你真的了解map和set吗？【上】
序列式、关联式容器
序列式容器：前文所讲的STL中的string、vector、list、deque、array、forward_list等容器，我们都称为序列式容器，因为它们的逻辑结构是线性序列的，两个位置存储的值之间⼀般没有紧密的关联关系，⽐如交换⼀下，他依旧是序列式容器。
关联式容器：它是用来存储数据的，其逻辑结构通常是非线性结构，并且两个位置有紧密的联系(如二叉搜索树)，只要交换某两个值的位置，它的存储结构就被破坏了。而关联式容器就包括本章节所接触到的map/set系列以及之后的unordered_map/unordered_set系列。(map和set的底层是依赖红黑树，并且set即是我们前文所讲的key搜索场景，map相对应便是Key/Value场景。
set系列的使用
需要注意的是，本章节小编只截取了set中常用的接口(参数类型做了相应删减)，降低学习成本。如需了解更多的接口访问此网站。
构造及迭代器
set类模板 | template<class T,class Compare = less<T>, class Alloc = allocator<T>> |
|---|---|
迭代器区间构造 | set (InputIterator first, InputIterator last) |
拷贝构造 | set (const set& x) |
initializer_list列表构造 | set (initializer_list<T> il) |
正向迭代器 | iterator begin() |
正向迭代器 | iterator end() |
反向迭代器 | reverse_iterator rbegin() |
反向迭代器 | reverse_iterator rend() |
int main()
{
//排序 和 去重
set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(2);
s.insert(4);
set<int>::iterator it = s.begin(); //正向迭代器
//auto it = s.begin();
while (it != s.end()) //正向迭代器
{
cout << *it << " ";
it++;
}
return 0;
}有迭代器，那么就支持范围for
for (auto& e : s)
{
cout << e << " ";
}插入一段initializer_list列表值
set<int> s = { 1,3,1,2,5 };增删查
由于set是序列式容器，并不支持改的操作，因为一旦改动某个结点的值，那么它的存储结构就被破坏了。
插入 | pair<iterator,bool> insert (const T& val) |
|---|---|
initializer_list列表插入 | void insert (initializer_list<T> il) |
迭代器区间插入 | void insert (InputIterator first, InputIterator last) |
删除某位置的值 | iterator erase (const_iterator position) |
删除某个值 | size_t erase (const T& val) |
删除一段迭代器区间的值 | iterator erase(const_iterator first, const_iterator last) |
查找某值 | iterator find (const T& val) |
为什么插入接口的返回值是pair<iterator,bool>，不应该是bool吗？且pair又是什么呢？
- 统一接口：在map系列的容器当中，Key/Value并不像二叉搜索树那样直接封装在树的结构体中，而是封装在pair中，这是因为在查找等情况C++无法做到返回多个值，但通过封装的方式达到返回多个值的目的。
- 所有关联容器（
map、set、unordered_map等）的插入操作遵循相同的返回值约定，降低学习成本。 - pair的封装，表示键值对。
template <class T1, class T2>
struct pair {
T1 first; // 第一个值
T2 second; // 第二个值
};为什么erase的返回值是size_t，不应该是bool吗？(插入失败返回0)
- 同样，这里的目的是为了统一接口，因为在multiset中是支持插入相同的数(即支持冗余)，在删除后可能返回多个数的情况，而set中只能存在0和1的情况，做到了两个类的ease使用同一个函数。
在C++11版本后支持initializer_list列表初始化、插入等，将需要插入的值用{}的方式(多参数隐式类型转换)。
multiset
initializer_list列表构造(可冗余) | multiset (initializer_list<T> il) |
|---|---|
删除某值（包括所有相等的值） | size_t erase (const T& val) |
查找某值(返回迭代器) | iterator find (const T& val) |
查找某值(返回个数) | size_t count (const T& val) const |
由于multiset是支持冗余的版本，导致了一些接口是和set不相同的，部分如上所示。
// 相⽐set不同的是，multiset是排序，但是不去重
multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };
// 相⽐set不同的是，count会返回x的实际个数
cout << s.count(x) << endl;
// 相⽐set不同的是，erase给值时会删除所有的x
s.erase(x);两个数组的交集
需要对两个数组采交集，那么可以先使用set容器对数据去重，然后采用同步算法的思想返回交集。
vector<int> ret;
set<int> s1(nums1.begin(),nums1.end());
set<int> s2(nums2.begin(),nums2.end());
auto cur1=s1.begin(),cur2=s2.begin();
while(cur1!=s1.end()&&cur2!=s2.end())
{
if(*cur1<*cur2) cur1++;
else if(*cur1>*cur2) cur2++;
else
{
ret.push_back(*cur1);
cur1++;
cur2++;
}
}
return ret;环形链表II
在还没学习set系列时，我们采用的是快慢指针的思想解决环形链表的问题。
在这里采用的是set实例化出ListNode*结点指针，只有当两个指针的地址相同时会出现环形的问题。
set<ListNode*> s;
ListNode* cur=head;
while(cur)
{
if(s.count(cur)==0)
{
s.insert(cur);
}
else
return cur;
cur=cur->next;
}
return nullptr;腾讯云开发者
