标准模板库

2019-03-13

STL的内容还是蛮多的，在这里对常用的stl和接口进行梳理。

vector

用法：

定义：
    vector<T> vec;

插入元素：
    vec.push_back(element);
    vec.insert(iterator, element);

删除元素：
    vec.pop_back();  //删除最后一个数据
    vec.erase(iterator);
    vec.erase(begin, end); //删除[begin, end]区间的数据

修改元素：
    vec[position] = element;

遍历容器：
    for(auto it = vec.begin(); it != vec.end(); ++it) {......}

排序：
    sort(vec.begin(), vec.end());   //需要添加头文件 #include<algorithm>

查找：
    find(vec.begin(), vec.end(), val);  //如果不存在val，返回vec.end()

其他：
    vec.empty();    //判断是否空
    vec.size();    // 实际元素
    vec.capacity();    // 容器容量
    vec.begin();    // 获得首迭代器
    vec.end();    // 获得尾迭代器
    vec.clear();    // 清空

实现：

模拟Vector实现

线性表，数组实现。
- 支持随机访问。
- 插入删除操作需要大量移动数据。
需要连续的物理存储空间。
每当大小不够时，重新分配内存（*2），并复制原内容。

错误避免：

迭代器失效

插入元素
- 尾后插入：size < capacity时，首迭代器不失效尾迭代实现（未重新分配空间），size == capacity时，所有迭代器均失效（需要重新分配空间）。
- 中间插入：size < capacity时，首迭代器不失效但插入元素之后所有迭代器失效，size == capacity时，所有迭代器均失效。
删除元素
- 尾后删除：只有尾迭代失效。
- 中间删除：删除位置之后所有迭代失效。

map

用法：

定义：
    map<T_key, T_value> mymap;

插入元素：
    mymap.insert(pair<T_key, T_value>(key, value));    // 同key不插入
    mymap.insert(map<T_key, T_value>::value_type(key, value));    // 同key不插入
    mymap[key] = value;    // 同key覆盖，不存在key则插入

删除元素：
    mymap.erase(key);    // 按值删
    mymap.erase(iterator);    // 按迭代器删

修改元素：
    mymap[key] = new_value;
    
查找元素：
	iter = mymap.find(key);
	if (iter != mymap.end()) cout<<"Find, the value is"<<iter->second<<endl;
	else cout<<"Do not find"<<endl;

遍历容器：
      for(auto it = mymap.begin(); it != mymap.end(); ++it) {
        cout << it->first << " => " << it->second << '\n';
        //first与second分别为key与value
      }
      
清空元素：
	mymap.clear();
	mapStudent.erase(mapStudent.begin(), mapStudent.end());

实现：

RBTree实现

树状结构，RBTree实现。
- 插入删除不需要数据复制。
- 操作复杂度仅跟树高有关。
RBTree本身也是二叉排序树的一种，key值有序，且唯一。
- 必须保证key可排序。

基于红黑树实现的map结构（实际上是map, set, multimap，multiset底层均是红黑树），不仅增删数据时不需要移动数据，其所有操作都可以在O(logn)时间范围内完成。另外，基于红黑树的map在通过迭代器遍历时，得到的是key按序排列后的结果，这点特性在很多操作中非常方便。

面试时候现场写红黑树代码的概率几乎为0，但是红黑树一些基本概念还是需要掌握的。

它是二叉排序树（继承二叉排序树特显）：
- 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值。
- 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值。
- 左、右子树也分别为二叉排序树。
它满足如下几点要求：
- 树中所有节点非红即黑。
- 根节点必为黑节点。
- 红节点的子节点必为黑（黑节点子节点可为黑）。
- 从根到NULL的任何路径上黑结点数相同。
查找时间一定可以控制在O(logn)。

红黑树的节点定义如下：

enum Color {
    RED = 0,
    BLACK = 1
};
struct RBTreeNode {
    struct RBTreeNode*left, *right, *parent;
    int key;
    int data;
    Color color;
};

所以对红黑树的操作需要满足两点：1.满足二叉排序树的要求；2.满足红黑树自身要求。通常在找到节点通过和根节点比较找到插入位置之后，还需要结合红黑树自身限制条件对子树进行左旋和右旋。

相比于AVL树，红黑树平衡性要稍微差一些，不过创建红黑树时所需的旋转操作也会少很多。相比于最简单的BST，BST最差情况下查找的时间复杂度会上升至O(n)，而红黑树最坏情况下查找效率依旧是O(logn)。所以说红黑树之所以能够在STL及Linux内核中被广泛应用就是因为其折中了两种方案，既减少了树高，又减少了建树时旋转的次数。

从红黑树的定义来看，红黑树从根到NULL的每条路径拥有相同的黑节点数（假设为n），所以最短的路径长度为n（全为黑节点情况）。因为红节点不能连续出现，所以路径最长的情况就是插入最多的红色节点，在黑节点数一致的情况下，最可观的情况就是黑红黑红排列……最长路径不会大于2n，这里路径长就是树高。

SET

set是关联容器，关联容器中的元素是按关键字来保存和访问的

（顺序容器是按照下标进行访问，关联容器按照键值进行访问）
set元素的键值就是实值，实值就是键值
set中的所有元素都会根据元素的键值自动排序
set不允许两个元素有相同的键值

用法：

初始化：
       set<int> st;        //声明一个int型set
       set<int> st(tmp);   //声明并用tmpset初始化vecset
       set<int> tmp(st.begin(), st.begin() + 3);  //用st的第0个到第2个值初始化tmp
       int arr[5] = {1, 2, 3, 4, 5};   
       set<int> st(arr, arr + 5);      //将arr数组的元素用于初始化vec向量

   插入元素：
       c.insert(elem);       //插入elem

   删除元素：
      st.erase(iterator);    // 按迭代器删
      st.erase(key);         // 按键值删除
       
   查找元素：
   	iter = st.find(elem);
	int c = count(elem);   //返回元素值为elem的个数  
         
   清空元素：
   	st.clear();

交换两个set：
	st.swap(tmp);

遍历元素：
	for (set<int>::iterator it = st.begin(); it! = st.end(); ++it) {
	    cout << ' ' << *it;
	}

其他：
	st.size();      //set的大小
	st.max_size();  //最大容量
	st.empty();     //判空