【双端队列】【栈】【队列】STL之deque、stack、queue、容器适配器

时间:2021-12-22 17:40:02

容器适配器

deque: g++ bits/stl_deque.h

stack: g++ bits/stl_stack.h

queue: g++ bits/stl_queue.h

deque 为容器,stack 和 queue 不是容器。看这句话:

This is not a true container, but an @e adaptor.  It holds another container, and provides a wrapper interface to that container.(stack, queue)

stack 和 queue 为其它容器的封装,如默认地使用 deque 作为底层容器(见下文)。

同为容器适配器的还有 priority_queue.

容器适配器:stack, queue, priority_queue.


1. deque

类模板:
template < class T, class Alloc = allocator<T> > class deque;


构造函数:

explicit deque (const allocator_type& alloc = allocator_type());

explicit deque (size_type n, const value_type& val = value_type(),
const allocator_type& alloc = allocator_type());

template <class InputIterator>
deque (InputIterator first, InputIterator last,
const allocator_type& alloc = allocator_type());

deque (const deque& x);

1. 其它参数都好理解,alloc 这个参数不知道是个啥玩意,它的默认值模板参数 Alloc 的一个对象,而 Alloc 的默认值为 std::allocator(g++ bits/allocator.h) 。所以注意了:这里的类模板参数(Alloc)和构造函数参数(alloc)都有默认值,搞清楚它们之间的区别和联系。也就是说既可以通过模板参数指定类型,又可以通过构造函数参数指定具体的对象,STL 的强大和复杂可见一斑。

2. 在这几个类中,deque 是最底层的,它的核心和不好理解的地方就是内存管理,这里不细谈,可以参见:

(1) std::allocator

(2) bits/stl_deque.h deque 的中注释部分

3. deque 也可以进行比较(g++ bits/stl_deque.h 重载了 ==, < 等操作符),比较的规则是 <algorithm> 中的 lexicographical_compare(http://blog.csdn.net/duyiwuer2009/article/details/23277803).

注意:这里的比较值得是两个容器之间的比较,不是容器内两个元素之间的比较。但是 lexicographical_compare 最终会涉及到元素之间的比较,由于 lexicographical_compare 默认采用 "<", 因此,对于复合类型,需要重载 "<" 才能比较。

2. stack

类模板:
template <class T, class Container = deque<T> > class stack;

构造函数:

explicit stack (const container_type& ctnr = container_type());
1. 可以通过 类模板参数指定 底层容器类型,它的 默认值是  deque。下面这段摘自 g++ bits/stl_stack.h:

The second template parameter defines the type of the underlying sequence/container.  It defaults to std::deque, but it can be any type that supports @c back, @c push_back, and @cpop_front, such as std::list,std::vector, or an appropriate user-defined type.

注意:这里的类模板参数(Container )和构造函数参数(ctnr)都有默认值,搞清楚它们之间的区别和联系。

2. 如果指定参数 const container_type& ctnr, 则从指定底层容器对象拷贝元素初始化 stack, 如:

std::deque<int> mydeque (3,100);          // deque with 3 elements
std::stack<int> second (mydeque); // stack initialized to copy of deque

3. stack 也可以进行比较,比较规则依赖于底层容器的实现,比如默认容器为 deque, 则比较规则是 lexicographical_compare(见上文).


3. queue

类模板:
template <class T, class Container = deque<T> > class queue;

构造函数:

explicit queue (const container_type& ctnr = container_type());
1. 可以通过 类模板参数指定 底层容器类型,它的 默认值是  deque。下面这段摘自 g++ bits/stl_queue.h:

The second template parameter defines the type of the underlying sequence/container.  It defaults to std::deque, but it can be any type that supports @cfront, @c back, @cpush_back, and @cpop_front, such asstd::list or an appropriate user-defined type.

注意:这里的类模板参数(Container )和构造函数参数(ctnr)都有默认值,搞清楚它们之间的区别和联系。

2. 同 stack 一样,参数 const container_type& ctnr 也是用于拷贝元素初始化 queue,见 stack 和例子。

3. queue 也可以进行比较,比较规则依赖于底层容器的实现,比如默认容器为 deque, 则比较规则是 lexicographical_compare(见上文).