STL模版 -- day02

一、deque 双端队列容器

• 头文件 #include < deque >

• 是下标顺序容器，它允许在首尾两端快速地插入、删除数据

• deque的元素不是全部相邻存储的：采用单独分配的固定大小数组的序列存储数据，以及额外的登记表(中控数组)，该表中记录了所有序列的地址，这表示通过下标访问元素时必须经过两次指针解引用，vector只需要一次

• deque支持随机访问，效率依然是O(1)

• deque的存储也可以按需自动扩展、收缩，并且deque的扩展比vector更优，因为不设计到原内存复制、销毁环节

  • vector扩容，先申请一块更大的新内存，把原内存数据拷贝，释放原内存

  • deque扩容，只需要申请一块新的固定大小的序列，记录到中控数组即可

• deque比vector多push_front\pop_front操作，并且效率也能O(1)

• vector比deque多个reserve预分配内存，因为deque不需要预分配内存来节约时间

• deque的优点：

  • 与vector相比，头部插入、删除时，不需要搬运后序元素，效率特别高(O(1));在扩容时，也不需要移动、释放原内存，只需操作中控数组即可

  • 与list相比，底层依然是连续空间，空间利用率更高，支持随机访问O(1)

• deque的缺点：

  • 没有vector和list那么极致，随机访问的速度比vector慢(vector是真正的连续空间)；中间位置的插入、删除没有list快，list根本不需要扩容

  • 不适合遍历，因为在遍历时deque的迭代器需要频繁地检查是否移动到了某个序列的末尾，并且需要解两次引用，效率低

  • 因此当需要线性容器时，大多数情况下优先考虑vector、list，deque的应用不多(stack\queue)

二、stack 栈容器(适配器)

• 头文件 #include < stack >

• 底层由deque实现的

• 不支持运算符，没有迭代器，只有无参构造、拷贝构造

• empty、push、pop、top、size

三、queue 队列容器(适配器)

• 头文件 #include < queue >

• 底层由deque实现的

• 不支持运算符，没有迭代器，只有无参构造、拷贝构造

• empty\push\pop\front\back\size

四、priority_queue 优先队列容器(适配器)

• 头文件 #include < queue >

• 底层采用vector实现，当数据入队时，会对数据进行调整成堆结构，默认是大顶堆，元素越大，优先级越高，越先出队

• 注意：存储的元素必须支持 < 运算符，如果是类类型数据必须重载<运算符

• 注意：只能查看top

• 如何调整优先队列的优先级：(小顶堆)

  • 元素取反存入、取出取反

  • 类类型数据重载 < 运算符，调整<运算符的比较过程

  • 固定语法

    • priority_queue<类型,vector<类型>,greater<类型> > 队列名;

      • // 升序

    • priority_queue<类型,vector<类型>,less<类型> > 队列名;

      • // 降序

五、关联性容器（有序）

• 关联性容器可以实现快速查找(O(logn))的容器
• 线性容器中array、vector、list、deque都可以使用全局find进行顺序查找(O(n))，必须支持operator==比较
• 底层实现 红黑树

六、set 集合容器

• 头文件 #include < set >

• 集合容器，底层采用红黑树实现，特点元素不能重复，会自动对数据进行排序，它存储的元素必须支持 < 运算符，只能使用迭代器遍历

• 默认下是按照 operater< 运算符进行比较

• 为什么不是使用 operator== 来比较？

  • 二叉排序树的规则：左小于根、根小于右，如果相等插入失败，==无法判断大小

  • a == b 可以使用 !(a<b || b<a) 替代

• 构造函数：只有无参、拷贝构造

• 支持的运算符：与list一致，不支持随机访问

• 常用成员函数：

  iterator insert( iterator i, const TYPE& val );
  //功能：向set中添加val，i位置意义不大
  void insert( input_iterator start, input_iterator end );
  //功能：想set添加一组[start,end)数据
  pair<iterator,bool> insert( const TYPE& val );
  //功能：向set中添加val
  //返回值：返回键值对pair<添加的位置,是否添加成功>
  
  size_type count( const key_type& key );
  //功能：查看key在set中有几个，要么0要么1
  
  iterator find( const key_type& key );
  //功能：查找set中key的元素的位置，并返回该位置的迭代器
  //如果找不到key，返回end()位置的迭代器
  
  pair<iterator, iterator> equal_range(const key_type& key );
  //功能：查看key在set中的范围，并返回该范围组成的键值对，在set中意义不大
  
  void erase( iterator pos );
  void erase( iterator start, iterator end );
  size_type erase( const key_type& key );
  //功能：删除值为key的元素，成功返回1 失败返回0
  
  key_compare key_comp() const;
  //功能：返回一个用于比较set中元素的函数对象，该对象属于set
  set<int>::key_compare cmp = s.key_comp();
  cmp(int,int);//第一个"小"，则为真
  
  value_compare value_comp() const;
  //    在set中等同于 key_comp
  
  iterator lower_bound( const key_type& key );
  //功能：返回一个大于或等于key的最小的元素的迭代器
  iterator upper_bound( const key_type& key );
  //功能：返回一个大于key的最小的元素的迭代器
  

