1. std::vector

std::vector是C++的默認(rèn)動(dòng)態(tài)數(shù)組，其與array最大的區(qū)別在于vector的數(shù)組是動(dòng)態(tài)的，即其大小可以在運(yùn)行時(shí)更改。std::vector是封裝動(dòng)態(tài)數(shù)組的順序容器，且該容器中元素的存取是連續(xù)的。

vector的存儲(chǔ)是自動(dòng)管理，不需要人為操作自動(dòng)實(shí)現(xiàn)按需擴(kuò)張收縮。但實(shí)現(xiàn)自動(dòng)管理的代價(jià)就是：vector通常占用多于靜態(tài)數(shù)組的空間，因?yàn)槠湫枰嗟膬?nèi)存以管理將來(lái)的增長(zhǎng)。vector在分配內(nèi)存的時(shí)候是先分配一定數(shù)量的內(nèi)存，然后在內(nèi)存耗盡時(shí)再重新申請(qǐng)分配。

2. vector的用法

2.1 vector的定義和聲明

std::vector在頭文件中定義，其聲明如下：

template<
    class T,
    class Allocator = std::allocator< T >
> class vector;

namespace pmr {
    template< class T >
    using vector = std::vector< T, std::pmr::polymorphic_allocator< T >>; //C++17 起
}

其中，參數(shù)T為容器要存儲(chǔ)的元素類型，對(duì)于T需要滿足：

• 可復(fù)制賦值和可復(fù)制構(gòu)造（C++11前）。
• 要求元素類型是完整類型并滿足可擦除，即元素類型的對(duì)象能以給定的分配器（Allocator）銷毀（C++11 起，C++17 前）。
• 要求元素類型是完整類型并滿足可擦除，但許多成員函數(shù)附帶了更嚴(yán)格的要求。（C++17 起）。

Allocator為用于獲取/釋放內(nèi)存及構(gòu)造/析構(gòu)內(nèi)存中元素的分配器。

2.2 成員函數(shù)

2.2.1 基本函數(shù)

operator=

operator=函數(shù)主要適用于賦值給容器，其函數(shù)聲明如下：

/*1. 復(fù)制賦值運(yùn)算符。以 other 的副本替換內(nèi)容。*/
vector& operator=( const vector& other ); //C++20 前
constexpr vector& operator=( const vector& other ); //C++20 起

/*2. 移動(dòng)賦值運(yùn)算符。用移動(dòng)語(yǔ)義以 other 的內(nèi)容替換內(nèi)容（即從 other 移動(dòng) other 中的數(shù)據(jù)到此容器中）。
     之后 other 在合法但未指定的狀態(tài)。*/
vector& operator=( vector&& other ); //C++11 起, C++17 前
vector& operator=( vector&& other ) noexcept(); //C++17 起, C++20 前
constexpr vector& operator=( vector&& other ) noexcept(); //C++20 起

/*3. 以 initializer_list ilist 所標(biāo)識(shí)者替換內(nèi)容。*/
vector& operator=( std::initializer_list< T > ilist ); //C++11 起, C++20 前
constexpr vector& operator=( std::initializer_list< T > ilist ); //C++20 起

復(fù)雜度：

• 1的復(fù)雜度與 *this 和 other 的大小成線性。
• 2的復(fù)雜度與 *this 的大小成線性，除非分配器不比較相等且不傳播，該情況下與 *this 和 other 的大小成線性。
• 3的復(fù)雜度與 *this 和 ilist 的大小成線性。

具體的示例如下：

std::vector< int > nums1 {3, 1, 4, 6, 5, 9};
std::vector< int > nums2;
std::vector< int > nums3;

// 從 nums1 復(fù)制賦值數(shù)據(jù)到 nums2
nums2 = nums1;
//此時(shí)nums2 = {3, 1, 4, 6, 5, 9}

// 從 nums1 移動(dòng)賦值數(shù)據(jù)到 nums3,
// 修改 nums1 和 nums3
nums3 = std::move(nums1);
//此時(shí) nums1 = {}, nums3 = {3, 1, 4, 6, 5, 9}


// initializer_list 的復(fù)制賦值復(fù)制數(shù)據(jù)給 nums3
nums3 = {1, 2, 3};
//此時(shí)nums3 = {1, 2, 3}

assign

assign函數(shù)的主要作用是將值賦給容器。其函數(shù)聲明如下：

/*1. 以 count 份 value 的副本替換內(nèi)容。*/
void assign( size_type count, const T& value ); //C++20 前
constexpr void assign( size_type count, const T& value ); //C++20 起

