6 個技巧，提升 C++11 的 vector 性能

AmparoQKDI 8年前發布 | 39K 次閱讀 C/C++開發 C/C++

Vector 就像是 C++ STL 容器的瑞士軍刀。Bjarne Stoutsoup 有一句話 – “一般情況下，如果你需要容器，就用 vector”。像我們這樣的普通人把這句話當作真理，只需要照樣去做。然而，就像其它工具一樣，vector 也只是個工具，它能提高效率，也能降低效率。

這篇文章中我們可以看到 6 種優化使用 vector 的方法。我們會在最常見的使用 vector 的開發任務中看到有效的方法和無效的方法，并以此衡量有效使用 vector 會帶來怎樣的性能提升，并試圖理解為什么能得到這樣的性能提升。

性能測試的搭建和方法:

所有測試都在我的 Surface Book 中運行，這臺筆記本擁有主頻 2.6Ghz 的酷睿 i7 處理器，8 GB 內存，安裝了 Windows 10 操作系統并使用 VS2015 C++ 編譯器編譯運行。
我們會使用 Stopwatch。這個工具由 Kjell 創建，在 https://github.com/KjellKod/Stopwatch 可以找到。
我們會運行每個測試 100 次，然后計算平均運行時間來作為依據。運行測試的代碼在這里。你可以自由下載，用于在你自己的系統中評估 vector 的性能。那里提供的代碼段只反映了一次循環，這讓事件變得簡單。
我們在 vector 中存入 TestStruct 結構的數據，并使用 FillVector() 來填充 vector。它們的定義如下。

// Test struct to be inserted/removed from vector
struct BigTestStruct
{
  int iValue = 1;
  float fValue;
  long lValue;
  double dValue;
  char cNameArr[10];
  int iValArr[100];
};

// Helper function to populate the test vectors
void FillVector(vector<BigTestStruct>& testVector)
{
  for (int i = 0; i < 10000; i++)
  {
    BigTestStruct bt;
    testVector.push_back(bt);
  }
}

馬上開始在 C++ 11 中優化 vector 用法的介紹。

#1 提前分配足夠的空間以避免不必要的重新分配和復制周期

程序員喜歡使用 vector，因為他們只需要往向容器中添加元素，而不用事先操心容器大小的問題。但是，如果由一個容量為 0 的 vector 開始，往里面添加元素會花費大量的運行性能。如果你之前就知道 vector 需要保存多少元素，就應該提前為其分配足夠的空間。

這里有一個簡單的示例，往 vector 里添加 1 萬個測試結構的實例——先進行不預分配空間的測試再進行有預分配的測試。

vector<BigTestStruct> testVector1;
vector<BigTestStruct> testVector2;
sw.Restart();
FillVector(testVector1);
cout << "Time to Fill Vector Without Reservation:" << sw.ElapsedUs() << endl;
sw.Restart();
testVector2.reserve(10000);
FillVector(testVector2);
cout << "Time to Fill Vector With Reservation:" << sw.ElapsedUs() << endl;

在我的計算機中，未預分配空間的情況用了 5145 微秒(us)，而預分配了空間的情況下只用了 1279 微秒，性能提高了 75.14%！！！

這個情況在 Scott Meyers 的書中得到了很好的解釋，這本書叫 Effective STL- 50條有效使用STL的經驗 :

“對于 vector 和 string，在需要更多空間的時候，會做與 realloc 等效的事情。這種類似 realloc 的操作有4個步驟：

1. 分別一個新的內存塊，其容量是容器當前容量的數倍。多數實現中，vector 和 string 容量的提升因子在 1.5 和 2 之間。

2. 從容器原來占用的內存中將元素拷貝到新分配的內存中。

3. 釋放原有內存中的對象。

4. 釋放原有內存。

有了所有這些操作：分配、回收、拷貝和釋放，如果說這些步驟（對于性能）極其昂貴，你一點都不應該感到驚訝。當然，你肯定不希望頻繁的進行這樣的操作。如果這還沒有打動你，那么想想每次進行這些步驟的時候，vector 和 string 中所有的迭代器、指針和引用都會失效。這意味著一個簡單的插入操作，對于其它使用了當前 vector 或 string 中的迭代器、指針或引用的數據結構，都有可能引起對它們進行更新。 ”

