本篇讲的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代码解释

官方文档示例：

//迭代器是一个双向迭代器

代码语言：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)