deque容器的存儲結構

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

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

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

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

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

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

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

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

為了實現(xiàn)遍歷 deque 容器的功能，deque 迭代器定義了如下的結構：

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

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

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

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

//當?shù)魈幱诋斍斑B續(xù)空間邊緣的位置時，如果繼續(xù)遍歷，就需要跳躍到其它的連續(xù)空間中，該函數(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());
}
//重載 * 運算符
reference operator*() const{return *cur;}
pointer operator->() const{return &(operator *());}
//重載前置 ++ 運算符
self & operator++(){
    ++cur;
    //處理 cur 處于連續(xù)空間邊緣的特殊情況
    if(cur == last){
        //調用該函數(shù)，將迭代器跳躍到下一個連續(xù)空間中
        set_node(node+1);
        //對 cur 重新賦值
        cur = first;
    }
    return *this;
}
//重置前置 -- 運算符
self& operator--(){
    //如果 cur 位于連續(xù)空間邊緣，則先將迭代器跳躍到前一個連續(xù)空間中
    if(cur == first){
        set_node(node-1);
        cur == last;
    }
    --cur;
    return *this;
}

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

了解了 deque 容器底層存儲序列的結構，以及 deque 容器迭代器的內部結構之后，接下來看看 deque 容器究竟是如何實現(xiàn)的。

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

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

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

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

借助 start 和 finish，以及 deque 迭代器中重載的諸多運算符，就可以實現(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迭代器重載了 - 運算符
//enpty() 成員函數(shù)
bool empty() const{return finish == start;}

stack和queue的原理

由stack和queue源碼可知，其實stack和queue是將deque容器進行再封裝，其底層是一個deque容器。對stack和queue操作，其實間接操作的是deque容器。

到此這篇關于C++ deque/queue/stack的底層原理的文章就介紹到這了,更多相關C++ deque/queue/stack的底層原理內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論