@Author:Runsen
STL 中的栈容器是一种容器适配器。在栈容器中,元素在一端插入并在同一端删除。
stack
为了实现堆栈容器,我们需要在我们的程序中包含头文件<stack>
。
#include<stack>
stack容器的一般声明语法是:
stack<objectType> stackNam
下面介绍下STL 中stack容器支持的各种操作。
push 操作用于在堆栈中插入一个元素。此操作始终在堆栈顶部添加元素。pop 操作用于从堆栈中删除元素。移除的元素是栈顶指向的元素。top : 返回栈顶元素。empty : 检查堆栈是否为空。size:返回栈的大小,即栈中元素的数量。
#include <iostream>#include <stack>using namespace std;int main() {stack<int> stack;stack.push(21);stack.push(22);stack.push(24);stack.push(25);stack.pop();stack.pop();while (!stack.empty()) {cout << ' ' << stack.top();stack.pop();}}
queue
元素添加到队列的后面,而从队列的前面删除。一般来说,队列采用先进先出(FIFO)的排列方式。
要在程序中实现队列容器,我们必须在代码中包含一个头文件<queue>
。
队列支持的各种操作。
empty() – 返回队列是否为空。size() – 返回队列的大小。swap():交换两个队列的内容,但队列的类型必须相同,尽管大小可能不同。emplace():在队列容器中插入一个新元素,新元素被添加到队列的末尾。queue::front() 和 queue::back() – front()函数返回对队列第一个元素的引用。back()函数返回对队列最后一个元素的引用。push(g) 和 pop() – push()函数在队列末尾添加元素“g”。pop()函数删除队列的第一个元素。
#include <iostream>#include <queue>using namespace std;// Print the queuevoid showq(queue<int> gq){queue<int> g = gq;while (!g.empty()) {cout << '\t' << g.front();g.pop();}cout << '\n';}// Driver Codeint main(){queue<int> gquiz;gquiz.push(10);gquiz.push(20);gquiz.push(30);cout << "The queue gquiz is : ";showq(gquiz);cout << "\ngquiz.size() : " << gquiz.size();cout << "\ngquiz.front() : " << gquiz.front();cout << "\ngquiz.back() : " << gquiz.back();cout << "\ngquiz.pop() : ";gquiz.pop();showq(gquiz);return 0;}
map
map是具有键值对的关联容器,因此键值始终是唯一的。map中的键可以插入或删除,但不能更改。另一方面,可以更改与键关联的值。
at 和 [ ]:运算符 at和 [ ] 用于访问map元素。at 和 [] 具有相同的功能,但只有一个区别。如果映射中不存在访问的键,则“at ”运算符会引发异常。而 [ ] 运算符会在映射中不存在访问的键时在map中插入新键。begin : 返回map中第一个元素的迭代器。end:返回指向map中最后一个元素之后的元素的迭代器。
#include <iostream>#include <map>using namespace std;int main(){map<int, int> mymap{{1,10},{2,20},{3,30} };map<int, int> ::iterator it;cout << "\nThe map mymap is : \n";cout << "\tKEY\tVALUE\n";for (it = mymap.begin(); it != mymap.end(); ++it) {cout << '\t' << it->first<< '\t' << it->second << '\n';}cout << endl;mymap.at(2) = 10; mymap[3] = 10; cout << "\nThe map mymap is : \n";cout << "\tKEY\tVALUE\n";for (it = mymap.begin(); it != mymap.end(); ++it) {cout << '\t' << it->first<< '\t' << it->second << '\n';}cout << endl;}
输出如下
The map mymap is :KEYVALUE1 102 203 30The map mymap is :KEYVALUE1 102 103 10
unordered_map
unordered_map 是一个关联容器,用于存储由键值和映射值组合形成的元素。map的API 对于unordered_map 的操作基本相同。
#include <iostream>#include <unordered_map>using namespace std;int main(){unordered_map<string, int> umap;umap["1"] = 10;umap["2"] = 20;umap["3"] = 30;for (auto x : umap)cout << x.first << " " << x.second << endl;}
map和unordered_map的对比:
map 操作的平均时间复杂度为 O(log n) 而对于 unordered_map,平均时间复杂度为 O(1)。
对于查找问题,unordered_map会更加高效一些,因此遇到查找问题,常会考虑一下用unordered_map,但是空间占用上unorder_map要高于map,因为unorder_map占用的内存更加高一点,unorder_map内部采用hash表,map内部采用的是红黑树,内存占有率的问题转化成hash表 VS 红黑树,还是unorder_map内存要高一点