本篇讲的map/set,其底层是红黑树，红黑树底层是一颗平衡二叉搜索树(具体可看之前的文章—二叉搜索树）。set是key搜索场景下的结构，map是key/value搜索场景下的结构。

2，set系列的使用

2.1,set类的介绍

代码语言：javascript

AI代码解释

template < class T,                        // set::key_type/value_type
           class Compare = less<T>,        // set::key_compare/value_compare
           class Alloc = allocator<T>      // set::allocator_type
           > class set;

set的声明如上，T就是set底层关键字(key)的类型。

set默认要求T是支持比较大小的，如果不支持或者想按自己的比较方式走，可以传仿函数给第二个模板参数。

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

一般情况下是不需要传后两个参数的

set底层是用红黑树实现的，增删查的效率为O(logN),迭代器遍历走的是中序遍历，所以是有序的

2.2,set的构造和迭代器

代码语言：javascript

AI代码解释

//无参构造
explicit set (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());

代码语言：javascript

AI代码解释

//迭代器区间构造
template <class InputIterator>
  set (InputIterator first, InputIterator last,
       const key_compare& comp = key_compare(),
       const allocator_type& = allocator_type());

代码语言：javascript

AI代码解释

//initializer_list列表构造  其中value_type就是关键字key
set (initializer_list<value_type> il,
     const key_compare& comp = key_compare(),
     const allocator_type& alloc = allocator_type());

代码语言：javascript

AI代码解释

//拷贝构造
set (const set& x);

代码语言：javascript

AI代码解释

官方文档示例：

//迭代器是一个双向迭代器 iteratora bidirectional iterator to value_typeconvertible to const_iteratorconst_iteratora bidirectional iterator to const value_type

代码语言：javascript

AI代码解释

//正向迭代器      
       iterator begin() noexcept;
const_iterator begin() const noexcept;    
       iterator end() noexcept;
const_iterator end() const noexcept;

//反向迭代器

代码语言：javascript

AI代码解释

      reverse_iterator rbegin() noexcept;
const_reverse_iterator rbegin() const noexcept;

代码语言：javascript

AI代码解释

      reverse_iterator rend() noexcept;
const_reverse_iterator rend() const noexcept;

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

2.3,set的增删查

//set中的key_type和value_type指的都是关键字key，它的类型是T key_type -> The first template parameter (T) value_type -> The first template parameter (T)

2.3.1,inset插入

// 单个数据插入，如果已经存在则插⼊失败

代码语言：javascript

AI代码解释

pair<iterator,bool> insert (const value_type& val);

// 列表插入，已经在容器中存在的值不会插入

代码语言：javascript

AI代码解释

void insert (initializer_list<value_type> il);

// 迭代器区间插入，已经在容器中存在的值不会插入

代码语言：javascript

AI代码解释

template <class InputIterator>
  void insert (InputIterator first, InputIterator last);

代码示例：

代码语言：javascript

AI代码解释

#include<iostream>
#include<set>
#include <string>
using namespace std;

int main()
{
    //去重+升序排序
    set<int> s;
    //去重+降序排序
    //set<int, greater<int>> s;

    s.insert(5);
    s.insert(2);
    s.insert(7);
    s.insert(5);
    //迭代器遍历
    auto it = s.begin();
    while (it != s.end())
    {
        cout << *it << " ";
        it++;
    }
    cout << endl;
    //重复的值不会插入
    s.insert({ 2,8,3,9 });
    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;
    //按ASCLL码大小比较
    set<string> str = { "sort","insert","add" };
    for (auto& e : str)
        cout << e << " ";
    cout << endl;
    return 0;
}

2.3.2,find+erase

// 查找 val ，返回 val 所在的迭代器，没有找到返回 end()

代码语言：javascript

AI代码解释

iterator  find (const value_type& val);

// 查找 val ，返回 Val 的个数

代码语言：javascript

AI代码解释

size_type count (const value_type& val) const;

// 删除⼀个迭代器位置的值

代码语言：javascript

AI代码解释

iterator  erase (const_iterator position);

// 删除 val ， val 不存在返回 0 ，存在返回 1

代码语言：javascript

AI代码解释

size_type erase (const value_type& val);

// 删除⼀段迭代器区间的值

代码语言：javascript

AI代码解释

iterator  erase (const_iterator first, const_iterator last);

// 返回⼤于等 val 位置的迭代器

代码语言：javascript

AI代码解释

 iterator lower_bound (const value_type& val);

// 返回⼤于 val 位置的迭代器

代码语言：javascript

AI代码解释

iterator upper_bound (const value_type& val);

使用示例1：

代码语言：javascript

AI代码解释

#include<iostream>
#include<set>
#include <string>
using namespace std;
int main()
{
	set<int> s = { 4,2,7,2,8,5,9 };
	for (auto x: s)
	{
		cout << x << " ";
	}
	cout << endl;

	cout << "删除最小值:";
	s.erase(s.begin());
	for (auto x : s)
	{
		cout << x << " ";
	}
	cout << endl;

	int x1 = 2;
	int num = s.erase(x1);
	if (num == 0)
		cout << "x1不存在!" << endl;

	int x2 = 10;
	auto pos = s.find(x2);
	if (pos == s.end())
		cout << "x2不存在" << endl;
	//利用count实现快速查找
	/*if(s.count(x2))
	{
		cout << "x在" << endl;
	}
	else
	{
		cout << "x不存在" << endl;
	}*/
	return 0;
}

使用示例2：

代码语言：javascript

AI代码解释

#include<iostream>
#include<set>
using namespace std;

int main()
{
	set<int> myset;
	for (int i = 1; i < 10; i++)
		myset.insert(i * 10);
	for (auto e : myset)
		cout << e << " ";
	cout << endl;

	//实现查找[itlow,itup]包含[30,60]区间
	//>=30的位置
	auto itlow = myset.lower_bound(30);
	//>60的位置
	auto itup = myset.upper_bound(60);
	//删除这段区间
	myset.erase(itlow, itup);
	for (auto e : myset)
		cout << e << " ";
	cout << endl;
	return 0;
}

2.4,multiset和set的差异

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

代码语言：javascript

AI代码解释

#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;
	//x值可能会有多个，查找中序的第一个
	int x;
	cin >> x;
	auto pos = s.find(x);
	while (pos != s.end() && *pos == x)
	{
		cout << *pos << " ";
		++pos;
	}
	cout << endl;
	//count会返回x的实际个数
	cout << s.count(x) << endl;
	//erase会删除所有的x
	s.erase(x);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

2.5,相关oj题

代码语言：javascript

AI代码解释

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> s;
        ListNode* cur=head;
        while(cur)
        {
            auto it=s.insert(cur);
            if(it.second==false)
            return cur;

            cur=cur->next;
        }
        return nullptr;
    }
};

3，map系列的使用

3.1,map类的介绍

map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型。

map默认要求Key支持比较，如果不支持或者需要的话可以自行实现仿函数传给第⼆个模版参数.

map底层存储数据的 内存是从空间配置器申请的。⼀般情况下，我们都不需要传后两个模版参数

map底层是⽤红⿊树实现，增删查改效率是O(logN),迭代器走的中序遍历。