/*2. 以范圍 [first, last) 中元素的副本替換內(nèi)容。其中有任何一個(gè)迭代器是指向 *this 中的迭代器時(shí)行為未定義。*/
template< class InputIt >
void assign( InputIt first, InputIt last ); //C++20 前
template< class InputIt >
constexpr void assign( InputIt first, InputIt last ); //C++20 起

/*3. 以來(lái)自 initializer_list ilist 的元素替換內(nèi)容。*/
void assign( std::initializer_list< T > ilist ); //C++11 起，C++20 前
constexpr void assign( std::initializer_list< T > ilist ); //C++20 起

復(fù)雜度：

• 1的復(fù)雜度與count呈線性。
• 2的負(fù)載度與 first 和 last間的距離呈線性。
• 3的復(fù)雜度與與 ilist.size()呈線性。

其具體用法如下：

std::vector< char > c;

c.assign(5, 'a');//此時(shí)c = {'a', 'a', 'a', 'a', 'a'}

const std::string str(6, 'b');
c.assign(str.begin(), str.end());//此時(shí)c = {'b', 'b', 'b', 'b', 'b', 'b'}

c.assign({'C', '+', '+', '1', '1'});//此時(shí)c = {'C', '+', '+', '1', '1'}

get_allocator

get_allocator函數(shù)的主要作用是返回相關(guān)的分配器。其函數(shù)聲明如下：

allocator_type get_allocator() const; //C++11 前
allocator_type get_allocator() const noexcept; //C++11 起, C++20 前
constexpr allocator_type get_allocator() const noexcept; //C++20 起

其返回值為與容器關(guān)聯(lián)的分配器。

2.2.2 元素訪問(wèn)

at

at用于訪問(wèn)指定的元素，同時(shí)進(jìn)行越界檢查，該函數(shù)返回位于指定位置pos的元素的引用，如果pos不在容器的范圍內(nèi)，則拋出std::out_of_range異常。其函數(shù)聲明如下：

reference at( size_type pos ); //C++20 前
constexpr reference at( size_type pos ); //C++20 起
const_reference at( size_type pos ) const; //C++20 前
constexpr const_reference at( size_type pos ) const; //C++20 起

其具體用法如下：

std::vector< int > data = {1, 2, 3};

std::cout<

operator[]

operator[]與at功能相同，即用來(lái)訪問(wèn)指定的元素，但其與at不同的是：operator[]不進(jìn)行邊界的檢查。其函數(shù)聲明如下所示：

reference operator[]( size_type pos ); //C++20 前
constexpr reference operator[]( size_type pos ); //C++20 起
const_reference operator[]( size_type pos ) const; //C++20 前
constexpr const_reference operator[]( size_type pos ) const; //C++20 起

front

front用于訪問(wèn)容器的第一個(gè)元素，其返回值為容器首元素的引用，其函數(shù)原型如下：

reference front(); //C++20 前
constexpr reference front(); //C++20 起
const_reference front() const; //C++20 前
constexpr const_reference front() const; //C++20 起

注 ：在空容器上對(duì) front 的調(diào)用是未定義的。

back

back主要功能是用來(lái)訪問(wèn)容器最后一個(gè)元素，其返回值為容器最后一個(gè)元素的引用，其函數(shù)原型如下所示：

reference back(); //C++20 前
constexpr reference back(); //C++20 起
const_reference back() const; //C++20 前
constexpr const_reference back() const; //C++20 起

注 ：在空容器上對(duì) back 的調(diào)用是未定義的。

data

data函數(shù)主要是用來(lái)返回容器底層的數(shù)組，其函數(shù)原型如下：

T* data(); //C++11 前
T* data() noexcept; //C++11 起, C++20 前
constexpr T* data() noexcept; //C++20 起
const T* data() const; //C++11 前
const T* data() const noexcept; //C++11 起, C++20 前
constexpr const T* data() const noexcept; //C++20 起

data函數(shù)返回指向作為元素存儲(chǔ)工作的底層數(shù)組的指針。返回的指針使得范圍 [data(), data() + size()) 始終是合法范圍，即使容器為空（此時(shí) data() 不可解引用）。

注 ：如果 size() 是 0，那么 data() 有可能會(huì)也有可能不會(huì)返回空指針。

2.2.3 迭代器

begin、end和cbegin、cend

begin和cbegin返回指向vector首元素的迭代器，end和cend返回指向vector末元素后一元素的迭代器。其函數(shù)聲明如下：

iterator begin(); //C++11 前
iterator begin() noexcept; //C++11 起，C++20 前
constexpr iterator begin() noexcept; //C++20 起
const_iterator begin() const; //C++11 前
const_iterator begin() const noexcept; //C++11 起，C++20 前
constexpr const_iterator begin() const noexcept; //C++20 起
const_iterator cbegin() const noexcept; //C++11 起，C++20 前
constexpr const_iterator cbegin() const noexcept; //C++20 起


