STL之deque

deque的基本組成原理

• deque是double ended queue的縮寫，讀作deck（我一直讀錯了，上次去面試把mutex讀錯了搞得很尴尬，是以放在首位哈）。
• deque系由一段一段的定量連續空間構成。一旦有必要在deque的前端或尾端增加新空間，便配置一段定量連續空間，串接在整個deque的頭端或尾端。deque的最大任務，便是在這些分段的定量連續空間上，維護其整體連續的假象，并提供随機存取的借口。避開了“重新配置、複制、釋放”的輪回，代價則是複雜的疊代器架構。
• deque采用一塊所謂的map（注意，不是STL的map容器）作為主要。這裡所謂map是一小塊連續空間，其中每個元素（此處稱為一個節點，node）都是指針，指向另一段（較大的）連續線性空間，稱為緩沖區（實際資料的存放位置）。緩沖區才是deque的儲存空間主體。結構很像一個二維數組，其中map為第一維，緩存區為第二維，deque大緻結構如圖所示：

  

• deque是分段連續的記憶體區域，為了使其看起來像一塊連續的記憶體區域，需要對疊代器進行特殊的設計，進而支援随機通路。

deque疊代器的設計

• 疊代器包含四個部分，cur，first,last,node;其中first指向目前緩存區中的起始位置，last指向目前緩沖區的尾後位置，cur指向目前資料所在位置。大概結構如下圖：

  

• deque容器所有緩沖區的容量都是一樣的，範圍都是:[first,last)。
• deque容器的兩個重要的疊代器
  1. start:綁定到第一個有效的map結點（并不是map的邊界哈，因為map可能存在未被使用的區域）和該結點對應的緩沖區。當然STL将有效的元素防止中間，預留白間放兩邊，這樣做是為了更好地實作首尾的操作。如下圖所示：

     

  2. finish:綁定到最後一個有效的map結點（ 不是下一個位置哈，别被end()給弄傻了 ）和該結點對應的緩沖區。如下圖所示：

     

• start.curr和finish.cur嚴格遵守STL的原則，左閉右開元組[…)，意思是說：start.cur指向的是其所綁定緩沖區第一個有效的元素，指針start.cur的移動方向是first<——-last（相當于–start.cur）；而finish.cur指向的是其所綁定緩沖區的最後一個有效元素的下一個位置，指針finish.cur的移動方向是first——->last（相當于++finish.cur）。記住：start.cur指向的永遠是一個含有實際值的位置，而finish.cur永遠指向的是一個空位置。
• start所綁定的緩沖區已滿的條件是start.cur=start.first，而當該緩沖區為空start.cur=start.last時，start會自動綁定到别的緩沖區（删除最後一個有效元素時發生）；finish所綁定的緩沖 區已滿的條件finish.cur=finish.last，為空的條件是finish.cur=cur.first。

deque容器的插入操作

• 在容器的首部插入 ，push_front(const T &t)。先找到start綁定的緩沖區，判斷該緩沖區是否還有空閑位置(若start.curr==start.first，則表示沒有空閑位置，否則表示有。因為 頭部的 curr指向的是含有實際值的位置，而尾部的curr指向的是含有實際值的下一個位置，這符合stl的規則，即左閉由開的原則,[..) )，如果有則在該空閑位置插入元素t，同時更新start.curr，若沒有空閑位置可以插入元素t，則在start.node（ 這是第一維 ）的前一個位置申請一個緩沖區，同時将 start綁定到該新緩沖區（即設定start的first,last) ，并将start.cur指向新申請緩沖區的最後一個有效的位置（即star.cur=star.last-1)。
• 在容器的尾部插入， push_back(const T& t)。先找到finish所綁定的緩沖區，判斷該緩沖區是否有空閑位置(若finish.curr==finish.last，則表示沒有空閑位置，否則表示有。因為 finish的curr指向的是含有實際值的下一個位置，last表示最後一個實際值的下一個位置，若兩者相等，則表示最後一個空閑位置用完了 ）。
• 在容器的指定位置前插入元素 ，insert(iter,t)、insert(iter,n,t)、insert(iter,b,e)。這裡，我們将容器空間分成三個部分 （前面部分，iter，後面部分） ，在插入之前，我們需要比較前面部分元素的個數與後面部分元素的個數，由于指定位置的插入必然會引起元素的移動（首、尾插入除外），那麼 我們移動的是前後兩部分中，元素個數比較少的那部分元素，這樣做的效率會更高，STL就是凡事以效率為前提 。

删除的注意事項

• 需要特别指的注意的是 ，在首部或尾部的插入操作中，有可能引發在插入端沒有空餘的map空間了，這個時候我們需要特别注意，STL的做法并不是因為該操作端沒有空閑的空間了就直接重新申請新的空間，而是先判斷下另一端是否有足夠的空間（ SGI STL的判斷标準是 map_size>2*已使用的map個數 ），如果空間足夠，則不需要重新配置設定map，隻需要移動下原來已有map元素的指針的位置即可。如果不夠，則重新配置設定（ 三部曲：申請空間、複制元素、删除舊空間 ）。

deque容器的删除操作

• 删除首部元素，pop_front() 。若start所綁定的緩沖區上有多個( 兩個及以上 ）元素，此時隻需将第一個有效元素析構即可destroy(start.curr)，析構完後再将start.cur++；若start所綁定的緩沖區上隻有一個元素，即start.curr==start.last-1，則将該元素析構後destory(start.cur)，需要先将start綁定的緩沖區的空間收回deallocate_node(start.first)，再将start重新綁定map結點（相當于第一維）和緩沖區（相當于第二維） start.set_node(start.node+1)， start.cur=start.first。
• 删除尾部元素，pop_back() 。若finish所綁定的緩沖區上有 1個或多個 元素，此時隻需将最後一個有效元素析構即可destroy(–finish.curr)；若start所綁定的緩沖區是空緩沖區，即finish.curr==finish.first，則先将該空緩沖區的空間釋放掉deallocate_node(finish.first)，再将finish綁定到上一個map結點和緩沖區finish.set_node(finish.node-1)，finish.cur=finish.last-1,最後将最後一個元素析構destroy(finish.cur)。
• 指定位置删除元素，erase(iter)，erase(b,e) 。這裡我隻想提下與插入操作相似的點，那就是删除元素之後，一定會涉及到移動操作，是移動左邊部分的元素還是右邊部分的元素呢？這取決于兩者元素的個數。STL從效率的角度考慮，隻會移動元素個數少的那部分。

使deque疊代器失效的操作

• 在deque的首部或尾部插入操作時，通常情況下疊代器是不會失效的，但是也有例外。 例外情況 是，當在容器的首部或尾部做頻繁的插入操作使得deque的兩端的預留白間用得差不多時 （還記得上面的判斷條件 SGI STL的判斷标準是 map_size>2*已使用的map個數 嗎） 會引起記憶體空間的重新配置（三部曲），這種特殊情況下容器内所有的疊代器都将失效 。
• 在deque的首部或尾部做删除操作時，除了被删除元素所對應的疊代器外，其他任何元素對應的疊代器都不會失效。
• 在deque的中間做插入或删除操作時，可能會使得被插入位置或删除位置的左邊所有疊代器失效，也可能使得其右邊的所有疊代器失效，具體那邊的疊代器失效得視左右兩邊元素的個數而定，元素個數少的那邊的所有疊代器都會失效，而元素個數多的那邊的所有疊代器都不會失效。

參考

1. STL之deque容器的實作架構
2. STL源碼剖析—deque