Vector 就像是 C++ STL 容器的瑞士軍刀诈泼。Bjarne Stoutsoup 有一句話 :
"一般情況下，如果你需要容器煤禽，就用 vector"铐达。
像我們這樣的普通人把這句話當(dāng)作真理，只需要照樣去做檬果。然而瓮孙，就像其它工具一樣，vector 也只是個(gè)工具选脊，它能提高效率杭抠，也能降低效率。
這篇文章中我們可以看到 6 種優(yōu)化使用 vector 的方法恳啥。我們會在最常見的使用 vector 的開發(fā)任務(wù)中看到有效的方法和無效的方法偏灿，并以此衡量有效使用 vector 會帶來怎樣的性能提升，并試圖理解為什么能得到這樣的性能提升钝的。
性能測試的搭建和方法:
所有測試都在我的 Surface Book 中運(yùn)行翁垂，這臺筆記本擁有主頻 2.6Ghz 的酷睿 i7 處理器，8 GB 內(nèi)存扁藕，安裝了 Windows 10 操作系統(tǒng)并使用 VS2015 C++ 編譯器編譯運(yùn)行沮峡。
我們會使用 Stopwatch。這個(gè)工具由 Kjell 創(chuàng)建亿柑，在 https://github.com/KjellKod/Stopwatch 可以找到。
我們會運(yùn)行每個(gè)測試 100 次棍弄，然后計(jì)算平均運(yùn)行時(shí)間來作為依據(jù)望薄。運(yùn)行測試的代碼在這里。你可以自由下載呼畸，用于在你自己的系統(tǒng)中評估 vector 的性能痕支。那里提供的代碼段只反映了一次循環(huán)，這讓事件變得簡單蛮原。
我們在 vector 中存入 TestStruct 結(jié)構(gòu)的數(shù)據(jù)卧须，并使用 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 中優(yōu)化 vector 用法的介紹花嘶。
1 提前分配足夠的空間以避免不必要的重新分配和復(fù)制周期
程序員喜歡使用 vector笋籽，因?yàn)樗麄冎恍枰蛉萜髦刑砑釉兀挥檬孪炔傩娜萜鞔笮〉膯栴}椭员。但是车海，如果由一個(gè)容量為 0 的 vector 開始，往里面添加元素會花費(fèi)大量的運(yùn)行性能隘击。如果你之前就知道 vector 需要保存多少元素侍芝，就應(yīng)該提前為其分配足夠的空間。
這里有一個(gè)簡單的示例埋同，往 vector 里添加 1 萬個(gè)測試結(jié)構(gòu)的實(shí)例——先進(jìn)行不預(yù)分配空間的測試再進(jìn)行有預(yù)分配的測試州叠。
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%！Ｓ炊楼熄！
這個(gè)情況在 Scott Meyers 的書中得到了很好的解釋，這本書叫 Effective STL-50條有效使用STL的經(jīng)驗(yàn):
“對于 vector 和 string浩峡，在需要更多空間的時(shí)候可岂，會做與 realloc 等效的事情。這種類似 realloc 的操作有4個(gè)步驟：
- 分別一個(gè)新的內(nèi)存塊翰灾，其容量是容器當(dāng)前容量的數(shù)倍缕粹。多數(shù)實(shí)現(xiàn)中，vector 和 string 容量的提升因子在 1.5 和 2 之間纸淮。
- 從容器原來占用的內(nèi)存中將元素拷貝到新分配的內(nèi)存中平斩。
- 釋放原有內(nèi)存中的對象。
- 釋放原有內(nèi)存咽块。
有了所有這些操作：分配绘面、回收、拷貝和釋放侈沪，如果說這些步驟（對于性能）極其昂貴揭璃，你一點(diǎn)都不應(yīng)該感到驚訝。當(dāng)然亭罪，你肯定不希望頻繁的進(jìn)行這樣的操作瘦馍。如果這還沒有打動你，那么想想每次進(jìn)行這些步驟的時(shí)候应役，vector 和 string 中所有的迭代器情组、指針和引用都會失效燥筷。這意味著一個(gè)簡單的插入操作，對于其它使用了當(dāng)前 vector 或 string 中的迭代器院崇、指針或引用的數(shù)據(jù)結(jié)構(gòu)肆氓，都有可能引起對它們進(jìn)行更新⊙谴啵”
2 使用 shrink_to_fit() 釋放 vector 占用的內(nèi)存做院， – clear() 或 erase() 不會釋放內(nèi)存
與大家所想的相反，使用 erase() 或 clear() 從 vector 中刪除元素并不會釋放分配給 vector 的內(nèi)存濒持。做個(gè)簡單的實(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() 不會減少 vector 占用的內(nèi)存官套。如果在代碼中到達(dá)某一點(diǎn)酒奶，不再需要 vector 時(shí)候，請使用 std::vector::shrink_to_fit() 方法釋放掉它占用的內(nèi)存奶赔。
請注意惋嚎，shrink_to_fit() 可能沒有被所有編譯器供應(yīng)商完全支持。這種情況下站刑，可以使用“Swap 慣用法”來清空 vector另伍，代碼如下：
container<T>( c ).swap( c ); // shrink-to-fit 慣用法，用于清空存儲空間
container<T>().swap( c ); // 用于清空所有內(nèi)容和存儲空間的慣用法
如果你對此感興趣绞旅，請查看“C++ Coding Standards: 101 Rules, Guidelines, and Best Practices”一書的條款# 82摆尝，其中有針對 swap 慣用法的細(xì)節(jié)介紹。
3 在填充或者拷貝到 vector 的時(shí)候因悲，應(yīng)該使用賦值而不是 insert() 或push_back()
從一個(gè) vector 取出元素來填充另一個(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% 。
為什么會這樣???
賦值非常有效率蝎土，因?yàn)樗酪截惖?vector 有多大视哑，然后只需要通過內(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
顯而易見，用 std::vector::at() 函數(shù)訪問 vector 元素是最慢的一個(gè)晴埂。
5 盡量避免在 vector 前部插入元素
任何在 vetor 前部部做的插入操作其復(fù)雜度都是 O(n) 的究反。在前部插入數(shù)據(jù)十分低效，因?yàn)?vector 中的每個(gè)元素項(xiàng)都必須為新的項(xiàng)騰出空間而被復(fù)制儒洛。如果在 vector 前部連續(xù)插入多次精耐，那可能需要重新評估你的總體架構(gòu)。
做個(gè)有趣的嘗試琅锻，下面是在 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;
如果我運(yùn)行這個(gè)測試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è)性能測試的結(jié)果會越差郁油。
6 在向 vector 插入元素的時(shí)候使用 emplace_back() 而不是 push_back()本股。
幾乎趕上 C++11 潮流的每個(gè)人都明確地認(rèn)同“安置”這種往 STL 容器里插入元素的方法。理論上來說桐腌，“安置”更有效率拄显。然而所有實(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次躬审，會得到這樣的輸出：
Average Using push_back :5431.58
Average Using emplace_back :5254.64
可以清楚的看到，“安置”函數(shù)比插入函數(shù)性能更好 – 但只有 177 微秒的差距蟆盐。在所有情況下承边，他們大致是相當(dāng)?shù)摹?/p>
僅在以下情況下，Emplacement 函數(shù)可能會更快：
- 要添加的值是在 vector 中構(gòu)造的石挂，而不是賦值的博助。
- 傳遞的參數(shù)類型與 vector 中保存的類型不同。例如痹愚，如果一個(gè)向量包含 std :: string富岳，但我們傳遞一個(gè)字符串值到該 vector蛔糯。
即使上述兩個(gè)條件都不成立，如本例所示的窖式，你也不要因?yàn)樵诓迦霑r(shí)使用 emplacement 而掉以輕心蚁飒。
更多關(guān)于 emplacement vs. insertion 的詳細(xì)信息，請查看 Scott Meyer 的“Effective Modern C++: 42 Specific Ways to Improve Your Use of C++11 and C++14“一書中的條目＃42萝喘。
結(jié)語
與任何第三方統(tǒng)計(jì)數(shù)據(jù)一樣淮逻，你不應(yīng)盲目地依賴此處提供的結(jié)果和建議。在不同的操作系統(tǒng)阁簸、處理器體系結(jié)構(gòu)和編譯器設(shè)置上測試時(shí)爬早，你可能遇到很多不確定因素。因此强窖，你需要根據(jù)實(shí)際數(shù)據(jù)凸椿，自己做出衡量。
