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函数来实现的。相比于红黑树,使用哈希函数可以快速的查找,但是建立哈希表需要消耗一定的资源。此类容器适用于需要大量查找的场景。