矢量與動態數組相比，速度有很大差異嗎？

現在我正在編寫解決車輛路徑問題的一些代碼。爲此，一個重要的決定是選擇如何對解決方案進行編碼。一個解決方案包含幾條路線，每個車輛一個。每條路線都有客戶訪問順序，路線負載和路線長度。要對解決方案信息進行修改，我還需要快速找到一些信息。例如，
哪條路線是客戶所在？
路線有哪些客戶？
路線中有多少個節點？
節點前面或後面有什麼節點？矢量與動態數組相比，速度有很大差異嗎？

現在，我想使用以下結構來保持解決方案。

struct Sol 
{ 
    vector<short> nextNode; // show what is the next node of each node; 
    vector<short> preNode; //show what is the preceding node 
    vector<short> startNode; 
    vector<short> rutNum; 
    vector<short> rutLoad; 
    vector<float> rutLength; 
    vector<short> rutSize; 
};

每個向量的通用大小是實例相關的，在200-2000之間。

我聽說有可能使用動態數組來完成這項工作。但在我看來，動態數組更復雜。必須找到內存並釋放內存。這裏我的問題是雙重的。

如何使用動態數組來實現相同的目的？如何定義結構或類，以便內存位置和發佈可以輕鬆處理？

使用動態數組會比使用矢量更快嗎？假設解決方案結構需要被訪問百萬次。

來源

2011-10-07 Jackie

爲什麼你有一個成員數組的結構，而不是一個具有成員的結構數組？後者不那麼容易混淆，不易出錯並且速度更快。 –

每個陣列中的信息是不同的，而不是相同的項目 – Jackie

由於後者基本上是前者的一個非常薄的包裝，因此很難在動態數組和矢量之間看到可觀的性能差異。另外請記住，使用vector將顯着減少錯誤。然而，可能存在的情況是一些信息被更好地存儲在不同類型的容器中，例如，在std::map。以下內容可能會引起您的興趣：What are the complexity guarantees of the standard containers?

重要的是對使用的容器類型進行一些思考。然而，當談到微型優化（例如向量與動態數組）時，最好的策略是首先對代碼進行剖析，然後只關注代碼中證明是真實的部分 - 而不是假設 - 的瓶頸。

來源

2011-10-07 16:48:08 NPE

感謝您的答案。我喜歡使用矢量，但如果使用動態數組可以使代碼更快，那麼我會選擇它。這是我主要希望知道的。有沒有我們用於比較的開源代碼？ – Jackie

它不會更快...... – DanDan

向量的代碼很可能比你自己寫的動態數組代碼更好，更高效。只有在分析顯示在vector上花費了大量時間時，我纔會考慮編寫自己的容易出錯的替換。另請參見Dynamically allocated arrays or std::vector

來源

2011-10-07 16:54:21

我正在使用MSVC，並且實現看起來儘可能快。

訪問通過操作[]數組是：

return (*(this->_Myfirst + _Pos));

，你會得到與動態內存這是一樣快。

您將得到的唯一開銷是在內存中使用一個向量，它似乎創建了一個指向該向量開始，向量結束和當前序列結束的指針。如果您使用的是動態數組，那麼這只是比您需要的更多的兩個指針。你只是創造了200-2000個，我懷疑記憶會變得那麼緊張。

我相信其他stl實現非常相似。我會吸收矢量存儲的次要成本，並將其用於您的項目中。

來源

2011-10-07 17:02:27 DanDan

內存使用不是我最關心的問題。速度是。 – Jackie

矢量與動態數組相比，速度有很大差異嗎？

回答

相關問題