在STL類模板中插入操作

Question

我有一個測試來了，它似乎有些問題涉及到STL類模板函數。許多處理算法的複雜性，所以我試圖讓基本操作的複雜性下降。我感到困惑的是插入操作。插入操作需要特定的容器允許進行插入開始從一些位置由一個iterator指出：

vector<int> vector1; 

for (int i=1; i<6; i++) vector1.push_back(i); 

vector<int>::iterator it; 

it = vector1.begin(); 

vector1.insert(it+2,10); 

現在，我認識到，這在插入操作將承擔大部分插入操作線性時間。但是，如果我插入單個項目，這是否仍然需要線性時間？我問這是因爲對於STL列表，插入單個項目需要一定的時間。我覺得這是因爲名單是一個動態雙鏈環形鏈。

載體是動態的，連續的存儲結構，因此這意味着，對於前矢量任何插入[大小-1]中，插入後的所有項目將有一個單位向上移動？

現在，爲雙層。我正在考慮將STL作爲一個由數組中的指針指向的單鏈鏈接系統;它是否正確？如果是這樣的話，單個插入到一個deque中，而不是在前面或後面，是O（1）？

謝謝，很抱歉有這麼多問題。

Answer 1

這裏有一些注意事項：

• 正如你提到的，插入到std::list需要O(1)時間。
• 正如你提到的，插入到std::vector將需要移動向量的所有剩餘的元素一個後排空間，這需要時間O(n)。
• 該標準不要求具體的實施雙端的，但它確實需要插入到前後採取O(1)時間。
• 然而，雙端做不要求O(1)插入時間，如果你插入容器中。
• 作爲題外話，載體僅如果插入在所述容器的所述端部提供O(1)插入時間。
• cppreference給出了一個關於什麼感覺是deques的頻繁實現方法的評論。它表示常見的實現是一系列固定長度的數組。所以我們有可以存儲16個元素的數組，我們有一個std::list（或多或少）這些數組。
• 據我所知，實現 可能實現 std::deque相同 sd::list。但是，如果不這樣做，可能會有性能改進。 如果一個特定的實現做到了這一點，那麼插入一個deque的中間就是O（1）。但是，這不是必需的。
• A std::deque不能實現爲std::list，因爲它提供了一個隨機訪問迭代器。這意味着deque::at(4)需要在恆定時間內提供該迭代​​器。 A std::list不能這樣做。

---

在問候一下，爲什麼通用deque::insert將O(n)的評論，這是我的想法。假設我們使用cppreference的deque實現。

讓我們創建一個具有10個元素的deque。插入一個接一個。我們假設，deque是由4個元素的數組實現的。

因此，目前的雙端隊列，實現爲：

[ E, E, E, E ] <-> [ E, E, E, E ] <-> [ E, E, _, _ ] 

讓我們在後面插入一個元素。

[ E, E, E, E ] <-> [ E, E, E, E ] <-> [ E, E, E, _ ] 

讓我們在前面

[ _, _, _, E] <-> [ E, E, E, E ] <-> [ E, E, E, E ] <-> [ E, E, E, _ ] 

所有這些行動的意義，他們如何能爲Ø工作插入元件（1）。

如果我們在數組中間插入了一個元素，該怎麼辦？

[ _, _, _, E] <-> [ E, E, E, E ] <-> [ E, E, E, E ] <-> [ E, E, E, _ ] 
            ^I want to insert here! 

要做到這一點，我需要將7個元素移開。這就是爲什麼這個操作可能是O(n)。

Answer 2

如果要插入單個項目爲載體，將仍然需要，因爲你提到的原因線性時間。

該deque實現特定於實施者。然而，插入到不在前面或後面的位置很可能是線性時間（不是恆定時間）。