iterator end(); //C++11 前
iterator end() noexcept; //C++11 起，C++20 前
constexpr iterator end() noexcept; //C++20 起
const_iterator end() const; //C++11 前
const_iterator end() const noexcept; //C++11 起，C++20 前
constexpr const_iterator end() const noexcept; //C++20 起
const_iterator cend() const noexcept; //C++11 起，C++20 前
constexpr const_iterator cend() const noexcept; //C++20 起

如果vector為空，則返回的迭代器將等于end或cend。end和cend指向vector末元素后一元素的迭代器，該元素的表現(xiàn)為占位符，試圖訪問(wèn)它將導(dǎo)致未定義行為。

rbegin、rend和crbegin、crend

rbegin和crbegin返回指向vector首元素的逆向迭代器。它對(duì)應(yīng)非逆向vector的末元素，若vector為空，則返回的迭代器等于rend或crend。rend和crend返回指向逆向vector末元素后一元素的逆向迭代器，它對(duì)應(yīng)非逆向vector首元素的前一元素，此元素表現(xiàn)為占位符，試圖訪問(wèn)它導(dǎo)致未定義行為。它們的聲明如下：

reverse_iterator rbegin(); //C++11 前
reverse_iterator rbegin() noexcept; //C++11 起，C++20 前
constexpr reverse_iterator rbegin() noexcept; //C++20 起
const_reverse_iterator rbegin() const; //C++11 前
const_reverse_iterator rbegin() const noexcept; //C++11 起，C++20 前
constexpr const_reverse_iterator rbegin() const noexcept; //C++20 起
const_reverse_iterator crbegin() const noexcept; //C++11 起，C++20 前
constexpr const_reverse_iterator crbegin() const noexcept; //C++20 起

reverse_iterator rend(); //C++11 前
reverse_iterator rend() noexcept; //C++11 起，C++20 前
constexpr reverse_iterator rend() noexcept; //C++20 起
const_reverse_iterator rend() const; //C++11 前
const_reverse_iterator rend() const noexcept; //C++11 起，C++20 前
constexpr const_reverse_iterator rend() const noexcept; //C++20 起
const_reverse_iterator crend() const noexcept; //C++11 起，C++20 前
constexpr const_reverse_iterator crend() const noexcept; //C++20 起

2.2.4 容量

empty

empty用來(lái)檢查容器是否為空，若為空則返回true，否則為false。其函數(shù)聲明如下：

bool empty() const; //C++11 前
bool empty() const noexcept; //C++11 起, C++20 前
[[nodiscard]] bool empty() const noexcept; //C++20 起

其底層實(shí)現(xiàn)就是檢查容器是否無(wú)元素，即判斷是否begin() == end()。

size

size函數(shù)返回容器中元素?cái)?shù)量，即std::distance(begin(), end())。其函數(shù)聲明如下：

size_type size() const; //C++11 前
size_type size() const noexcept; //C++11 起，C++20 前
constexpr size_type size() const noexcept; //C++20 起

max_size

max_size函數(shù)返回根據(jù)系統(tǒng)或庫(kù)實(shí)現(xiàn)限制的容器可保有的元素最大數(shù)量，即對(duì)于最大容器的 std::distance(begin(), end())。其函數(shù)聲明為：

size_type max_size() const; //C++11 前
size_type max_size() const noexcept; //C++11 起

注 ：此值通常反映容器大小上的理論極限，至多為 std::numeric_limits::max() 。運(yùn)行時(shí)，可用 RAM 總量可能會(huì)限制容器大小到小于 max_size() 的值。

capacity

capacity函數(shù)的主要作用是返回當(dāng)前存儲(chǔ)空間能夠容納的元素?cái)?shù)（即當(dāng)前分配存儲(chǔ)的容量）。其函數(shù)原型如下：

size_type capacity() const; //C++11 前
size_type capacity() const noexcept; //C++11 起, C++20 前
constexpr size_type capacity() const noexcept; //C++20 起

reserve

reserve函數(shù)是用來(lái)為vector預(yù)留存儲(chǔ)空間，其函數(shù)聲明如下：

//new_cap: vector 的新容量
void reserve( size_type new_cap ); //C++20 前
constexpr void reserve( size_type new_cap ); //C++20 起