#2使用 shrink_to_fit() 釋放 vector 占用的內存， – clear() 或 erase() 不會釋放內存。

與大家所想的相反，使用 erase() 或 clear() 從 vector 中刪除元素并不會釋放分配給 vector 的內存。做個簡單的實驗就可以證明這一點。我們往一個 vector 中添加 100 個元素，然后在這個 vector 上調用 clear() 和 erase()。然后我們可以讓 capacity() 函數告訴我們為這個容器分配的內存可以存入多少元素。

FillVector(testVector1);
size_t capacity = testVector1.capacity();
cout << "Capacity Before Erasing Elements:" << capacity << endl;

testVector1.erase(testVector1.begin(), testVector1.begin() + 3); //
capacity = testVector1.capacity();
cout << "Capacity After Erasing 3 elements Elements:" << capacity << endl;
testVector1.clear();
capacity = testVector1.capacity();
cout << "Capacity After clearing all emements:" << capacity << endl;
testVector1.shrink_to_fit();
capacity = testVector1.capacity();
cout << "Capacity After shrinking the Vector:" << capacity << endl;

下面是輸出：

Capacity Before Erasing Elements:12138
Capacity After Erasing 3 elements Elements:12138
Capacity After clearing all emements:12138
Capacity After shrinking the Vector:0

從上面的輸出可以看到，erase() 或 clear() 不會減少 vector 占用的內存。如果在代碼中到達某一點，不再需要 vector 時候，請使用 std::vector::shrink_to_fit() 方法釋放掉它占用的內存。

請注意，shrink_to_fit() 可能沒有被所有編譯器供應商完全支持。這種情況下，可以使用“Swap 慣用法”來清空 vector，代碼如下：

container<T>( c ).swap( c ); // shrink-to-fit 慣用法，用于清空存儲空間

container<T>().swap( c ); // 用于清空所有內容和存儲空間的慣用法

#3在填充或者拷貝到 vector 的時候，應該使用賦值而不是 insert() 或push_back().

從一個 vector 取出元素來填充另一個 vector 的時候，常有三種方法 – 把舊的 vector 賦值給新的 vector，使用基于迭代器的 std::vector::insert() 或者使用基于循環的 std::vector::push_back()。 這些方法都展示在下面：

vector<BigTestStruct> sourceVector, destinationVector;
FillVector(sourceVector);
// Assign sourceVector to destination vector
sw.Restart();
destinationVector = sourceVector;
cout << "Assigning Vector :" << sw.ElapsedUs() << endl;
//Using std::vector::insert()
vector<BigTestStruct> sourceVector1, destinationVector1;
FillVector(sourceVector1);
sw.Restart();
destinationVector1.insert(destinationVector1.end(),
  sourceVector1.begin(),
  sourceVector1.end());
cout << "Using insert() :" << sw.ElapsedUs() << endl;

這是它們的性能：

賦值: 589.54 us

insert(): 1321.27 us

push_back(): 5354.70 us

我們看到vector 賦值比 insert() 快了 55.38%，比 push_back() 快了 89% 。

為什么會這樣???

賦值非常有效率，因為它知道要拷貝的 vector 有多大，然后只需要通過內存管理一次性拷貝 vector 內部的緩存。

所以，想高效填充 vector，首先應嘗試使用 assignment，然后再考慮基于迭代器的 insert()，最后考慮 push_back。當然，如果你需要從其它類型的容器拷貝元素到 vector 中，賦值的方式不可行。這種情況下，只好考慮基于迭代器的 insert()。

#4遍歷 std::vector 元素的時候，避免使用 std::vector::at() 函數。

遍歷 vector 有如下三種方法：

使用迭代器
使用 std::vector::at() 成員函數
使用下標 – [ ] 運算符

下面展示了每種用法：

//Using an iterator
vector<BigTestStruct> testVectorSum;
FillVector(testVectorSum);
sw.Restart();
int sum = 0;
for (auto it = testVectorSum.begin(); it != testVectorSum.end(); ++it)
{
  sum = sum + it->iValue;
}
cout << "Using Iterator:" << sw.ElapsedUs() << endl;

//Using the at() member function
sw.Restart();
sum = 0;
for (unsigned i = 0; i < testVectorSum.size(); ++i)
{
  sum = sum + testVectorSum.at(i).iValue;
}
cout << "Using at() :" << sw.ElapsedUs() << endl;

