https://en.cppreference.com/w/cpp/container
头文件Defined in header <deque>
声明(1) template<
class T,
class Allocator = std::allocator<T>
> class deque;
(2) (since C++17)
namespace pmr {
template <class T>
using deque = std::deque<T, std::pmr::polymorphic_allocator<T>>;
}
std::deque (双向队列)是是一个可索引的序列容器，它允许在两端快速的插入和删除。此外，无论在哪一端进行 插入或删除都不会出现非法指针或非法引用。
跟std::vector不同的是，一个deque内的元素可能不是连续存储的：典型实现是，使用一系列的单独分配的固定大小的数组，和一个额外的查找表;它意味着，通过索引来访问deque必须执行两个指针解引用;这不像vector那样，vector只需要执行1个指针解引用。
一个deque的存储空间是根据需要自动扩展和收缩的。deque的扩展要比std::vector的扩展高效的多，因为它不会对现有的元素进行拷贝。另一方面，deque 会有更大的最小内存消耗;一个只有一个元素的deque必须分配它的整个内部数组(例如，8倍目标大小，8倍目标大小或者4096个字节，等等)。
通用操作的复杂度如下：
1）随机访问---固定O(1)
2）在两端插入或删除元素---固定O(1)
3）在其它地方插入或删除元素---线性O(n)
std::deque meets the requirements of Container, AllocatorAwareContainer, SequenceContainer and ReversibleContainer.
模板参数TThe type of the elements.
T must meet the requirements of CopyAssignable and CopyConstructible. (until C++11)
The requirements that are imposed on the elements depend on the actual operations performed on the container. Generally, it is required that element type is a complete type and meets the requirements of Erasable, but many member functions impose stricter requirements. (since C++11)
If erasing at begin - only erased elements。
If erasing at end - only erased elements and the past-the-end iterator。
Otherwise - all iterators are invalidated (including the past-the-end iterator).
resizeIf the new size is smaller than the old one : only erased elements and the past-the-end iterator。
If the new size is bigger than the old one : all iterators are invalidated。
Otherwise - none iterators are invalidated.
pop_front Only to the element erasedpop_backOnly to the element erased and the past-the-end iterator非法操作的说明1）当在任何一端插入元素，引用都不会是无效。
2）push_front, push_back, emplace_front 和 emplace_back都不会使引用无效。
3）当在任何一端删除元素时，引用到非删除的元素时，是有效的。
4）resize到一个更小的size， 不能使到没有删除的元素的引用失效。换言之，会使那些到已删除元素的引用非法。
4）resize到一个更大的size， 不能使任何元素的引用失效。
成员类型和定义类型定义value_typeTallocator_typeAllocatorsize_typeUnsigned integer type (usually std::size_t)difference_type Signed integer type (usually std::ptrdiff_t)referenceAllocator::reference (until C++11) value_type& (since C++11) const_referenceAllocator::const_reference (until C++11) const value_type& (since C++11) pointerAllocator::pointer (until C++11) std::allocator_traits<Allocator>::pointer (since C++11) const_pointerAllocator::const_pointer (until C++11) std::allocator_traits<Allocator>::const_pointer (since C++11) iteratorLegacyRandomAccessIteratorconst_iterator Constant LegacyRandomAccessIteratorreverse_iteratorstd::reverse_iterator<iterator>const_reverse_iteratorstd::reverse_iterator<const_iterator>元素访问ataccess specified element with bounds checking(public member function)operator[]access specified element
(public member function)frontaccess the first element
(public member function)backaccess the last element迭代器操作begin
cbeginreturns an iterator to the beginning
(public member function)end
cendreturns an iterator to the end
(public member function)rbegin
crbeginreturns a reverse iterator to the beginning
(public member function)rend
crendreturns a reverse iterator to the end
(public member function)能力指标emptychecks whether the container is empty
(public member function)sizereturns the number of elements
(public member function)max_sizereturns the maximum possible number of elements
(public member function)shrink_to_fitreduces memory usage by freeing unused memory
(public member function)修改操作clear(until C++11)void clear();
(since C++11)void clear() noexcept;clears the contents
(public member function)insert
(1)
(until C++11)iterator insert( iterator pos, const T& value );
(since C++11)iterator insert( const_iterator pos, const T& value );
(2)
(since C++11)iterator insert( const_iterator pos, T&& value );
(3)
(until C++11)void insert( iterator pos, size_type count, const T& value );
(since C++11)iterator insert( const_iterator pos, size_type count, const T& value );
(4)
(until C++11)template< class InputIt >void insert( iterator pos, InputIt first, InputIt last);
(since C++11)template< class InputIt >
iterator insert( const_iterator pos, InputIt first, InputIt last );
(5)
(since C++11)iterator insert( const_iterator pos, std::initializer_list<T> ilist );
(public member function)emplacetemplate< class... Args >
iterator emplace( const_iterator pos, Args&&... args );
(since C++11)constructs element in-place
(public member function)erase(1)
(until C++11)iterator erase( iterator pos );
(since C++11)iterator erase( const_iterator pos );
(2)
(until C++11)iterator erase( iterator first, iterator last );
(since C++11)iterator erase( const_iterator first, const_iterator last );erases elements
(public member function)push_back
(1)
void push_back( const T& value );
(2)
(since C++11) void push_back( T&& value );
adds an element to the end(public member function)emplace_back
(since C++11)(until C++17)template< class... Args >
void emplace_back( Args&&... args );
(since C++17)template< class... Args >reference emplace_back( Args&&... args );
(public member function)pop_backvoid pop_back();removes the last element
(public member function)push_frontvoid push_front( const T& value );
(since C++11)void push_front( T&& value );inserts an element to the beginning
(public member function)emplace_front(since C++11)(until C++17)template< class... Args >
void emplace_front( Args&&... args );
(since C++17)template< class... Args >reference emplace_front( Args&&... args );constructs an element in-place at the beginning
(public member function)pop_frontvoid pop_front();removes the first element
(public member function)resize
(1)
(until C++11)void resize( size_type count, T value = T() );
(since C++11)void resize( size_type count );
(2)
(since C++11)void resize( size_type count, const value_type& value );
(public member function)swap(until C++17)void swap( deque& other );
(since C++17)void swap( deque& other ) noexcept(/* see below */);swaps the contents
(public member function)举例
#include <iostream>
#include <deque>
int main()
{
// Create a deque containing integers
std::deque<int> d = {7, 5, 16, 8};
// Add an integer to the beginning and end of the deque
d.push_front(13);
d.push_back(25);
// Iterate and print values of deque
for(int n : d) {
std::cout << n << 'n';
}
}
Output:
13
7
5
16
8
25