超速向量的push_back

Question

我試圖加快矢量::的push_back時容量不能被預測

當儲備可用的push_back在容器的端部將新的元素，然後結束標記被移動的載體。在使用所有保留後，push_back可能會觸發重新分配，這是一個緩慢的過程。
爲了加快速度，預留幾個即將到來的push_back重新生成，沒有重新分配時，爲空。你認爲這個代碼如何幫助實現這個目標？

#ifndef __VECTOR_HPP 
#define __VECTOR_HPP 
#include <exception> 
#include "Concept.hpp" //Concept::RESA constant 
#include <vector> 
template <typename T> 
class Vector : public std::vector<T> { 
public : 
    void push_back (T t) { 
    if (std::vector<T>::size() == std::vector<T>::capacity()) { 
     std::vector<T>::reserve ((size_t) Concept::RESA); 
    } 
    std::vector<T>::push_back (t); 
    } 
}; 
#endif 

測試程序：

#include "Vector.hpp" 

int main (int argc, char* argv []) { 
    { 
    std::vector<size_t> v0; 
    clock_t t (clock()); 
    size_t duration (0); 
    for (size_t i (0); i != 10000000; i++) { 
     v0.push_back (i); 
    } 
    duration = (size_t) (clock() -t); 
    std::cout << "duration old push_back == " << duration << " ticks" << std::endl; 
    } 
    { 
    size_t duration (0); 
    Vector<size_t> v1; 
    clock_t t (clock()); 
    for (size_t i (0); i != 10000000; i++) { 
     v1.push_back (i); 
    } 
    duration = (size_t) (clock() -t ); 
    std::cout << "duration new push_back == " << duration << " ticks" << std::endl; 
    } 
} 

結果：

一個概念:: RESA == 8192，並應用建議，這裏有一個聯想ThinkCentre icore5結果（Linux的Debian的， g ++）：

持續時間old push_back == 105317 ticks

duration new push_back == 87156 ticks

Answer 1

確實push_back可能觸發器重新分配，這是一個緩慢的過程。
雖然每個單獨的push_back都不會這樣做，但它會每次都會保留指數級更多的內存，因此如果您事先具有結果向量大小的良好近似值，則明確的reserve纔有意義。

換句話說，std::vector已經照顧到你在代碼中建議的內容。

另一點：there is a reserve method，它比插入和擦除元素的目的更好，最顯着的是它不創建和銷燬實際的對象。

具有諷刺意味的是，@Sopel提到在你的課堂中用reserve代替插入/擦除會禁止向量的增長分期，使你的代碼成爲幾個錯誤（有點）取消對方的好例子。

Answer 2

您的代碼有幾個問題。

• 你基本上確定一個類型非常相似，std::vector與std::vector的唯一成員。爲什麼不首先使用std::vector？

• 您的push_back()功能太糟糕了。讓我先解釋一下std::vector<>::push_back()實際上做了什麼。

  1. 如果size()<capacity()：它只是在複製所述塊的端部的新的元素和遞增end標記。 這是最常見的情況。

  2. 僅如果size()==capacity()，需要重新分配及

     1. 它分配新的內存塊中，通常的電流容量
     2. 它的所有數據移動到開始新塊
     的兩次
     3. 它解除分配的存儲器中的舊的塊
     4. 它最後在數據的末端構建了一個新的元件

  現在讓我們來看看你的

  void push_back (const T& t) { 
      if (val_.size() == val_.capacity()) { 
      val_.insert (val_.end(), resa_.begin(), resa_.end()); 
      auto i = val_.end(); 
      i -= (size_t) Concept::RESA; 
      val_.erase (i, val_.end()); 
      } 
      val_.push_back (t); 
  } 
  

  做什麼，如果val_.size()==val_.capacity()：

  1. 它在val_.end()insert()的默認構造的元素。爲此，std::vector::insert()執行以下操作：
     1. 它分配一個新的內存塊，足夠大以容納舊數據加上要插入的數據，但可能更大。
     2. 它的所有數據移動到開始新塊的
     3. 它解除分配的存儲器中的舊的塊
     4. 其複製到在舊數據的最後被插入的元件
  2. 它破壞所有新插入的元素。
  3. 如果最後在數據的末尾構建新元素（不需要重新分配）。

  因此，你的功能也需要重新分配大約頻繁純std::push_back()和完全不必要複製，結構，然後破壞元素的整個塊。有無法避免重新分配當你想連續內存佈局（如std::vector承諾）和不知道最終的大小提前。如果這些要求中的任何一個可以被刪除，您可以避免重新分配：通過std::vector<>::reserve()或使用具有非連續內存的容器（例如std::deque）。