Vector 就像是 C++ STL 容器的瑞士軍刀。Bjarne Stoutsoup 有一句話 :
"一般情況下，如果你需要容器，就用 vector"。
像我們這樣的普通人把這句話當(dāng)作真理，只需要照樣去做。然而，就像其它工具一樣，vector 也只是個(gè)工具，它能提高效率，也能降低效率。
這篇文章中我們可以看到 6 種優(yōu)化使用 vector 的方法。我們會(huì)在最常見(jiàn)的使用 vector 的開(kāi)發(fā)任務(wù)中看到有效的方法和無(wú)效的方法，并以此衡量有效使用 vector 會(huì)帶來(lái)怎樣的性能提升，并試圖理解為什么能得到這樣的性能提升。
性能測(cè)試的搭建和方法:
所有測(cè)試都在我的 Surface Book 中運(yùn)行，這臺(tái)筆記本擁有主頻 2.6Ghz 的酷睿 i7 處理器，8 GB 內(nèi)存，安裝了 Windows 10 操作系統(tǒng)并使用 VS2015 C++ 編譯器編譯運(yùn)行。
我們會(huì)使用 Stopwatch。這個(gè)工具由 Kjell 創(chuàng)建，在 https://github.com/KjellKod/Stopwatch 可以找到。
我們會(huì)運(yùn)行每個(gè)測(cè)試 100 次，然后計(jì)算平均運(yùn)行時(shí)間來(lái)作為依據(jù)。運(yùn)行測(cè)試的代碼在這里。你可以自由下載，用于在你自己的系統(tǒng)中評(píng)估 vector 的性能。那里提供的代碼段只反映了一次循環(huán)，這讓事件變得簡(jiǎn)單。
我們?cè)?vector 中存入 TestStruct 結(jié)構(gòu)的數(shù)據(jù)，并使用 FillVector() 來(lái)填充 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);
}
}
馬上開(kāi)始在 C++ 11 中優(yōu)化 vector 用法的介紹。
1 提前分配足夠的空間以避免不必要的重新分配和復(fù)制周期
程序員喜歡使用 vector，因?yàn)樗麄冎恍枰蛉萜髦刑砑釉?，而不用事先操心容器大小的?wèn)題。但是，如果由一個(gè)容量為 0 的 vector 開(kāi)始，往里面添加元素會(huì)花費(fèi)大量的運(yùn)行性能。如果你之前就知道 vector 需要保存多少元素，就應(yīng)該提前為其分配足夠的空間。
這里有一個(gè)簡(jiǎn)單的示例，往 vector 里添加 1 萬(wàn)個(gè)測(cè)試結(jié)構(gòu)的實(shí)例——先進(jìn)行不預(yù)分配空間的測(cè)試再進(jìn)行有預(yù)分配的測(cè)試。
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;
在我的計(jì)算機(jī)中，未預(yù)分配空間的情況用了 5145 微秒(us)，而預(yù)分配了空間的情況下只用了 1279 微秒，性能提高了 75.14%！?。?/p>
這個(gè)情況在 Scott Meyers 的書(shū)中得到了很好的解釋，這本書(shū)叫 Effective STL-50條有效使用STL的經(jīng)驗(yàn):
“對(duì)于 vector 和 string，在需要更多空間的時(shí)候，會(huì)做與 realloc 等效的事情。這種類似 realloc 的操作有4個(gè)步驟：
- 分別一個(gè)新的內(nèi)存塊，其容量是容器當(dāng)前容量的數(shù)倍。多數(shù)實(shí)現(xiàn)中，vector 和 string 容量的提升因子在 1.5 和 2 之間。
- 從容器原來(lái)占用的內(nèi)存中將元素拷貝到新分配的內(nèi)存中。
- 釋放原有內(nèi)存中的對(duì)象。
- 釋放原有內(nèi)存。
有了所有這些操作：分配、回收、拷貝和釋放，如果說(shuō)這些步驟（對(duì)于性能）極其昂貴，你一點(diǎn)都不應(yīng)該感到驚訝。當(dāng)然，你肯定不希望頻繁的進(jìn)行這樣的操作。如果這還沒(méi)有打動(dòng)你，那么想想每次進(jìn)行這些步驟的時(shí)候，vector 和 string 中所有的迭代器、指針和引用都會(huì)失效。這意味著一個(gè)簡(jiǎn)單的插入操作，對(duì)于其它使用了當(dāng)前 vector 或 string 中的迭代器、指針或引用的數(shù)據(jù)結(jié)構(gòu)，都有可能引起對(duì)它們進(jìn)行更新?！?/p>
2 使用 shrink_to_fit() 釋放 vector 占用的內(nèi)存， – clear() 或 erase() 不會(huì)釋放內(nèi)存
與大家所想的相反，使用 erase() 或 clear() 從 vector 中刪除元素并不會(huì)釋放分配給 vector 的內(nèi)存。做個(gè)簡(jiǎn)單的實(shí)驗(yàn)就可以證明這一點(diǎn)。我們往一個(gè) vector 中添加 100 個(gè)元素，然后在這個(gè) vector 上調(diào)用 clear() 和 erase()。然后我們可以讓 capacity() 函數(shù)告訴我們?yōu)檫@個(gè)容器分配的內(nèi)存可以存入多少元素。
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() 不會(huì)減少 vector 占用的內(nèi)存。如果在代碼中到達(dá)某一點(diǎn)，不再需要 vector 時(shí)候，請(qǐng)使用 std::vector::shrink_to_fit() 方法釋放掉它占用的內(nèi)存。
請(qǐng)注意，shrink_to_fit() 可能沒(méi)有被所有編譯器供應(yīng)商完全支持。這種情況下，可以使用“Swap 慣用法”來(lái)清空 vector，代碼如下：
container<T>( c ).swap( c ); // shrink-to-fit 慣用法，用于清空存儲(chǔ)空間
container<T>().swap( c ); // 用于清空所有內(nèi)容和存儲(chǔ)空間的慣用法
如果你對(duì)此感興趣，請(qǐng)查看“C++ Coding Standards: 101 Rules, Guidelines, and Best Practices”一書(shū)的條款# 82，其中有針對(duì) swap 慣用法的細(xì)節(jié)介紹。
3 在填充或者拷貝到 vector 的時(shí)候，應(yīng)該使用賦值而不是 insert() 或push_back()
從一個(gè) vector 取出元素來(lái)填充另一個(gè) vector 的時(shí)候，常有三種方法 – 把舊的 vector 賦值給新的 vector，使用基于迭代器的 std::vector::insert() 或者使用基于循環(huán)的 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% 。
為什么會(huì)這樣???
賦值非常有效率，因?yàn)樗酪截惖?vector 有多大，然后只需要通過(guò)內(nèi)存管理一次性拷貝 vector 內(nèi)部的緩存。
所以，想高效填充 vector，首先應(yīng)嘗試使用 assignment，然后再考慮基于迭代器的 insert()，最后考慮 push_back。當(dāng)然，如果你需要從其它類型的容器拷貝元素到 vector 中，賦值的方式不可行。這種情況下，只好考慮基于迭代器的 insert()。
4 遍歷 std::vector 元素的時(shí)候，避免使用 std::vector::at() 函數(shù)
遍歷 vector 有如下三種方法：
使用迭代器
使用 std::vector::at() 成員函數(shù)
使用下標(biāo) – [ ] 運(yùn)算符
下面展示了每種用法：
//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
顯而易見(jiàn)，用 std::vector::at() 函數(shù)訪問(wèn) vector 元素是最慢的一個(gè)。
5 盡量避免在 vector 前部插入元素
任何在 vetor 前部部做的插入操作其復(fù)雜度都是 O(n) 的。在前部插入數(shù)據(jù)十分低效，因?yàn)?vector 中的每個(gè)元素項(xiàng)都必須為新的項(xiàng)騰出空間而被復(fù)制。如果在 vector 前部連續(xù)插入多次，那可能需要重新評(píng)估你的總體架構(gòu)。
做個(gè)有趣的嘗試，下面是在 std::vector 前部做插入和在 std::list 前部部做插入的對(duì)比：
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;
如果我運(yùn)行這個(gè)測(cè)試10，其中使用一個(gè)包含100個(gè)元素的vector，那么輸出結(jié)果如下：
Average of Pushing in front of Vector :11999.4
Average of Pushing in front of list :20.36
在 list 前部部插入操作比在 vector 前部部快大約58836%。不用感到奇怪，因?yàn)樵?list 前部做元素插入的算法，其復(fù)雜度為 O(1)。顯然，vector 包含元素越多，這個(gè)性能測(cè)試的結(jié)果會(huì)越差。
6 在向 vector 插入元素的時(shí)候使用 emplace_back() 而不是 push_back()。
幾乎趕上 C++11 潮流的每個(gè)人都明確地認(rèn)同“安置”這種往 STL 容器里插入元素的方法。理論上來(lái)說(shuō)，“安置”更有效率。然而所有實(shí)踐都表明，有時(shí)候性能差異甚至可以忽略不計(jì)。
思考下面的代碼：
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;
如果運(yùn)行100次，會(huì)得到這樣的輸出：
Average Using push_back :5431.58
Average Using emplace_back :5254.64
可以清楚的看到，“安置”函數(shù)比插入函數(shù)性能更好 – 但只有 177 微秒的差距。在所有情況下，他們大致是相當(dāng)?shù)摹?/p>
僅在以下情況下，Emplacement 函數(shù)可能會(huì)更快：
- 要添加的值是在 vector 中構(gòu)造的，而不是賦值的。
- 傳遞的參數(shù)類型與 vector 中保存的類型不同。例如，如果一個(gè)向量包含 std :: string，但我們傳遞一個(gè)字符串值到該 vector。
即使上述兩個(gè)條件都不成立，如本例所示的，你也不要因?yàn)樵诓迦霑r(shí)使用 emplacement 而掉以輕心。
更多關(guān)于 emplacement vs. insertion 的詳細(xì)信息，請(qǐng)查看 Scott Meyer 的“Effective Modern C++: 42 Specific Ways to Improve Your Use of C++11 and C++14“一書(shū)中的條目＃42。
結(jié)語(yǔ)
與任何第三方統(tǒng)計(jì)數(shù)據(jù)一樣，你不應(yīng)盲目地依賴此處提供的結(jié)果和建議。在不同的操作系統(tǒng)、處理器體系結(jié)構(gòu)和編譯器設(shè)置上測(cè)試時(shí)，你可能遇到很多不確定因素。因此，你需要根據(jù)實(shí)際數(shù)據(jù)，自己做出衡量。
