本篇讲的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()