@Author:Runsen
STL 中的栈容器是一种容器适配器。在栈容器中,元素在一端插入并在同一端删除。
stack
为了实现堆栈容器,我们需要在我们的程序中包含头文件<stack> 。
stack容器的一般声明语法是:
stack<objectType> stackNam
下面介绍下STL 中stack容器支持的各种操作。
- push 操作用于在堆栈中插入一个元素。此操作始终在堆栈顶部添加元素。
- pop 操作用于从堆栈中删除元素。移除的元素是栈顶指向的元素。
- top : 返回栈顶元素。
- empty : 检查堆栈是否为空。
- size:返回栈的大小,即栈中元素的数量。
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()函数删除队列的第一个元素。
using namespace std;
// Print the queue
void showq(queue<int> gq)
{
queue<int> g = gq;
while (!g.empty()) {
cout << '\t' << g.front();
g.pop();
}
cout << '\n';
}
// Driver Code
int 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中最后一个元素之后的元素的迭代器。
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 :
KEY VALUE
1 10
2 20
3 30
The map mymap is :
KEY VALUE
1 10
2 10
3 10
unordered_map
unordered_map 是一个关联容器,用于存储由键值和映射值组合形成的元素。map的API 对于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内存要高一点
|