C++中最快的動態數據結構

-2

我有一個任務，主要是在C++中增加或刪除數組中的元素。由於數組不是動態的，但對它們的操作速度非常快，所以我一直在尋找一種動態數據結構，它幾乎和運行速度一樣快。我一直在考慮std::vector，但由於它是預定義的，而且非常龐大，所以我擔心對我而言至關重要的操作時間。任何人都可以向我提供一些關於您的觀點的信息嗎？我會很高興得到您的幫助！C++中最快的動態數據結構

編輯：

我真的很抱歉，我沒有列入我的問題的所有重要的一點;下面我想嘗試添加更多的信息：

我會遍歷結構多次的元素和訪問它們以隨機的方式使操作上的元素在每一個可能的位置是可能的
我認爲，將會（取決於測試提供的）在數據結構中的元素以及其「邊緣」附近進行許多操作。

我相信這將有助於我的帖子更清晰，更具體，因此對他人更有用。

謝謝你所有的答案！

來源

2014-03-26 musztard2000

向量通常速度一樣快，但問題是，您在哪裏插入/刪除這些元素？ – chris

從數組末尾添加或刪除數據非常緩慢，矢量只是使用數組作爲基礎結構。 – Dukeling

+1 @chris，你需要提供更多信息。另外，基準測試可能是可以選擇的。 –

參見Mikael Persson的‘容器選擇’圖：在STL執行了將被用於不同的原因

http://www.cim.mcgill.ca/~mpersson/pics/STLcontainerChoices.png

來源

2014-03-26 19:01:35

@JodyHagins：我在你的回答中提到你最後一段。 –

[這裏]（http://www.cim.mcgill.ca/~mpersson/pics/STLcontainerChoices.png）是我製作的另一個類似的流程圖。我不認爲這是無可爭議的..這只是我的承擔。 –

@MikaelPersson：這很好，我可以開始使用它嗎？ –

的不同的數據結構。因此，結構在結構的開始，中間或結束或者結構元素的隨機訪問時的插入/刪除速度不同。

來源

2014-03-26 19:04:02 Veritas

一個很好的STL容器的簡短的對比：

http://john-ahlgren.blogspot.com/2013/10/stl-container-performance.html

如果可以讓你使用一個關聯數組，地圖至少保證的O插入/查找時間（log n）的其對於大量的數據/大量的插入和刪除，比非向後插入的向量對O（n）的保證要快得多。

不知道他們將在這裏還是不行，這個環節也說明基準的一些圖表使用幾個不同的容器隨機插入/刪除/搜索/填充/排序等：

http://www.baptiste-wicht.com/2012/12/cpp-benchmark-vector-list-deque/

最後，從一個流程圖，這樣可以幫助你的容器上決定：

In which scenario do I use a particular STL container?

雖然並不完美，但它仍然可能會變成一個向量是你最好的選擇。

來源

2014-03-26 19:07:38 Instinct

使用數組實現的鏈表是否滿足您的需求？

class AList 
{ 
    public: 

     AList() 
     { 
     for (int = 0; i != 256; ++i) 
     { 
      nodes[i].prev = (i-1+256)%256; 
      nodes[i].next = (i+1)%256; 
     } 
     } 

     int const& operator[](int index) 
     { 
     // Deal with the case where nodes[index].isSet == false 
     return nodes[index].data; 
     } 

     // Not sure what the requirements are for adding 
     // and removing items from the list. 
     // 
     // add(); 
     // remove(); 

    private: 

     struct Node 
     { 
     Node() : data(0), prev(0), next(0), isSet(false) {} 

     int data; 
     unsigned char prev; 
     unsigned char next; 
     bool isSet; 
     }; 

     Node nodes[256]; 
};

來源

2014-03-26 20:17:20

C++中最快的動態數據結構

回答

相關問題