該函數(shù)主要用來(lái)增加vector的容量（即 vector 在不重新分配存儲(chǔ)的情況下能最多能持有的元素的數(shù)量）到大于或者等于new_cap的值。如果new_cap大于當(dāng)前vector的capacity()，那么就會(huì)重新分配新的存儲(chǔ)，否則該方法不做任何事情。

注 ：

• reserve() 不會(huì)更改 vector 的大小。
• 如果 new_cap 大于 capacity()，那么所有迭代器，包含 end()迭代器和所有到元素的引用都會(huì)失效。否則，沒(méi)有迭代器或引用會(huì)失效。
• 在調(diào)用 reserve() 后，插入只會(huì)在它將導(dǎo)致 vector 的大小大于capacity()的值時(shí)觸發(fā)重新分配。
• 在 new_cap > max_size() 時(shí)拋出std::length_error。
• 不能用 reserve() 減少容器容量。為該目的提供的是 shrink_to_fit()。(文章后面有詳細(xì)的介紹)

正確的使用reserve能夠避免減少不必要的分配，例如在向vector添加元素之前提前知道元素的大致數(shù)量，使用reserve，可以提前合理分配好存儲(chǔ)空間，避免在vector增長(zhǎng)階段不必要的內(nèi)存分配和復(fù)制，進(jìn)而提高效率和存儲(chǔ)空間的利用率。

shrink_to_fit

shrink_to_fit函數(shù)主要是用來(lái)請(qǐng)求移除未使用的容量。其函數(shù)原型如下：

void shrink_to_fit();

它是減少capacity()到size()非強(qiáng)制性請(qǐng)求。請(qǐng)求是否達(dá)成依賴于實(shí)現(xiàn)。如果發(fā)生重分配，那么所有迭代器，包含 end()迭代器，和所有到元素的引用都會(huì)失效。如果沒(méi)有發(fā)生重分配，那么沒(méi)有迭代器或引用會(huì)失效。

具體的示例如下：

std::vector< int > vec = {1, 2, 3};
vec.reserve(100);
std::cout < < "vec的capacity : " < < vec.capacity() < < std::endl; //vec的capacity : 100
vec.shrink_to_fit();
std::cout < < "vec的capacity : " < < vec.capacity() < < std::endl; //vec的capacity : 3

2.2.5 修改器

clear

clear函數(shù)主要用來(lái)擦除所有元素，使用clear()后，再次調(diào)用size()，size函數(shù)返回0。clear函數(shù)的聲明如下：

void clear(); //C++11 前
void clear() noexcept; //C++11 起, C++20 前
constexpr void clear() noexcept; //C++20 起

注 ：clear不會(huì)影響vector的capacity()的大小。

insert

insert函數(shù)主要用于插入元素到容器的指定位置，其函數(shù)原型如下所示：

//在 pos 前插入 value
//返回值：指向被插入 value 的迭代器。
iterator insert( const_iterator pos, const T& value ); //C++20 前
constexpr iterator insert( const_iterator pos, const T& value ); //C++20 起

//在 pos 前插入 value
//返回值：指向被插入 value 的迭代器。
iterator insert( const_iterator pos, T&& value ); //C++11 起，C++20 前
constexpr iterator insert( const_iterator pos, T&& value ); //C++20 起

//在 pos 前插入 value 的 count 個(gè)副本。
//返回值：指向首個(gè)被插入元素的迭代器，或者在 count == 0 時(shí)返回 pos。
iterator insert( const_iterator pos, size_type count, const T& value ); //C++20 前
constexpr iterator
    insert( const_iterator pos, size_type count, const T& value ); //C++20 起

//在 pos 前插入來(lái)自范圍 [first, last) 的元素。
//返回值：指向首個(gè)被插入元素的迭代器，或者在 first == last 時(shí)返回 pos。
template< class InputIt >
iterator insert( const_iterator pos, InputIt first, InputIt last ); //C++20 前
template< class InputIt >
constexpr iterator insert( const_iterator pos, InputIt first, InputIt last ); //C++20 起

//在 pos 前插入來(lái)自 initializer_list ilist 的元素。
//返回值：指向首個(gè)被插入元素的迭代器，或者在 ilist 為空時(shí)返回 pos。
iterator insert( const_iterator pos, std::initializer_list< T > ilist ); //C++11 起，C++20 前
constexpr iterator insert( const_iterator pos,
                           std::initializer_list< T > ilist ); //C++20 起

具體用法示例如下：

std::vector< int > c1(3, 100); //初始化c1，此時(shí)c1 = {100, 100, 100}

auto it = c1.begin();
it = c1.insert(it, 200); //在it前插入元素200
//c1 = {200，100, 100, 100}

c1.insert(it, 2, 300); //在it前插入兩個(gè)元素值都為300
//c1 = {300，300，200，100, 100, 100}

