关键词

C++ stack容器适配器详解

在 C++ 中,容器适配器是一种特殊的容器类,它实际上不是自己存储数据,而是依赖于其它的容器,例如 vector、list、deque 等。

简单理解,容器适配器就是对现有容器进行了一次封装(包装),在容器的使用上做了更严格的规定,又或者进行了扩展。

本节要讲的 stack 就是 C++ 标准库提供的一个容器适配器。默认情况下,stack 底层使用的是 deque 容器,deque 容器允许从两端插入、删除元素,且提供了迭代器可以遍历元素;stack 只允许从一端插入、删除元素,它没有提供迭代器,不支持直接遍历元素。

stack容器适配器的创建

stack 本质是一个模板类,定义在<stack>头文件中。

默认情况下,stack 底层是用 deque 实现的:
template <class T, class Container = deque<T> > class stack;
可以看到 template 的第二个参数 Container 默认指定的是 deque。除了 deque 之外,stack 的底层还可以指定用 vector 和 list 容器实现。

构造 stack 容器的方式有多种,包括:

1) 创建一个不包含任何元素的 stack 适配器,并采用默认的 deque 基础容器:
std::stack<int> values;
上面这行代码,就成功创建了一个可存储 int 类型元素,底层采用 deque 基础容器的 stack 适配器。

2) 上面提到,stack<T,Container=deque<T>> 模板类提供了 2 个参数,通过指定第二个模板类型参数,我们可以指定 vector 或者 list 作为 stack 的底层容器。
std::stack<std::string, std::list<int>> values;

3) 可以用一个基础容器来初始化 stack 适配器,只要该容器的类型和 stack 底层使用的基础容器类型相同即可。例如:
std::list<int> values {1, 2, 3};
std::stack<int,std::list<int>> my_stack (values);
注意,初始化后的 my_stack 适配器中,栈顶元素为 3,而不是 1。另外在第 2 行代码中,stack 第 2 个模板参数必须显式指定为 list<int>(必须为 int 类型,和存储类型保持一致),否则 stack 底层将默认使用 deque 容器,也就无法用 lsit 容器的内容来初始化 stack 适配器。

4) 还可以用一个 stack 适配器来初始化另一个 stack 适配器,只要它们存储的元素类型以及底层采用的基础容器类型相同即可。例如:
std::list<int> values{ 1, 2, 3 };
std::stack<int, std::list<int>> my_stack1(values);
std::stack<int, std::list<int>> my_stack=my_stack1;
//std::stack<int, std::list<int>> my_stack(my_stack1);
可以看到,和使用基础容器不同,使用 stack 适配器给另一个 stack 进行初始化时,有 2 种方式,使用哪一种都可以。

stack容器适配器的使用

stack 容器不提供迭代器,任何元素的进出都必须符合先进后出的规则,每次只能使用栈顶元素,而且也没有办法遍历整个容器中的内容。

下表列出了操作 stack 容器的常用成员函数。

表 1 stack容器适配器支持的成员函数
成员函数 功能
empty() 当 stack 栈中没有元素时,该成员函数返回 true;反之,返回 false。
size() 返回 stack 栈中存储元素的个数。
top() 返回一个栈顶元素的引用,类型为 T&。如果栈为空,程序会报错。
push(const T& val) 先复制 val,再将 val 副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。
push(T&& obj) 以移动元素的方式将其压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
pop() 弹出栈顶元素。
emplace(arg...) arg... 可以是一个参数,也可以是多个参数,但它们都只用于构造一个对象,并在栈顶直接生成该对象,作为新的栈顶元素。
swap(stack<T> & other_stack) 将两个 stack 适配器中的元素进行互换,需要注意的是,进行互换的 2 个 stack 适配器中存储的元素类型以及底层采用的基础容器类型,都必须相同。

下面的 C++ 程序演示了表中部分成员函数的用法:
#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;
    s.push(1); // 添加元素
    s.push(2);
    s.push(3);

    int x = s.top(); // 访问顶部元素(不删除)
    std::cout << x << std::endl; // 输出3

    s.pop(); // 删除顶部元素

    bool isEmpty = s.empty(); // 检查stack是否为空
    std::cout << std::boolalpha << isEmpty << std::endl; // 输出false
    return 0;
}
运行结果为:

3
false

总结

容器适配器提供了一种非常有效的方式来限制或扩展基础容器(vector、list、deque 等)的功能。

和 vector、list、deque 容器相比,stack 容器对它们的用法做了限制,元素的进出必须符合先进后出的规则,每次只能使用栈顶元素,而且也没有办法遍历整个容器中的内容。

本文链接:http://task.lmcjl.com/news/4191.html

展开阅读全文