C++ deque使用
deque
- C++ deque使用
-
- 概述
- 创建deque
-
- 构造函数
- opertor=
- assign
- 元素访问
-
- at
- operator[]
- front
- back
- 迭代器
-
- begin\cbegin
- end\cend
- rbegin\crbegin
- rend\crend
- 容量
-
- empty
- size
- max_size
- shrink_to_fit
- 修改器
-
- clear
- insert
- emplace
- erase
- push_back
- emplace_back
- pop_back
- push_front
- emplace_front
- pop_front
- resize
- swap
- 非成员函数
-
- operator==
- std::swap
- erase(std::deque)
- erase_if(std::deque)
概述
定义于头文件<deque>，std::deque （ double-ended queue ，双端队列）是有下标顺序容器，它允许在其首尾两段快速插入及删除。另外，在 deque 任一端插入或删除不会非法化指向其余元素的指针或引用。
类模板：
template<
class T,
class Allocator = std::allocator<T>
> class deque;
模板形参：
T - 元素的类型;
Allocator - 用于获取/释放内存及构造/析构内存中元素的分配器。
deque上的常见操作复杂度（效率）如下：
随机访问——常数 𝓞(1)
在末尾插入或移除元素——均摊常数 𝓞(1)
插入或移除元素——线性 𝓞(n)
创建deque
构造函数
从各种数据源构造新容器，可选地使用用户提供的分配器 alloc 。
与vector构造函数一样。
定义：
// 1、默认构造函数
deque();
// 2、构造拥有给定分配器 alloc 的空容器。
explicit deque( const Allocator& alloc );
// 3、构造拥有 count 个有值 value 的元素的容器。
deque( size_type count,
const T& value,
const Allocator& alloc = Allocator());
// 4、构造拥有个 count 默认插入的 T 实例的容器。不进行复制。
explicit deque( size_type count, const Allocator& alloc = Allocator() );
// 5、构造拥有范围 [first, last) 内容的容器。
template< class InputIt >
deque( InputIt first, InputIt last,
const Allocator& alloc = Allocator() );
// 6、复制构造函数
deque( const deque& other );
// 7、构造拥有 other 内容的容器，以 alloc 为分配器。
deque( const deque& other, const Allocator& alloc );
// 8、移动构造函数
deque( deque&& other );
// 9、有分配器扩展的移动构造函数。
deque( deque&& other, const Allocator& alloc );
// 10、构造拥有 initializer_list init 内容的容器。
deque( std::initializer_list<T> init,
const Allocator& alloc = Allocator() );
用法：
// 1、默认构造函数
std::deque<std::string> words1;
// 3、构造拥有 count 个有值 value 的元素的容器
std::deque<std::string> words3(5, "Mo"); //words2 为 {"Mo", "Mo", "Mo", "Mo", "Mo"}
// 5、构造拥有范围 [first, last) 内容的容器
std::deque<std::string> words5(words3.begin(), words3.end());
// 6、复制构造函数
std::deque<std::string> words6(words5);
// 8、移动构造函数
std::deque<std::string> words8(std::move(words6));
// 10、C++ 11 初始化器列表语法：
std::deque<std::string> words10 {"the", "frogurt", "is", "also", "cursed"};
opertor=
替换容器的内容。
定义：
deque& operator=( const deque& other ); // 复制赋值运算符。
deque& operator=( deque&& other ); // 移动赋值运算符。
deque& operator=( std::initializer_list<T> ilist ); // 以 initializer_list ilist 所标识者替换内容。
用法：
std::deque<int> nums1 {3, 1, 4, 6, 5, 9};
std::deque<int> nums2;
std::deque<int> nums3;
// 从 nums1 复制赋值数据到 nums2
nums2 = nums1;
// 从 nums1 移动赋值数据到 nums3,
nums3 = std::move(nums1);
// initializer_list 的复制赋值复制数据给 nums3
nums3 = {1, 2, 3};
assign
替换容器的内容。
定义：
void assign( size_type count, const T& value ); // 1、以 count 份 value 的副本替换内容。
template< class InputIt > // 2、以范围 [first, last) 中元素的副本替换内容。
void assign( InputIt first, InputIt last );
void assign( std::initializer_list<T> ilist ); // 3、以来自 initializer_list ilist 的元素替换内容。
用法：
// 以 count 份 value 的副本替换内容
std::deque<char> characters;
characters.assign(5, 'a');
// 以范围 [first, last) 中元素的副本替换内容
std::deque<char> vchar;
vchar.assign(characters.begin(), characters.end());
// 以来自 initializer_list ilist 的元素替换内容
characters.assign({'\n', 'C', '+', '+', '1', '1', '\n'});
元素访问
at
返回位于指定位置 pos 的元素的引用，有边界检查。
若 pos 不在容器范围内，则抛出 std::out_of_range 类型的异常。
定义：
reference at( size_type pos );
const_reference at( size_type pos ) const;
用法：
std::deque<int> data = {1, 2, 3, 4, 5, 6};
data.at(1) = 0; // 修改元素
std::cout << data.at(2) << std::endl; // 获取元素
operator[]
返回位于指定位置 pos 的元素的引用。不进行边界检查。
定义：
reference operator[]( size_type pos );
const_reference operator[]( size_type pos ) const;
用法：
std::deque<int> vi = {1, 2, 3, 4, 5, 6};
vi[1] = 0; // 修改元素
std::cout << vi[2] << std::endl; // 获取元素
front
返回到容器首元素的引用。
对于容器 c ，表达式 c.front() 等价于 *c.begin() 。
定义：
reference front();
const_reference front() const;
用法：
std::deque<char> letters {'o', 'm', 'g', 'w', 't', 'f'};
if (!letters.empty()) {
std::cout << letters.front() << std::out; // 输出 o
}
back
返回到容器中最后一个元素的引用。
对于非空容器 c ，表达式 c.back() 等价于 *std::prev(c.end()) 。
定义：
reference back();
const_reference back() const;
用法：
std::deque<char> letters {'o', 'm', 'g', 'w', 't', 'f'};
if (!letters.empty()) {
std::cout << letters.back() << std::endl; // 输出 f
}
迭代器
begin\cbegin
返回指向deque 首元素的迭代器。 cbegin中的c表示const，即返回const_iterator，不允许通过迭代器修改元素。
若 deque 为空，则返回的迭代器将等于 end() 。
定义：
iterator begin();
const_iterator cbegin() const noexcept;
用法：
std::deque<int> vi = {1, 2, 3, 4, 5, 6};
std::cout << *(vi.begin()) << std::endl; // 输出 1
*(vi.begin()) = 0;
std::cout << *(vi.cbegin()) << std::endl; // 输出 0
end\cend
指向后随最后元素的迭代器。
定义：
iterator end();
const_iterator cend() const noexcept;
用法：
std::deque<char> vc;
if (vc.begin() == vc.end())
{
std::cout << "deque is empty." << std::endl;
}
rbegin\crbegin
返回指向逆向 deque 首元素的逆向迭代器。 它对应非逆向 deque 的末元素。若 deque 为空，则返回的迭代器等于 rend() 。
定义：
reverse_iterator rbegin();
const_reverse_iterator crbegin() const noexcept;
用法：
std::deque<int> vi = {1, 2, 3, 4, 5, 6};
std::cout << *(vi.rbegin()) << std::endl; // 输出 6
std::cout << *(vi.crbegin()) << std::endl; // 输出 6
rend\crend
返回指向逆向 deque 末元素后一元素的逆向迭代器。 它对应非逆向 deque 首元素的前一元素。此元素表现为占位符，试图访问它导致未定义行为。
定义：
reverse_iterator rend();
const_reverse_iterator crend() const noexcept;
用法：
std::deque<int> vi = {1, 2, 3, 4, 5, 6};
std::cout << *std::prev(vi.rend()) << std::endl; // 输出 1
std::cout << *std::prev(vi.crend()) << std::endl; // 输出 1
容量
empty
检查容器是否无元素，即是否 begin() == end() 。
定义：
用法：
deque<int> v;
bool flag = v.empty(); // 输出 true
size
返回容纳的元素数。
定义：
用法：
std::deque<int> nums {1, 3, 5, 7};
std::cout << nums.size() << std::endl; // 输出 4
max_size
返回根据系统或库实现限制的容器可保有的元素最大数量，即对于最大容器的 std::distance(begin(), end()) 。
定义：
用法：
std::deque<int> vi;
std::cout << vi.max_size() << std::endl; // 可能输出 4611686018427387903
std::deque<char> vc;
std::cout << vc.max_size() << std::endl; // 可能输出 18446744073709551615
shrink_to_fit
请求移除未使用的容量。 释放任何不使用的内存。
它是减少使用内存而不更改序列的大小非强制性请求。请求是否达成依赖于实现。
若发生重分配，则所有迭代器，包含尾后迭代器，和所有到元素的引用都被非法化。若不发生重分配，则没有迭代器或引用被非法化。
定义：
用法：
std::deque<int> nums(1000, 42);
nums.push_front(1);
nums.pop_front();
nums.clear();
// nums 现在不含项目，但它仍保有分配的内存。
// 调用 shrink_to_fit 可能会释放任何不使用的内存。
nums.shrink_to_fit();
修改器
clear
从容器擦除所有元素。此调用后 size() 返回零。
非法化任何指代所含元素的引用、指针或迭代器。任何尾后迭代器亦被非法化。
定义：
用法：
std::deque<int> container{1, 2, 3};
container.clear();
std::cout << container.size() << std::endl; // 输出 0
insert
插入元素到容器中的指定位置。
定义：
// 1、在 pos 前插入 value
iterator insert( iterator pos, const T& value );
// 2、在 pos 前插入 value
iterator insert( const_iterator pos, T&& value );
// 3、在 pos 前插入 value 的 count 个副本
void insert( iterator pos, size_type count, const T& value );
// 4、在 pos 前插入来自范围 [first, last) 的元素
template< class InputIt >
void insert( iterator pos, InputIt first, InputIt last);
// 5、在 pos 前插入来自 initializer_list ilist 的元素
iterator insert( const_iterator pos, std::initializer_list<T> ilist );
用法：
std::deque<int> vec(3,100);
// 1，2、在 pos 前插入 value
auto it = vec.begin();
it = vec.insert(it, 200); // 200 100 100 100
// 3、插入多个value
vec.insert(it,2,300); // 300 300 200 100 100 100
// "it" 不再合法，获取新值：
it = vec.begin();
// 4、在 pos 前插入来自范围 [first, last) 的元素
std::deque<int> vec2(2,400);
vec.insert(it+2, vec2.begin(), vec2.end()); // 300 300 400 400 200 100 100 100
// 5、在 pos 前插入来自 initializer_list ilist 的元素
int arr[] = { 501,502,503 };
vec.insert(vec.begin(), arr, arr+3); // 501 502 503 300 300 400 400 200 100 100 100
emplace
直接于 pos 前插入元素到容器中。
定义：
template< class... Args >
iterator emplace( const_iterator pos, Args&&... args );
用法：
std::deque<int> v {1, 2, 3};
v.emplace(v.begin() + 1, 4); // v : 1, 4, 2, 3
erase
从容器擦除指定的元素。
定义：
// 1、移除位于 pos 的元素。
iterator erase( iterator pos );
// 2、移除范围 [first; last) 中的元素。
iterator erase( iterator first, iterator last );
用法：
std::deque<int> c {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
c.erase(c.begin()); // 1 2 3 4 5 6 7 8 9
c.erase(c.begin()+2, c.begin()+5); // 1 2 6 7 8 9 (前开后闭，6没有被删除)
push_back
后附给定元素 value 到容器尾
定义：
// 1、初始化新元素为 value 的副本。
void push_back( const T& value );
// 2、移动 value 进新元素。
void push_back( T&& value );
用法：
std::deque<std::string> letters;
letters.push_back("abc"); // letters : "abc"
std::string s = "def";
letters.push_back(std::move(s)); // letters : "abc" "def" , s为空
emplace_back
添加新元素到容器尾
定义：
// C++ 11
template< class... Args >
void emplace_back( Args&&... args );
// C++ 17
template< class... Args >
reference emplace_back( Args&&... args );
用法：
// 下列代码用 emplace_back 后附 President 类型对象到 std::deque 。
// 它演示 emplace_back 如何转发参数到 President 的构造函数，
// 并展示如何用 emplace_back 避免用 push_back 时的额外复制或移动操作。
#include <deque>
#include <string>
#include <iostream>
struct President
{
std::string name;
std::string country;
int year;
President(std::string p_name, std::string p_country, int p_year)
: name(std::move(p_name)), country(std::move(p_country)), year(p_year)
{
std::cout << "I am being constructed.\n";
}
President(President&& other)
: name(std::move(other.name)), country(std::move(other.country)), year(other.year)
{
std::cout << "I am being moved.\n";
}
President& operator=(const President& other) = default;
};
int main()
{
std::deque<President> elections;
std::cout << "emplace_back:\n";
elections.emplace_back("Nelson Mandela", "South Africa", 1994);
std::deque<President> reElections;
std::cout << "\npush_back:\n";
reElections.push_back(President("Franklin Delano Roosevelt", "the USA", 1936));
std::cout << "\nContents:\n";
for (President const& president: elections) {
std::cout << president.name << " was elected president of "
<< president.country << " in " << president.year << ".\n";
}
for (President const& president: reElections) {
std::cout << president.name << " was re-elected president of "
<< president.country << " in " << president.year << ".\n";
}
}
// 输出
emplace_back:
I am being constructed.
push_back:
I am being constructed.
I am being moved.
Contents:
Nelson Mandela was elected president of South Africa in 1994.
Franklin Delano Roosevelt was re-elected president of the USA in 1936.
pop_back
移除容器的末元素。
定义：
用法：
std::deque<int> numbers {1, 2, 3};
numbers.pop_back(); // {1, 2}
push_front
前附给定元素 value 到容器起始。 所有迭代器，包含尾后迭代器，都被非法化
定义：
void push_front( const T& value );
void push_front( T&& value );
用法：
std::deque<int> numbers {1, 2};
numbers.push_front(0); // {0, 1, 2}
emplace_front
插入新元素到容器起始。
定义：
// C++ 11
template< class... Args >
void emplace_front( Args&&... args );
// C++ 17
template< class... Args >
reference emplace_front( Args&&... args );
用法： 参考emplace_back的用法。
pop_front
移除容器首元素。 指向被擦除元素的迭代器和引用被非法化。若元素是容器的最后元素，则尾后迭代器亦被非法化。其他迭代器和引用不受影响。
定义：
用法：
std::deque<int> c = {1, 2, 3};
c.pop_front(); // c : 2, 3
resize
重设容器大小以容纳 count 个元素。 若当前大小大于 count ，则减小容器为其首 count 个元素。若当前大小小于 count ，1) 则后附额外的默认插入的元素，2) 则后附额外的 value 的副本。
定义：
void resize( size_type count );
void resize( size_type count, const value_type& value );
用法：
std::deque<int> c = {1, 2, 3};
c.resize(5); // c : 1, 2, 3, 0, 0
c.resize(2); // c : 1, 2
swap
将内容与 other 的交换。 不在单独的元素上调用任何移动、复制或交换操作。
定义：
用法：
std::deque<int> a1{1, 2, 3}, a2{4, 5};
a1.swap(a2);
非成员函数
operator==
检查 lhs 与 rhs 的内容是否相等，即它们是否拥有相同数量的元素且 lhs 中每个元素与 rhs 的同位置元素比较相等。
定义：
template< class T, class Alloc >
bool operator==( const std::deque<T,Alloc>& lhs,
const std::deque<T,Alloc>& rhs );
用法：
std::deque<int> alice{1, 2, 3};
std::deque<int> bob{7, 8, 9, 10};
std::deque<int> eve{1, 2, 3};
// 比较不相等的容器
std::cout << "alice == bob returns " << (alice == bob) << std::endl; //输出 false
// 比较相等的容器
std::cout << "alice == eve returns " << (alice == eve) << std::endl; //输出 true
std::swap
为 std::deque 特化 std::swap 算法。交换 lhs 与 rhs 的内容。调用 lhs.swap(rhs) 。
定义：
template< class T, class Alloc >
void swap( std::deque<T,Alloc>& lhs,
std::deque<T,Alloc>& rhs );
用法：
std::deque<int> alice{1, 2, 3};
std::deque<int> bob{7, 8, 9, 10};
//交换容器
std::swap(alice,bob);
//交换后：alice : 7 8 9 10 bob : 1 2 3
erase(std::deque)
从容器中擦除所有比较等于 value 的元素。(C++ 20)
定义：
template< class T, class Alloc, class U >
constexpr typename std::deque<T,Alloc>::size_type
erase(std::deque<T,Alloc>& c, const U& value);
用法：
std::deque<char> cnt {'1', '2', '3', '5', '6'};
auto erased = std::erase(cnt, '3');
erase_if(std::deque)
从容器中擦除所有满足 pred 的元素。(C++ 20)
定义：
template< class T, class Alloc, class U >
constexpr typename std::deque<T,Alloc>::size_type
erase_if(std::deque<T,Alloc>& c, Pred pred);
用法：
std::deque<char> cnt {'1', '2', '3', '5', '6'};
std::erase_if(cnt,
[](char x) { return (x - '0') % 2 == 0; }
);