std :: deque :: push_back/front的複雜性要求

由於前幾天的問題this，有幾件事情一直在困擾着我，關於std::deque::push_back/push_front的複雜性要求與實際的std::deque實現野生。std :: deque :: push_back/front的複雜性要求

上一個問題的結果是，這些操作都要求具有最差情況下的複雜性O(1)。我驗證，這是確實是在c++11的情況下：

從23.3.3.4雙端隊列改性劑
，指的插入，推/佈設前/後

複雜性：複雜性是在插入元件的數量線性加上到deque開始和結束的距離中較小的一個。插入在雙端隊列的開頭或結尾的單個元件或者總是需要一定的時間和使得一個調用T.

這是通過用於索引的O(1)複雜度要求的組合構造，經由operator[]等

問題是，實現並不嚴格地滿足這些要求。

在這兩種msvc和gcc的std::deque實施而言是被阻止的數據結構，由指針的動態陣列的至（固定大小）的塊，其中每個塊中存儲有數量的數據元素。

在最壞的情況下，push_back/front etc可能需要分配一個額外的塊（這是很好的 - 固定大小的分配是O(1)），但它也可能需要調整塊指針的動態數組大小 - 這是不好的，因爲這是O(m)其中m是塊的數量，在一天結束時是O(n)。

很明顯，這仍然是分期付款O(1)的複雜性，因爲一般m << n它將在實踐中相當快。但是，這似乎是一致性問題？

作爲進一步的觀點，我沒有看到如何設計一個嚴格滿足push_back/front etc和的複雜度的數據結構。您可以有塊指針的鏈接列表，但這不會給您所需的operator[]行爲。它可以做到嗎？

來源

2011-12-01 Darren Engwirda

相關（但沒有真正的答案）：http://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl –

@NateKohl：是的確切 - 以及對這個問題的答案似乎證實你不能嚴格滿足所有的複雜性要求... –

在C++ 11 FDIS，我們可以看到：

23.2.3序列容器[sequence.reqmts]

16/表101列出了被提供用於該操作一些類型的序列容器，但不是其他類型。實施應對「容器」欄中顯示的所有容器類型提供這些操作，並應實施它們以便採取分攤的恆定時間。

凡表101名爲可選順序容器操作並列出deque爲push_back和push_front操作。

因此，它似乎更像是您引用的段落中的輕微遺漏。也許值得一個缺陷報告？

請注意，調用構造函數的單個仍然成立。

來源

2011-12-01 08:11:22

這個問題實際上似乎最近引起了一些討論，請參閱例如：http://stackoverflow.com/questions/8627373/what-data-structure-exactly-are-deques-in-c/8628035#8628035和http://stackoverflow.com/questions/8631531/what-does-constant-complexity-really-mean-time-count-of-copies-moves –

@DarrenEngwirda：感謝指針:)我認爲真正的問題是沒有人知道如何實現一個滿足標準要求的'deque'，只有近似......而我也不知道。就我而言，隨機訪問/ O（1）推送/保存參考文獻三部曲是無法管理的，即使採用攤銷O（1）推送。 –

在這個答案中的標準參考有點誤導，因爲它不是複雜性受到限制的唯一地方。通過同樣的條款，人們可以閱讀，索引一個'std :: vector'只需要** amortized **常量時間，但在其他地方清楚地表明，對於任何單個實例來說，這種情況必須是恆定的。類似地，對於'std :: deque :: push_front'，詳細條目（我的副本中的23.3.3.4:3）表示**總是需要在OP中引用的常量時間**，這顯然似乎覆蓋了23.2中所述的內容0.3：16。 –

我懷疑塊指針的重新分配是用幾何增加的大小完成的 - 這是std :: vector的一個常見技巧。我認爲這在技術上是O（log m），但是當你指出n時，作爲一個實際問題它不會影響真實世界的結果。

來源

2011-12-01 01:48:58

我知道你的意思，但標準並沒有真正允許有太多空間可以移動，要求恆定時間總能達到。也許標準可以修改？ –

實際上，幾何增長使其*攤銷* O（1）（如'vector'）。 –

std :: deque :: push_back/front的複雜性要求

回答

相關問題