// it 已經(jīng)失效，提供新迭代器
it = c1.begin();

std::vector< int > c2(2, 400); //c2 = {400, 400}
c1.insert(std::next(it, 2), c2.begin(), c2.end()); //在it后兩個(gè)元素（即200）的前面插入c2
//c1 = {300，300，400，400，200，100, 100, 100}

int arr[] = {501, 502, 503};
c1.insert(c1.begin(), arr, arr + std::size(arr));
//c1 = {501，502，503，300，300，400，400，200，100, 100, 100}

c1.insert(c1.end(), {601, 602, 603});
//c1 = {501，502，503，300，300，400，400，200，100, 100, 100，601，602，603}

emplace

emplace函數(shù)的聲明如下：

/*----------------------------------
  pos：將構(gòu)造新元素到其前的迭代器
  args：轉(zhuǎn)發(fā)給元素構(gòu)造函數(shù)的參數(shù)
  返回值iterator：指向被安置的元素的迭代器
------------------------------------*/
template< class... Args >
iterator emplace( const_iterator pos, Args&&... args ); //C++11 起, C++20 前

template< class... Args >
constexpr iterator emplace( const_iterator pos, Args&&... args ); //C++20 起

其主要作用就是原位構(gòu)造元素并將其在pos前插入到容器中。

earse

earse的函數(shù)主要功能是擦除元素，其聲明如下：

//移除位于pos的元素
//返回值：最后移除元素之后的迭代器。如果pos指代末元素，則返回end()迭代器
iterator erase( iterator pos ); //C++11 前
iterator erase( const_iterator pos ); //C++11 起，C++20 前
constexpr iterator erase( const_iterator pos ); //C++20 起

//移除范圍[first, last)中的元素。
/*返回值：最后移除元素之后的迭代器。
         如果在移除前l(fā)ast == end()，那么最終返回end()迭代器
         如果范圍[first, last) 為空，那么返回 last。*/
iterator erase( iterator first, iterator last ); //C++11 前
iterator erase( const_iterator first, const_iterator last ); //C++11 起，C++20 前
constexpr iterator erase( const_iterator first, const_iterator last ); //C++20 起

具體的用法如下所示：

std::vector< int > c{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

c.erase(c.begin());
//c = {1, 2, 3, 4, 5, 6, 7, 8, 9}

c.erase(c.begin() + 2, c.begin() + 5);
//c = {1, 2, 6, 7, 8, 9}

// 移除所有偶數(shù)
for (std::vector< int >::iterator it = c.begin(); it != c.end();)
{
  if (*it % 2 == 0)
    it = c.erase(it);
  else
    ++it;
}
//c = {1, 7, 9}

push_back

push_back函數(shù)的主要作用是將元素添加到容器末尾，其聲明如下：

//后附給定元素 value 到容器尾。初始化新元素為 value 的副本。
void push_back( const T& value ); //C++20 前
constexpr void push_back( const T& value ); //C++20 起

//后附給定元素 value 到容器尾。移動(dòng) value 進(jìn)新元素。
void push_back( T&& value ); //C++11 起，C++20 前
constexpr void push_back( T&& value ); //C++20 起

注 ：如果新的 size()大于 capacity()，那么所有迭代器和引用（包含 end() 迭代器）都會(huì)失效。否則只有 end() 迭代器會(huì)失效。

emplace_back

emplace_back函數(shù)與emplace類似，只不過(guò)是在容器末尾就地構(gòu)造元素，其函數(shù)聲明如下：

template< class... Args >
void emplace_back( Args&&... args ); //C++11 起, C++17 前

template< class... Args >
reference emplace_back( Args&&... args ); //C++17 起, C++20 前

template< class... Args >
constexpr reference emplace_back( Args&&... args ); //C++20 起

由于emplace_back是原地構(gòu)造元素，因此其插入效率要高于push_back。

注 ：如果新的 size()大于 capacity()，那么所有迭代器和引用（包含 end() 迭代器）都會(huì)失效。否則只有 end() 迭代器會(huì)失效。

pop_back

pop_back函數(shù)的主要作用就是移除末元素，其函數(shù)聲明如下：

void pop_back(); //C++20 前
constexpr void pop_back(); //C++20 起

如果在空容器上調(diào)用pop_back會(huì)導(dǎo)致未定義行為。

注 ：使指向末元素的迭代器和引用，以及end()迭代器失效。

resize

resize函數(shù)的主要作用是改變?nèi)萜髦锌纱鎯?chǔ)元素的個(gè)數(shù)，通過(guò)該函數(shù)可以重新設(shè)置容器大小，其函數(shù)聲明如下：

