SGI

deque<T, Alloc>

类别: 容器 组件类型: 类型

描述

一个deque [1] 非常类似于一个vector: 像vector一样，它是一个支持对元素进行随机访问的序列，在序列末尾插入和删除元素的时间复杂度为常数，在中间插入和删除元素的时间复杂度为线性。

主要的区别是deque与vector不同，deque还支持在序列开头插入和删除元素的时间复杂度为常数 [2]。另外，deque没有类似于vector的capacity()和reserve()的成员函数，也不提供与这些成员函数相关的任何关于迭代器有效性的保证 [3]。

示例

deque<int> Q;
Q.push_back(3);
Q.push_front(1);
Q.insert(Q.begin() + 1, 2);
Q[2] = 0;
copy(Q.begin(), Q.end(), ostream_iterator<int>(cout, " "));
// The values that are printed are 1 2 0

定义

定义在标准头文件 deque 中，以及非标准向后兼容头文件 deque.h 中。

模板参数

参数 描述 默认值
T deque 的值类型：存储在 deque 中的对象的类型。  
Alloc 的分配器，用于所有内部内存管理。dequealloc 模型

随机访问容器，前插入序列，后插入序列。

类型要求

无，除了 随机访问容器，前插入序列 和 后插入序列 的要求所规定的。

公共基类

无。

成员

成员

定义位置 value_type 描述
容器 对象类型， 存储在 deque 中。Tpointer
指向 对象类型， referenceT.
对 对象类型， const_referenceT
对 对象类型， size_typeT
无符号整型。 对象类型， difference_type
有符号整型。 对象类型， iterator
用于遍历一个 对象类型， const_iteratordeque.
用于遍历一个 对象类型， reverse_iteratordeque.
可逆容器 用于反向遍历一个 const_reverse_iteratordeque.
用于反向遍历一个 用于反向遍历一个 iterator begin()deque.
返回一个 对象类型， 指向 deque 开头的迭代器。用于遍历一个iterator end()deque.
指向 deque 末尾的迭代器。 对象类型， 指向 deque 开头的迭代器。用于遍历一个const_iterator begin() constdeque.
返回一个 对象类型， const_iterator end() const用于遍历一个iterator end()deque.
reverse_iterator rbegin() 对象类型， const_iterator end() const用于遍历一个const_iterator begin() constdeque.
指向反转 deque 开头的迭代器。 用于反向遍历一个 const_iterator end() const可逆容器reverse_iterator rend()
指向反转 deque 末尾的迭代器。 用于反向遍历一个 const_iterator end() const可逆容器const_reverse_iterator rbegin() const
const_reverse_iterator rend() const 用于反向遍历一个 const_iterator end() const用于反向遍历一个reverse_iterator rend()
size_type size() const 用于反向遍历一个 const_iterator end() const用于反向遍历一个const_reverse_iterator rbegin() const
返回 deque 的大小。 对象类型， size_type max_size() constdeque.
返回 deque 的最大可能大小。 对象类型， bool empty() constdeque.
true 对象类型， 如果 deque 的大小为reference operator[](size_type n)deque随机访问容器0.
返回第 n 个元素。const_reference operator[](size_type n) constdeque()
创建一个空的 deque。 n 个元素。const_reference operator[](size_type n) constdeque()
deque(size_type n) 对象类型， 序列
创建一个包含 个元素的 deque。 deque(size_type n, const T& t)const_reference operator[](size_type n) const的副本。
t 个元素的 deque。 deque(size_type n, const T& t)const_reference operator[](size_type n) constdeque(const deque&)复制构造函数。.
创建一个包含一个范围副本的 deque。 对象类型， ~deque() 
template <class InputIterator>
deque(InputIterator f, InputIterator l)
[4]
个元素的 deque。 析构函数。
deque& operator=(const deque&) 对象类型， 赋值运算符
reference front() 对象类型， 前插入序列
返回第一个元素。 const_reference front() const reference back()
后插入序列 const_reference front() const reference back()
返回最后一个元素。 const_reference back() const void push_front(const T&)
在开头插入一个新元素。 const_reference back() const void push_front(const T&)
void push_back(const T&) const_reference front() const 在末尾插入一个新元素。
void pop_front() const_reference back() const 删除第一个元素。
void pop_back() const_reference front() const 删除最后一个元素。
void swap(deque&) const_reference back() const 交换两个 deque 的内容。
插入 对象类型， x 
iterator insert(iterator pos, 
                const T& x)
个元素的 deque。 在pos之前插入范围. 
template <class InputIterator>
void insert(iterator pos, 
            InputIterator f, InputIterator l)
[4]
个元素的 deque。 [f, l)iterator erase(iterator pos)之前插入范围. 
void insert(iterator pos,
            size_type n, const T& x)
个元素的 deque。 在const_reference operator[](size_type n) constdeque(const deque&)pos之前插入范围.
删除位置为 个元素的 deque。 的元素。插入范围.
iterator erase(iterator first, iterator last) 个元素的 deque。 删除范围[first, last)
void clear() 个元素的 deque。 删除所有元素。
void resize(n, t = T()) 个元素的 deque。 在末尾插入或删除元素，使大小变为const_reference operator[](size_type n) const. 
bool operator==(const deque&, 
                const deque&)
前向容器 测试两个 deque 是否相等。这是一个全局函数，不是成员函数。 
bool operator<(const deque&, 
               const deque&)
前向容器 字典序比较。这是一个全局函数，不是成员函数。

新成员

所有deque的成员都定义在 随机访问容器，前插入序列 和 后插入序列 要求中。Deque没有引入任何新的成员。

注释

[1] deque 的发音为 "deck"，代表 "双端队列"。Knuth (第 2.6 节) 报告说这个名字是由 E. J. Schweppe 创造的。有关 deque 的更多信息，请参见 Knuth 的第 2.2.1 节。(D. E. Knuth, 计算机程序设计艺术。卷 1: 基本算法，第二版。Addison-Wesley, 1973.)

[2] 在 deque 的开头或末尾插入一个元素的时间复杂度为均摊常数。在中间插入一个元素的时间复杂度为线性，其中deque是插入点到开头和插入点到末尾的元素数量中的较小者。const_reference operator[](size_type n) const[3] 迭代器失效的语义const_reference operator[](size_type n) const与如下：

插入deque(包括push_frontpush_back) 会使所有指向和的迭代器失效。删除deque. 在 deque 的中间会使所有指向deque的迭代器失效。deque. 在 deque 的中间在 deque 的开头或末尾dequepush_backpop_front和pop_back) 仅当迭代器指向被删除的元素时才会使它失效。

[4] 这个成员函数依赖于成员模板函数，目前 (1998 年初) 并非所有编译器都支持。如果你的编译器支持成员模板，你可以用任何类型的 输入迭代器 调用此函数。但是，如果你的编译器尚不支持成员模板，那么参数必须是const value_type*类型或deque::const_iterator.

类型。

vector, 另请参见, list
[Silicon Surf] [STL Home]
slist 版权所有 © 1999 Silicon Graphics, Inc. 保留所有权利。