七、multiset 多重集合容器

• 头文件 #include < set >

• 元素可以重复，也会对元素自动进行排序，元素必须支持<运算符，只能用迭代器遍历

• size_type count( const key_type& key );
  //功能：计算有几个key
  pair<iterator, iterator> equal_range(const key_type& key);
  //功能：返回值为key的元素的范围
  

八、map 映射容器

• 头文件 #include

• 有序键值对容器，是由key/value组成的元素(键值对、字典)pair，要求key不能重复，一个key只能对应一个值，会根据key进行排序，因此key必须支持 < 运算符

• 一般map中存储一些经常需要查找的数据，因为map的查找速度极快，set速度也不慢，但是map比set多一个value来进行描述，redis内存数据库中使用键值对存储数据

• key和value一一对应，可以根据key来访问value，底层采用红黑树根据key来进行组织、管理，查找效率很高

• //构造函数：
  map( iterator start, iterator end );
  //功能：使用一组数据(pair类型)构造
  map( iterator start, iterator end,const key_compare& cmp );
  //功能：使用一组数据(pair类型)构造，并提供key的比较函数
  map( const key_compare& cmp );
  //功能：提供key的比较函数构造
  //支持的运算符：
          //[] 支持通过key作为下标访问元素的value
          //既可以用于访问，当key不存在时，也可以用于插入数据<key,value>，如果key存在，则修改value
              m[key] = value; //  添加、修改
              m[key]; //  key不存在，添加key-value value使用无参构造或者默认值0
              m[key]; //  key存在，访问对应的value
          //成员函数 at(key) 也可以用于访问、修改key的value，但是当key不存在时会抛出异常out_of_range
  //常用成员函数：
  iterator insert( iterator i, const TYPE& pair );
  void insert( input_iterator start, input_iterator end );
  pair<iterator,bool> insert( const TYPE& pair );
  

九、multimap 多重映射容器

• 头文件 #include

• 使用方式与map几乎类似

• 不同的是它的key可以对应多个不同的value，因此不能支持[]运算符

• 一些成员函数：count、equal_range 就变得有意义

• 通过迭代器删除元素需要注意的问题：

  • 对于关联性容器(set\multiset\map\multimap)，删除当前iterator会仅仅使得当前iterator失效，其余位置没有变化，因此在erase时只需要递增iterator即可依次删除，因为底层是红黑树，某个节点删除不会影响其它节点的位置

    • map.erase(it++);

  • 对于线性容器(vector\deque\stack\queue\priority_queue)，删除当前iterator后，后序所有的iterator失去原来意义，因为使用的是连续内存，删除一个，后面所有元素都重新移动，iterator不能递增删除，只能通过重新接收erase的返回值，获取新的当前iterator继续删除

    • it = vector.erase(it);

  • list 两种方式都可以

十、bitset 位集合容器

• 头文件 #include < bitset >

• 是一种封装了各种位操作的类类型数据结构

• !=, ==, &=, ^=, |=, ~, <<=, >>=, []

• 成员函数：

• any(); //有任意一位是1，返回真
  count(); //统计二进制位是1的位数有几位
  flip(); //所有二进制位取反\指定的二进制位取反
  none(); //全部位没有一个是1，返回真
  reset(); //全部二进制位置0\指定二进制位置0
  set(); //全部二进制位置1\指定二进制位置val=1
  size(); //获取位数
  test(); //访问指定的二进制位的值
  to_string(); //把所有二进制位转stirng类型
  to_ulong(); //把所有二进制位转unsigned long类型,C++不常用，但是对于嵌入式软件编程会比较方便去设置二进制位
  

• 常考面试题：

  • vector与list的区别？

  • 指针与迭代器的区别？

  • STL中哪些容器底层采用红黑树？为什么？