// Using the subscript notation
sw.Restart();
sum = 0;
for (unsigned i = 0; i < testVectorSum.size(); ++i)
{
  sum = sum + testVectorSum[i].iValue;
}
cout << "Using subscripting:" << sw.ElapsedUs() << endl;

輸出是：

Using Iterator:0
Using at() :3.73
Using subscripting:0

顯而易見，用 std::vector::at() 函數訪問 vector 元素是最慢的一個。

#5 盡量避免在 vector 前部插入元素

任何在 vetor 前部部做的插入操作其復雜度都是 O(n) 的。在前部插入數據十分低效，因為 vector 中的每個元素項都必須為新的項騰出空間而被復制。如果在 vector 前部連續插入多次，那可能需要重新評估你的總體架構。

做個有趣的嘗試，下面是在 std::vector 前部做插入和在 std::list 前部部做插入的對比：

vector<BigTestStruct> sourceVector3, pushFrontTestVector;
FillVector(sourceVector3);
list<BigTestStruct> pushFrontTestList;
//Push 100k elements in front of the new vector -- this is horrible code !!! 
sw.Restart();
for (unsigned i = 1; i < sourceVector3.size(); ++i)
{
  pushFrontTestVector.insert(pushFrontTestVector.begin(), sourceVector3[i]);
}
cout << "Pushing in front of Vector :" << sw.ElapsedUs() << endl;
// push in front of a list
sw.Restart();
for (unsigned i = 0; i < sourceVector3.size(); ++i)
{
  pushFrontTestList.push_front(sourceVector3[i]);
}
cout << "Pushing in front of list :" << sw.ElapsedUs() << endl;

如果我運行這個測試10，其中使用一個包含100個元素的vector，那么輸出結果如下：

Average of Pushing in front of Vector :11999.4
Average of Pushing in front of list :20.36

在 list 前部部插入操作比在 vector 前部部快大約58836%。不用感到奇怪，因為在 list 前部做元素插入的算法，其復雜度為 O(1)。顯然，vector 包含元素越多，這個性能測試的結果會越差。

#6在向 vector 插入元素的時候使用 emplace_back() 而不是 push_back()。

幾乎趕上 C++11 潮流的每個人都明確地認同“安置”這種往 STL 容器里插入元素的方法。理論上來說，“安置”更有效率。然而所有實踐都表明，有時候性能差異甚至可以忽略不計。

思考下面的代碼：

vector<BigTestStruct> sourceVector4, pushBackTestVector, emplaceBackTestVector;
FillVector(sourceVector4);
//Test push back performance
sw.Restart();
for (unsigned i = 0; i < sourceVector4.size(); ++i)
{
  pushBackTestVector.push_back(sourceVector4[i]);
}
cout << "Using push_back :" << sw.ElapsedUs() << endl;
//Test emplace_back()
sw.Restart();
for (unsigned i = 0; i < sourceVector4.size(); ++i)
{
  emplaceBackTestVector.emplace_back(sourceVector4[i]);
}
cout << "Using emplace_back :" << sw.ElapsedUs() << endl;

如果運行100次，會得到這樣的輸出：

Average Using push_back :5431.58
Average Using emplace_back :5254.64

可以清楚的看到，“安置”函數比插入函數性能更好 – 但只有 177 微秒的差距。在所有情況下，他們大致是相當的。

僅在以下情況下，Emplacement 函數可能會更快：

要添加的值是在 vector 中構造的，而不是賦值的。
傳遞的參數類型與 vector 中保存的類型不同。例如，如果一個向量包含 std :: string，但我們傳遞一個字符串值到該 vector。

即使上述兩個條件都不成立，如本例所示的，你也不要因為在插入時使用 emplacement 而掉以輕心。

結語

與任何第三方統計數據一樣，你不應盲目地依賴此處提供的結果和建議。在不同的操作系統、處理器體系結構和編譯器設置上測試時，你可能遇到很多不確定因素。因此，你需要根據實際數據，自己做出衡量。

來自：https://www.oschina.net/translate/6-tips-supercharge-cpp-11-vector-performance

本文由用戶 AmparoQKDI 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1480476452646.html

C/C++開發 C/C++