快捷導(dǎo)航

C++ deque/queue/stack的底層原理解析

更新時(shí)間：2023年07月21日 16:09:54 作者：lliuhao--

這篇文章主要介紹了C++ deque/queue/stack的底層原理解析,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

deque容器的存儲(chǔ)結(jié)構(gòu)

和 vector 容器采用連續(xù)的線性空間不同，deque 容器存儲(chǔ)數(shù)據(jù)的空間是由一段一段等長的連續(xù)空間構(gòu)成，各段空間之間并不一定是連續(xù)的，可以位于在內(nèi)存的不同區(qū)域。

deque采用一塊所謂的map數(shù)組（注意，不是STL的map容器）作為主控。這里所謂map是一小塊連續(xù)空間（類似于vector），其中每個(gè)元素（此處稱為一個(gè)節(jié)點(diǎn)，node）都是指針，指向另一段（較大的）連續(xù)線性空間，稱為緩沖區(qū)。緩沖區(qū)才是deque的儲(chǔ)存空間主體。SGI STL 允許我們指定緩沖區(qū)大小，默認(rèn)值0表示將使用512 bytes 緩沖區(qū)。

通過建立 map 數(shù)組，deque 容器申請(qǐng)的這些分段的連續(xù)空間就能實(shí)現(xiàn)“整體連續(xù)”的效果。換句話說，當(dāng) deque 容器需要在頭部或尾部增加存儲(chǔ)空間時(shí)，它會(huì)申請(qǐng)一段新的連續(xù)空間，同時(shí)在 map 數(shù)組的開頭或結(jié)尾添加指向該空間的指針，由此該空間就串接到了 deque 容器的頭部或尾部。

如果 map 數(shù)組滿了怎么辦？很簡單，再申請(qǐng)一塊更大的連續(xù)空間供 map 數(shù)組使用，將原有數(shù)據(jù)（很多指針）拷貝到新的 map 數(shù)組中，然后釋放舊的空間。

deque 容器的分段存儲(chǔ)結(jié)構(gòu)，提高了在序列兩端添加或刪除元素的效率，但也使該容器迭代器的底層實(shí)現(xiàn)變得更復(fù)雜。

deque容器迭代器的底層實(shí)現(xiàn)

由于 deque 容器底層將序列中的元素分別存儲(chǔ)到了不同段的連續(xù)空間中，因此要想實(shí)現(xiàn)迭代器的功能，必須先解決如下 2 個(gè)問題：

迭代器在遍歷 deque 容器時(shí)，必須能夠確認(rèn)各個(gè)連續(xù)空間在 map 數(shù)組中的位置；
迭代器在遍歷某個(gè)具體的連續(xù)空間時(shí)，必須能夠判斷自己是否已經(jīng)處于空間的邊緣位置。如果是，則一旦前進(jìn)或者后退，就需要跳躍到上一個(gè)或者下一個(gè)連續(xù)空間中。

為了實(shí)現(xiàn)遍歷 deque 容器的功能，deque 迭代器定義了如下的結(jié)構(gòu)：

template<class T,...>
struct __deque_iterator{
    ...
    T* cur;
    T* first;
    T* last;
    map_pointer node;//map_pointer 等價(jià)于 T**
}

可以看到，迭代器內(nèi)部包含 4 個(gè)指針，它們各自的作用為：

cur：指向當(dāng)前正在遍歷的元素；
first：指向當(dāng)前連續(xù)空間的首地址；
last：指向當(dāng)前連續(xù)空間的末尾地址；
node：它是一個(gè)二級(jí)指針，用于指向 map 數(shù)組中存儲(chǔ)的指向當(dāng)前連續(xù)空間的指針。

借助這 4 個(gè)指針，deque 迭代器對(duì)隨機(jī)訪問迭代器支持的各種運(yùn)算符進(jìn)行了重載，能夠?qū)?deque 分段連續(xù)空間中存儲(chǔ)的元素進(jìn)行遍歷。例如：

//當(dāng)?shù)魈幱诋?dāng)前連續(xù)空間邊緣的位置時(shí)，如果繼續(xù)遍歷，就需要跳躍到其它的連續(xù)空間中，該函數(shù)可用來實(shí)現(xiàn)此功能
void set_node(map_pointer new_node){
    node = new_node;//記錄新的連續(xù)空間在 map 數(shù)組中的位置
    first = *new_node; //更新 first 指針
    //更新 last 指針，difference_type(buffer_size())表示每段連續(xù)空間的長度
    last = first + difference_type(buffer_size());
}
//重載 * 運(yùn)算符
reference operator*() const{return *cur;}
pointer operator->() const{return &(operator *());}
//重載前置 ++ 運(yùn)算符
self & operator++(){
    ++cur;
    //處理 cur 處于連續(xù)空間邊緣的特殊情況
    if(cur == last){
        //調(diào)用該函數(shù)，將迭代器跳躍到下一個(gè)連續(xù)空間中
        set_node(node+1);
        //對(duì) cur 重新賦值
        cur = first;
    }
    return *this;
}
//重置前置 -- 運(yùn)算符
self& operator--(){
    //如果 cur 位于連續(xù)空間邊緣，則先將迭代器跳躍到前一個(gè)連續(xù)空間中
    if(cur == first){
        set_node(node-1);
        cur == last;
    }
    --cur;
    return *this;
}

deque容器的底層實(shí)現(xiàn)

了解了 deque 容器底層存儲(chǔ)序列的結(jié)構(gòu)，以及 deque 容器迭代器的內(nèi)部結(jié)構(gòu)之后，接下來看看 deque 容器究竟是如何實(shí)現(xiàn)的。

deque 容器除了維護(hù)先前講過的 map 數(shù)組，還需要維護(hù) start、finish 這 2 個(gè) deque 迭代器。以下為 deque 容器的定義：

//_Alloc為內(nèi)存分配器
template<class _Ty,
    class _Alloc = allocator<_Ty>>
class deque{
    ...
protected:
    iterator start;
    iterator finish;
    map_pointer map;
...
}

其中，start 迭代器記錄著 map 數(shù)組中首個(gè)連續(xù)空間的信息，finish 迭代器記錄著 map 數(shù)組中最后一個(gè)連續(xù)空間的信息。另外需要注意的是，和普通 deque 迭代器不同，start 迭代器中的 cur 指針指向的是連續(xù)空間中首個(gè)元素；而 finish 迭代器中的 cur 指針指向的是連續(xù)空間最后一個(gè)元素的下一個(gè)位置。

因此，deque 容器的底層實(shí)現(xiàn)如下圖所示：

借助 start 和 finish，以及 deque 迭代器中重載的諸多運(yùn)算符，就可以實(shí)現(xiàn) deque 容器提供的大部分成員函數(shù)，比如：

//begin() 成員函數(shù)
iterator begin() {return start;}
//end() 成員函數(shù)
iterator end() { return finish;}
//front() 成員函數(shù)
reference front(){return *start;}
//back() 成員函數(shù)
reference back(){
    iterator tmp = finish;
    --tmp;
    return *tmp;
}
//size() 成員函數(shù)
size_type size() const{return finish - start;}//deque迭代器重載了 - 運(yùn)算符
//enpty() 成員函數(shù)
bool empty() const{return finish == start;}