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; }
);