/*
該函數(shù)重設(shè)容器的大小為count，在count==size()時(shí)不做任何操作。
如果當(dāng)前大小大于 count，那么減小容器到它的開(kāi)頭 count 個(gè)元素。
如果當(dāng)前大小小于 count，那么后附額外的默認(rèn)插入的元素。
*/
void resize( size_type count ); //C++20 前
constexpr void resize( size_type count ); //C++20 起

/*
該函數(shù)重設(shè)容器的大小為count，在count==size()時(shí)不做任何操作。
如果當(dāng)前大小大于 count，那么減小容器到它的開(kāi)頭 count 個(gè)元素。
如果當(dāng)前大小小于 count，那么后附額外的 value 的副本
*/
void resize( size_type count, const value_type& value ); //C++20 前
constexpr void resize( size_type count, const value_type& value ); //C++20 起

其具體用法示例如下：

std::vector< int > c = {1, 2, 3};

c.resize(5); //將其size增加大小到5
//c = {1, 2, 3, 0, 0}

c.resize(2); //將其size減少大小到2
//c = {1, 2}

c.resize(6, 4); //將其size增加大小到6，填充值為4";
//c = {1, 2, 4, 4, 4，4}

swap

swap函數(shù)的主要作用是交換兩個(gè)vector容器的內(nèi)容，不在單獨(dú)的元素上調(diào)用任何移動(dòng)、復(fù)制或交換操作。所有迭代器和引用保持有效。end()迭代器會(huì)失效。其函數(shù)聲明如下：

void swap( vector& other ); //C++17 前
void swap( vector& other ) noexcept(); //C++17 起, C++20 前
constexpr void swap( vector& other ) noexcept(); //C++20 起

其用法示例如下圖所示：

std::vector< int > a1{1, 2, 3}, a2{4, 5};

auto it1 = std::next(a1.begin()); //*it1 = 2 
auto it2 = std::next(a2.begin()); //*it2 = 5 

int& ref1 = a1.front(); //ref1 = 1
int& ref2 = a2.front(); //ref1 = 4

std::cout < ' ' < < *it2 < < ' ' < < ref1 < < ' ' < < ref2 < < 'n';
//打印結(jié)果為2 5 1 4

a1.swap(a2);

//此時(shí)a1 = {4, 5}，a2 = {1, 2, 3}
std::cout < ' ' < < *it2 < < ' ' < < ref1 < < ' ' < < ref2 < < 'n';
//打印結(jié)果仍為2 5 1 4

/*注：
    交換后迭代器與引用保持與原來(lái)的元素關(guān)聯(lián)，
    例如盡管 'a1' 中值為 2 的元素被移動(dòng)到 'a2' 中，
    原來(lái)指向它的 it1 仍指向同一元素。*/

2.2 非成員函數(shù)

operator==,!=,<,<=,>,>=,<=>(std::vector)

C++提供operator==,!=,<,<=,>,>=,<=>(std::vector)非成員函數(shù)用來(lái)比較兩個(gè)vector的大小，相關(guān)函數(shù)及函數(shù)聲明如下：

//1. ==
//返回值：在 vector 內(nèi)容相等時(shí)返回 true，否則返回 false
template< class T, class Alloc >
bool operator==( const std::vector< T, Alloc >& lhs,
                 const std::vector< T, Alloc >& rhs ); //C++20 前
template< class T, class Alloc >
constexpr bool operator==( const std::vector< T, Alloc >& lhs,
                           const std::vector< T, Alloc >& rhs ); //C++20 起

//2. !=
//返回值：在 vector 內(nèi)容不相等時(shí)返回 true，否則返回 false
template< class T, class Alloc >
bool operator!=( const std::vector< T, Alloc >& lhs,
                 const std::vector< T, Alloc >& rhs ); //C++20 前

//3. < 
//返回值：在 lhs 的內(nèi)容按字典序小于 rhs 的內(nèi)容時(shí)返回 true，否則返回 false
template< class T, class Alloc >
bool operator< ( const std::vector< T, Alloc >& lhs,
                const std::vector< T, Alloc >& rhs ); //C++20 前

//4. <=
//返回值：在 lhs 的內(nèi)容按字典序小于或等于 rhs 的內(nèi)容時(shí)返回 true，否則返回 false
template< class T, class Alloc >
bool operator<=( const std::vector< T, Alloc >& lhs,
                 const std::vector< T, Alloc >& rhs ); //C++20 前

//5. >
//返回值：在 lhs 的內(nèi)容按字典序大于 rhs 的內(nèi)容時(shí)返回 true，否則返回 false
template< class T, class Alloc >
bool operator >( const std::vector< T, Alloc >& lhs,
                const std::vector< T, Alloc >& rhs ); //C++20 前

