C++中的STL简介
STL的全称是Standard Template Library，中文名为标准模板库。该模板库分为三大部分，主要包含容器、迭代器和算法三部分。本文主要介绍STL中的一些容器。STL中的容器主要分为两大类，一类是序列式容器，另一类是关联式容器。
序列式容器，每个元素均有固定的位置，该位置取决于对容器的类型，与数据的值没有关系。STL提供了三种序列式容器，他们分别式向量(vector), 双端队列(deque), 列表(list)，此外，string 当作一种特殊的序列式容器。
关联式容器，元素的位置取决于特定的排序准则以及元素的值，和插入次序无关。STL提供四种关联式容器，他们分别是集合(set),多重集合(multiset)，映射(map), 和多重映射(multimap)。
序列式容器
起作用类似于C++中的数组，不过该容器解决的问题是能够动态的扩展数组的大小。拥有一段连续的地址空间，且起始地址不变。虽然能够动态扩展数组的大小，但是也带来了很多问题，比如当前数组的空间不够的时候，需要扩展数组的空间，此时将会大大影响程序的效率。同时，对数组中元素进行插入，删除也会带来大量的数据移动，降低了程序的效率。因此该容器适用于对象简单，变化较小，需要频繁的随机访问的场景。
面试中常被问到的一个问题：vector和list的区别。
-
vector是顺序表。可以开辟一段连续的空间，并且支持随机访问，所以他的访问的时间复杂度为O(1).缺点是当需要空间不足的时候，需要申请新的空间，并将原有的元素复制到新的空间。
-
list链表：底层实现是循环双链表，当对大量的数据进行插入删除时，其时间复杂度为O（1），但是由于底层元素没有连续的空间，所以不能实现随机访问。
所以当需要大量的随机访问而不考虑从频繁的插入删除时，推荐使用vector,当需要大量的插入删除时，考虑使用list.
另一个容易问到的问题时vector扩展空间大小的策略。
-
扩充空间不是在原来空间的背后开辟新的空间，而是以原大小的两倍另外配置一块较大的空间，然后将原内容拷贝过去，并释放原空间，一旦引起空间重新分配，原来指向原空间的所有迭代器全部失效。
-
预估vector容器的空间大小，可以避免不必要的空间重新分配。可以使用reserve（）函数提前设定空间的大小。
关于上述申请新空间的证明可以使用以下程序：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include<iostream> #include<vector> using namespace std; int main() { vector<int> a; a.push_back(1); int* addr1 = &a[0]; cout<<addr1<<endl; int i = 1; int cnt = 1; while(true) { i ++; a.push_back(i); int* tmpaddr = &a[0]; if(addr1 != tmpaddr){ cout<<"i = "<<i<<endl; cout<<tmpaddr<<endl; addr1 = tmpaddr; cnt ++; } if(cnt >= 10) { break; } } return 0; } |
以上程序的输出为：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
0x6e1740 i = 2 0x6e1750 i = 3 0x6e1760 i = 5 0x6e1778 i = 9 0x6e17a0 i = 17 0x6e17e8 i = 33 0x6e1870 i = 65 0x6e1978 i = 129 0x6e1b80 i = 257 |
可以看到，每次申请新空间都是进行复制的，而且当空间不够时，都是继续两倍的申请。
vector中的常用方法：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
vect.size() //获取当前向量中元素的个数 vect.empty() // 判断当前向量中是否含有元素 vect.push_back(ele) //向向量的末尾添加元素 vect.insert(iter， ele) //向iter迭代器所指向得地方插入元素 vect.insert(iter) //删除iter指向的元素 vect.swap(iter1, iter2) //交换两个元素 vect.clear() //清空所有的元素 对于元素的访问通常直接使用下标进行访问。也可以使用 vect.at(index)函数，使用函数的方法会进行越界检查 vect.front() //访问第一个元素 vect.back() //访问最后一个元素 vect.begin() //指向开始元素的迭代第 vect.end() //指向最后一个元素的后一个的迭代器 |
deque
双段队列是由一段一段的定量的连续空间组成。一旦要在deque的前端和尾端增加新空间，便配置一段定量的连续空间，串在整个deque的头端和尾端。因此不论尾部和头部安插元素十分迅速。但是在中间插入元素比较费时，必须移动其他元素。deque的最大任务就是在这些分段的连续空间上，维护其整体连续的假象，并提供随机存取的接口
值得注意的是，deque支持随机访问，deque是list和vector折中的方案，兼有list的有点也有vector随机线性访问效率高的优点。
适用于既要关心两端数据的插入和删除，又需要大量的随机访问的情况。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include<iostream> #include<deque> using namespace std; int main() { deque<int> dequeInt; for(int i = 0; i <= 8; i ++) { if(i % 2) { dequeInt.push_back(i); } else { dequeInt.push_front(i); } } for(int i = 0; i <= 8; i ++) { cout<<dequeInt[i]<<endl; } return 0; } |
输出为
|
1 2 3 4 5 6 7 8 9 |
8 6 4 2 0 1 3 5 7 |
list
list的底层是由双向链表实现的，每个元素都是的内存地址不是连续的，通指针来进行数据 访问，这就使得该容器进行随机访问时的效率非常的低，因此该容器没有提供[]操作符的重载，但是由于链表的特点，可以进行高效的插入和删除操作。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include<iostream> #include<list> using namespace std; int main() { list<char> listChar; for(int i = 'a'; i <= 'z'; i ++) { if(i % 2) { listChar.push_back(i); } else { listChar.push_front(i); } } while (!listChar.empty()) { cout<<listChar.front()<<endl; listChar.pop_front(); } return 0; } |
关联式容器
set
故名思意，set实现的就是集合的功能，即该容器中没有重复的元素。除此之外，set底层是使用红黑树来实现的，其内部的元素自动排序，每个元素的值只能出现一次，不允许重复。插入和删除元素的效率都是，使用场景是适用于需要使用到集合这一数据结构且需要排序的场景。multiset的用法和set一样，不同的是multiset允许插入重复的元素。
multiset
multiset，就是集合中可以包含重复的元素，这一性质似乎违背了集合的性质，但是还是有其存在的价值，
map
map实现的是”键值/实值”，每个元素有一个键，是排序准则的基础，每个键只能出现一次，不允许重复。map实现的是一对一映射。multiset的用法和map的用法一致，但允许又重复元素，也就是说multimap可包含多个键值相同的元素。
multimap
multiset，从名字可以看出，其含义是一个key可以对应多个value，但是这样就带来了一些问题，比如对于一个key对应的value们怎么遍历，以及怎么删除等问题，这些问题都在下面的代码中有介绍。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include<map> #include<iostream> using namespace std; typedef multimap<int, string>::iterator iter; void Output(multimap<int, string>& m) { for(iter tmp = m.begin(); tmp != m.end(); tmp ++) { cout<<tmp->first<<" "<<tmp->second<<endl; } } int main() { multimap<int, string> mapStudent; // 增，插入元素 mapStudent.insert(pair<int, string>(0, "00")); mapStudent.insert(pair<int, string>(0, "01")); mapStudent.insert(pair<int, string>(0, "01")); // 注意这里同一个value，插入两次，计数的时候仍然重复计算 mapStudent.insert(pair<int, string>(1, "10")); mapStudent.insert(pair<int, string>(1, "11")); mapStudent.insert(pair<int, string>(2, "20")); mapStudent.insert(pair<int, string>(2, "20")); mapStudent.insert(pair<int, string>(3, "30")); mapStudent.insert(pair<int, string>(4, "40")); // 查 cout<<"key 0 对应的value的个数"<<mapStudent.count(0)<<endl; // 查找相应key对应的value的值 pair<iter, iter> pos = mapStudent.equal_range(0); // 该函数返回的是一个key对应的value们的迭代器 while (pos.first != pos.second) { cout<<pos.first->first<<" "<<pos.first->second<<endl; pos.first ++; } // 使用find函数 cout<<"使用find函数"<<endl; iter tmp = mapStudent.find(0); // find返回的位置貌似是第一个符合条件的iter,然后还想看其他的value，可以参考下面的方法 while(tmp->first == 0) { cout<<tmp->first<<" "<<tmp->second<<endl; tmp ++; } // 还可以查找key位于一个范围中的value们 cout<<"查找key位于一个范围中的value们"<<endl; iter begin = mapStudent.lower_bound(0); iter end = mapStudent.upper_bound(2); for(iter tmp = begin; tmp != end; tmp ++) { cout<<tmp->first<<" "<<tmp->second<<endl; } // 删 mapStudent.erase(1); // 将删除相应key对应的所有pair对 cout<<"删除key 1 对应的所有key-value对"<<endl; Output(mapStudent); // 删除一个key特定的value cout<<"删除key 0 对应的 01"<<endl; pos = mapStudent.equal_range(0); while (pos.first != pos.second) { if(pos.first->second == "01") { mapStudent.erase(pos.first); } pos.first ++; } Output(mapStudent); // 修改第一个 2 对应的20 为 21 // 目前还不了解其对应的排序机制是什么 cout<<"修改第一个2对应的20为21"<<endl; tmp = mapStudent.find(2); tmp->second = "21"; Output(mapStudent); return 0; } |
容器配接器
除了以上7个基本容器类别，为满足特殊需求，STL还提供一些特别的容器配接器，根据基本容器类别实现而成：
stack
栈，对元素满足后进先出的原则。
queue
对元素采取先进先出的原则，也就是说，他是一个普通的缓冲区。
priority_queue
优先队列，也可以理解为堆。容器种的不同元素含有不用的优先权，对于自定义的类型，需要重载比较符号，以及给出排序规则
使用方法参考优先队列的使用方法
默认是大顶堆。
unordered类的容器们
前面介绍的关联式容器底层实现都是依靠红黑树来实现的。unordered_map,unordered_multimap,unordered_set和unordered_multiset底层是依靠HASH函数来实现的。相比于红黑树，使用哈希函数可以快速的查找，但是建立哈希表需要消耗一定的资源。此类容器适用于需要大量查找的场景。