容器適配器

適配器是一種設(shè)計模式（設(shè)計模式是一套反復(fù)使用的、大部分人知道的代碼設(shè)計經(jīng)驗(yàn)的總結(jié)），該模式試講一個類的接口轉(zhuǎn)化為用戶希望的另一個接口，雖然stack與queue中也可以存放元素，但在STL中并沒有將其劃分為容器，而是成為容器適配器，這是因?yàn)閟tack與隊列只是堆其他容器進(jìn)行了包裝，STL中的stack和queue是使用雙端隊列進(jìn)行封裝的。

雙端隊列

概念

它是一種雙開口的連續(xù)空間數(shù)據(jù)結(jié)構(gòu)（與隊列沒有關(guān)系），雙開口的含義是可以再兩端進(jìn)行插入刪除操作，且時間復(fù)雜度為O(1)，與vector比較，頭插效率比較高，不需要移動數(shù)據(jù)，與list比較，空間利用率高。

結(jié)構(gòu)

deque并不是真正的連續(xù)空間，而是使用一小段連續(xù)的小空間拼接而成，實(shí)際上deque類似于一個動態(tài)的二維數(shù)組，其底層結(jié)構(gòu)如下圖所示：

中控數(shù)組map：?map數(shù)組是一個指針數(shù)組，指向多個buff數(shù)組用來儲存數(shù)據(jù)，當(dāng)buff數(shù)組頭或尾滿了，就新開辟一個buff數(shù)組，其指針存在map的相對應(yīng)位置，當(dāng)map數(shù)組滿了，會對map數(shù)組擴(kuò)容(指針數(shù)組的擴(kuò)容并不會效率低)

deque迭代器

deque所謂的連續(xù)空間是一個假象，是他底層復(fù)雜的迭代器實(shí)現(xiàn)

STL源碼：

typedef T** map_pointer;
T* cur;
T* first;
T* last;
map_pointer node

• cur:是當(dāng)前的node指向的buff數(shù)組當(dāng)前指向的地址
• first：是當(dāng)前node指向的buff數(shù)組，第一個元素的地址。
• last:是當(dāng)前node指向的buff數(shù)組，最后一個元素的地址。
• node：是指向當(dāng)前map數(shù)組對應(yīng)的指針，由于他指向的也是一個指針·，所以為二級指針。

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

雙端隊列，說明他很合適頭插頭刪，尾插尾刪，他去做stack和queue的容器適配器很合適。

缺點(diǎn)：

雙端隊列中間插入刪除非常麻煩，效率不高。

deque是一種折中的方案設(shè)計，隨機(jī)訪問效率不如vector，任意插入刪除不及l(fā)ist

stack模擬

stack是一種容器適配器，專門在具有后進(jìn)先出的上下文環(huán)境中，其刪除只能是在一端進(jìn)行操作。

stack是作為容器適配器被實(shí)現(xiàn)的，容器適配器即是對特定類封裝作為其底層的容器，并提供一組特定的成員函數(shù)來訪問其元素，將特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出 。

stack的底層原理可以是任何標(biāo)椎的容器類模板或者一些特定的容器類，這些容器類應(yīng)該支持以下操作：

• empty:判空操作。
• back:尾部元素獲取。
• push_back：尾部插入元素操作
• pop_back:尾部刪除元素操作。

模擬實(shí)現(xiàn)

template<class T, class Con = deque<T>>
    class stack
    {
    public:
        stack();
        void push(const T& x)
        {
            _c.push_back(x);
        }
        void pop()
        {
            _c.pop_back();
        }
        T& top()
        {
            return _c.back()
        }
        const T& top()const
        {
            return _c.back();
        }
        size_t size()const
        {
            return _c.size();
        }
        bool empty()const
        {
            return _c.empty();
        }
    private:
        Con _c;
    };
?

queue模擬實(shí)現(xiàn)

隊列是一種容器適配器，專門用于在FIFO上下文(先進(jìn)先出)中操作，其中從容器一端插入元素，另一端提取元素

隊列作為容器適配器實(shí)現(xiàn)，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數(shù)來訪問其元素。元素從隊尾入隊列，從隊頭出隊列

底層容器可以是標(biāo)準(zhǔn)容器類模板之一，也可以是其他專門設(shè)計的容器類。該底層容器應(yīng)至少支持以下操作:

• empty：檢測隊列是否為空
• size：返回隊列中有效元素的個數(shù)
• front：返回隊頭元素的引用
• back：返回隊尾元素的引用
• push_back：在隊列尾部入隊列
• pop_front：在隊列頭部出隊列

模擬實(shí)現(xiàn)

template<class T, class Con = deque<T>>
    class queue
    {
        public:
            queue();
            void push(const T& x)
            {
                _c.push_back(x);
            }
            void pop()
            {
                _c.pop_front();
            }
            T& back()
            {
                return _c.back();
            }
            const T& back()const
            {
                return _c.back();
            }
            T& front()
            {
                return _c.front();
            }
            const T& front()const
            {
                return _c.front();
            }
            size_t size()const
            {
                return _c.size();
            }
            bool empty()const
            {
                return _c.empty();
            }
        private:
            Con _c;
    };

?