//6. >=
//返回值：在 lhs 的內(nèi)容按字典序大于或等于 rhs 的內(nèi)容時(shí)返回 true，否則返回 false
template< class T, class Alloc >
bool operator >=( const std::vector< T, Alloc >& lhs,
                 const std::vector< T, Alloc >& rhs ); //C++20 前

//7. <= >
//返回值：lhs 與 rhs 中的首對(duì)不等價(jià)元素的相對(duì)順序，如果有這種元素；否則是 lhs.size() <= > rhs.size()。
template< class T, class Alloc >
constexpr  operator<= >( const std::vector< T, Alloc >& lhs,
                                       const std::vector< T, Alloc >& rhs ); //C++20 起

• 1,2中會(huì)檢查lhs和rhs的內(nèi)容是相等，即他們是否擁有相同數(shù)量的元素且lhs中每個(gè)元素與rhs的相同位置元素比較相等。同時(shí)函數(shù)中T 必須符合 可相等比較(EqualityComparable) 的要求

• 3-6中按照字典比較lhs和rhs的內(nèi)容，其內(nèi)部等價(jià)于調(diào)用std::lexicographical_compare函數(shù)進(jìn)行比較。同時(shí)函數(shù)中T 必須符合[ 可小于比較(LessThanComparable) 的要求。

• 7中也是按字典序比較lhs和rhs的內(nèi)容。其內(nèi)部等價(jià)于調(diào)用std::lexicographical_compare_three_way進(jìn)行比較。返回類型同合成三路比較的結(jié)果類型。其邏輯大致如下：

  lhs < rhs ? std::weak_ordering::less :
  rhs < lhs ? std::weak_ordering::greater :
              std::weak_ordering::equivalent
  //注：通常情況下less對(duì)應(yīng)的是-1，greater對(duì)應(yīng)1，equivalent對(duì)應(yīng)0
  

  lhs與rhs中的首對(duì)不等價(jià)元素的相對(duì)順序，如果有這種元素；否則是lhs.size() <=> rhs.size()。

其具體的應(yīng)用示例如下所示：

std::vector< int > alice{1, 2, 3};
std::vector< int > bob{7, 8, 9, 10};
std::vector< int > eve{1, 2, 3};

std::cout < < std::boolalpha;

// 比較不相等的容器
std::cout < < "alice == bob returns " < < (alice == bob) < < 'n';
std::cout < < "alice != bob returns " < < (alice != bob) < < 'n';
std::cout < < "alice <  bob returns " < < (alice < bob) < < 'n';
std::cout < < "alice <= bob returns " < < (alice <= bob) < < 'n';
std::cout < < "alice >  bob returns " < < (alice > bob) < < 'n';
std::cout < < "alice >= bob returns " < < (alice >= bob) < < 'n';

std::cout < < 'n';

// 比較相等的容器
std::cout < < "alice == eve returns " < < (alice == eve) < < 'n';
std::cout < < "alice != eve returns " < < (alice != eve) < < 'n';
std::cout < < "alice <  eve returns " < < (alice < eve) < < 'n';
std::cout < < "alice <= eve returns " < < (alice <= eve) < < 'n';
std::cout < < "alice >  eve returns " < < (alice > eve) < < 'n';
std::cout < < "alice >= eve returns " < < (alice >= eve) < < 'n';

輸出結(jié)果為

alice == bob returns false
alice != bob returns true
alice <  bob returns true
alice <= bob returns true
alice >  bob returns false
alice >= bob returns false
 
alice == eve returns true
alice != eve returns false
alice <  eve returns false
alice <= eve returns true
alice >  eve returns false
alice >= eve returns true

std::swap(std::vector)

std::swap(std::vector)函數(shù)是為std::vector特化std::swap 算法。其函數(shù)聲明如下：

template< class T, class Alloc >
void swap( std::vector< T, Alloc >& lhs,
           std::vector< T, Alloc >& rhs ); //C++11 起, C++17 前

template< class T, class Alloc >
void swap( std::vector< T, Alloc >& lhs,
           std::vector< T, Alloc >& rhs ) noexcept();//C++17 起, C++20 前

template< class T, class Alloc >
constexpr void swap( std::vector< T, Alloc >& lhs,
                     std::vector< T, Alloc >& rhs ) noexcept(); //C++20 起

交換 lhs 與 rhs 的內(nèi)容。調(diào)用lhs.swap(rhs)。其具體用法如下：

std::vector< int, 3 > a1{1, 2, 3}, a2{4, 5, 6};

auto it1 = a1.begin(); //*it1 = 1
auto it2 = a2.begin(); //*it2 = 4

int &ref1 = a1[1]; // ref1 = 2
int &ref2 = a2[1]; // ref1 = 5

std::cout < < *it1 < < ' ' < < *it2 < < ' ' < < ref1 < < ' ' < < ref2 < < 'n';
// 打印結(jié)果為1 4 2 5

std::swap(a1, a2);

// 此時(shí)a1 = {4, 5, 6}，a2 = {1, 2, 3}
std::cout < < *it1 < < ' ' < < *it2 < < ' ' < < ref1 < < ' ' < < ref2 < < 'n';
// 打印結(jié)果為4 1 5 2

std::erase, std::erase_if (std::vector)

std::erase, std::erase_if (std::vector)函數(shù)主要用來(lái)擦除所有滿足特定判別標(biāo)準(zhǔn)的元素。其函數(shù)聲明如下：

//從容器中擦除所有比較等于 value 的元素
template< class T, class Alloc, class U >
constexpr typename std::vector< T, Alloc >::size_type
    erase(std::vector< T, Alloc >& c, const U& value); //C++20 起

//從容器中擦除所有滿足 pred 的元素
template< class T, class Alloc, class Pred >
constexpr typename std::vector< T, Alloc >::size_type
    erase_if(std::vector< T, Alloc >& c, Pred pred); //C++20 起

std::erase(std::vector)從容器中擦除所有比較等于 value 的元素，其返回值為被擦除的元素個(gè)數(shù)，其等價(jià)于

auto it = std::remove(c.begin(), c.end(), value);
auto r = std::distance(it, c.end());
c.erase(it, c.end());
return r;

std::erase_if (std::vector)從容器中擦除所有滿足 pred 的元素，其返回值為被擦除的元素個(gè)數(shù)，其等價(jià)于

auto it = std::remove_if(c.begin(), c.end(), pred);
auto r = std::distance(it, c.end());
c.erase(it, c.end());
return r;

示例：

std::vector< int > c{1, 2, 3, 4, 6};
// 擦除c中的值等于3的元素
auto erased1 = std::erase(c, 3); // erased1 = 1
// 此時(shí)c = {1, 2, 4, 6}

// 擦除c中的偶數(shù)
auto erased2 = std::erase_if(c, [](int n)
                             { return n % 2 == 0; }); // erased2 = 3
// 此時(shí)c = {1}

3. 總結(jié)

vector容器的優(yōu)勢(shì)和劣勢(shì)：

優(yōu)勢(shì)

• 支持隨機(jī)訪問(wèn)，訪問(wèn)無(wú)開(kāi)銷，時(shí)間恒定。
• 線性遍歷/搜索。
• 在容量滿足的情況下，末端插入元素效率高。

劣勢(shì)

• 如果元素類型具有較高的復(fù)制/分配成本，則插入元素速度比較慢。
• 如果隨之位置插入或擦除占程序的主導(dǎo)地位，程序會(huì)變慢。

vector容器在具體的應(yīng)用中需要注意一下幾點(diǎn)：

1. 創(chuàng)建一個(gè)新vector

// 值列表初始化: C++11
vector< int > v {0, 1, 2, 3};   // v = {0, 1, 2, 3}

// 初始化一個(gè)長(zhǎng)度為4，所有元素值都為2的vector
vector< int > w (4, 2)  // w = {2, 2, 2, 2}
  
// 深拷貝，以v初始化vector對(duì)象b
vector< int > b {v}; // b = {0, 1, 2, 3}

2. vector的size和capacity

• size()代表vector中元素的數(shù)量
• capacity()代表當(dāng)前vector中可以存儲(chǔ)元素?cái)?shù)量的最大值。
  如果在向vector中添加元素之前提前知道元素（大致的）數(shù)量n，及時(shí)使用resrve(n)，這樣可以避免在元素插入階段可能產(chǎn)生的不必要內(nèi)存分配和復(fù)制。

3. 插入元素和擦除元素的效率
   在末尾插入元素的效率最快，但插入任意位置可能會(huì)很慢，因?yàn)橹虚g可能涉及到元素的復(fù)制和移動(dòng)。擦除元素同理。
4. 使用shrink_to_fit()降低內(nèi)存
   從vector中擦除元素不會(huì)改變其容量，因此未存放的元素的位置對(duì)應(yīng)內(nèi)存不會(huì)被釋放，如果后續(xù)不需要再使用這些空閑的內(nèi)存，可以使用shrink_to_fit()對(duì)該內(nèi)存進(jìn)行釋放，提高內(nèi)存使用效率。