【1】提前分配足够空间以免不必要的重新分配和复制代价
关于vector容器重新分配和复制及析构释放的代价，请参见随笔《STL容器之vector》。
应用示例对比代码如下：
#include <vector>
#include <ctime>
#include <iostream>
using namespace std; // 计时器
// 调用clock()函数实现，返回毫秒(ms)数
class TestProgramRunTimer
{
enum { kClockPerSecond = CLOCKS_PER_SEC }; // 每秒时钟的跳数 public:
TestProgramRunTimer()
: cost_time()
, start_time()
, end_time()
{
start();
} ~TestProgramRunTimer()
{} void reset()
{
cost_time = ;
start_time = ;
end_time = ;
} void start()
{
start_time = clock();
} void stop()
{
end_time = clock();
cost_time = (end_time - start_time) / (kClockPerSecond / 1000.0);
return;
} double cost()
{
return cost_time;
} protected:
double cost_time;
clock_t start_time;
clock_t end_time;
}; TestProgramRunTimer tt; struct BigTestStruct
{
int iValue;
float fValue;
long lValue;
double dValue;
char cNameArr[];
int iValArr[];
}; void FillVector(vector<BigTestStruct>& testVector)
{
for (int i = ; i < ; ++i)
{
BigTestStruct bt;
testVector.push_back(bt);
}
} void main()
{
cout << sizeof(BigTestStruct) << endl; vector<BigTestStruct> myVec1, myVec2, myVec3;
tt.start();
FillVector(myVec1);
tt.stop();
cout << "cost time to Fill vector without reservation: " << tt.cost() << endl; myVec2.reserve();
tt.reset();
tt.start();
FillVector(myVec2);
tt.stop();
cout << "cost time to Fill vector with reservation(100): " << tt.cost() << endl; myVec3.reserve();
tt.reset();
tt.start();
FillVector(myVec3);
tt.stop();
cout << "cost time to Fill vector with reservation(10000): " << tt.cost() << endl; system("pause");
} // run out:
/*
440
cost time to Fill vector without reservation: 31
cost time to Fill vector with reservation(100): 16
cost time to Fill vector with reservation(10000): 0
请按任意键继续. . .
*/
同样是push_back操作，预分配足够空间和不分配空间的时间代价显而易见。
【2】使用shrink_to_fit（）释放vector占用的内存。（备注：clear（） 和 erase（）不会释放内存）
shrink to fit 压缩到合适的大小空间，即把多余的内存空间释放掉。
示例代码如下：
#include <vector>
#include <iostream>
using namespace std; struct BigTestStruct
{
int iValue;
float fValue;
long lValue;
double dValue;
char cNameArr[];
int iValArr[];
}; void FillVector(vector<BigTestStruct>& testVector, int nNum = )
{
nNum = ( == nNum) ? : nNum;
for (int i = ; i < nNum; ++i)
{
BigTestStruct bt;
testVector.push_back(bt);
}
} // shrink_to_fit函数原形
/*
void shrink_to_fit()
{ // reduce capacity
if (size() < capacity())
{ // worth shrinking, do it
_Myt _Tmp(*this);
swap(_Tmp);
}
}
*/ void main()
{
vector<BigTestStruct> myVec1, myVec2, myVec3;
FillVector(myVec1, );
size_t capacity = myVec1.capacity();
cout << "删除元素前，容器可容纳元素数量：" << capacity << endl;
myVec1.erase(myVec1.begin(), myVec1.begin() + );
capacity = myVec1.capacity();
cout << "删除元素后，容器可容纳元素数量：" << capacity << endl; myVec1.clear();
capacity = myVec1.capacity();
cout << "清空元素后，容器可容纳元素数量：" << capacity << endl; FillVector(myVec1, );
cout << "重新添加100个元素后，容器可容纳元素数量：" << capacity << endl;
vector<BigTestStruct> tempVec1(myVec1);
tempVec1.swap(myVec1); // 压缩到合适大小（因为myVec1只填充了100个元素,所以相当于释放多余内存空间）
capacity = myVec1.capacity();
cout << "利用拷贝构造新容器，与之交换后容器可容纳元素数量：" << capacity << endl; FillVector(myVec2, );
cout << endl << "添加200个元素后，容器可容纳元素数量：" << capacity << endl;
capacity = myVec2.capacity();
vector<BigTestStruct> tempVec2;
tempVec2.swap(myVec2); // 清空容器（因为tempVec2是空容器,所以相当于释放内存空间）
capacity = myVec2.capacity();
cout << "利用空容器，与之交换后容器可容纳元素数量：" << capacity << endl; FillVector(myVec3, );
capacity = myVec3.capacity();
cout << endl << "压缩前，容器可容纳元素数量：" << capacity << endl;
// 压缩到合适大小（因为myVec3只填充了300个值,所以相当于释放多余内存空间）
myVec3.shrink_to_fit();
capacity = myVec3.capacity();
cout << "压缩后，容器可容纳元素数量：" << capacity << endl; system("pause");
} // run out:
/*
删除元素前，容器可容纳元素数量：141
删除元素后，容器可容纳元素数量：141
清空元素后，容器可容纳元素数量：141
重新添加100个元素后，容器可容纳元素数量：141
利用拷贝构造新容器，与之交换后容器可容纳元素数量：100 添加200个元素后，容器可容纳元素数量：100
利用空容器，与之交换后容器可容纳元素数量：0 压缩前，容器可容纳元素数量：316
压缩后，容器可容纳元素数量：300
请按任意键继续. . .
*/
通过上面的示例代码及运行输出结果分析可知：
1、erase和clear函数并不释放内存空间。执行两者后，容器的容量输出结果不变，说明并不会减少vector占用的内存空间。
2、shrink_to_fit压缩容器内存空间到合适大小（即capacity()容量等于元素个数size() ）。
2.1 由于vector容器是动态自动扩容的，但自动扩容的规则不保证每次增加空间后刚好能容纳所有元素而没有一点浪费。
所以，当元素填充完全后，为了释放多余的内存空间，可以调用shrink_to_fit函数达到目的。
2.2 释放容器内存空间。一般人们总以为调用erase或clear后，容器内存空间也释放掉了，如上示例证明根本不是那么回事。
清理掉（erase或clear）容器所有元素之后，相当于容器元素个数为0，但容器容量仍不变（即内存空间仍存在）。
如果想释放掉容器内存空间，可以调用shrink_to_fit函数，使容器的容量值等于元素个数0。
注意：容器的容量值为0，意味着容器没有任何内存空间再可以填充元素，即释放了内存空间。
3、shrink_to_fit函数其本质同swap函数。
从示例代码中注释部分的shrink_to_fit函数原形可以看到，真正实现过程调用swap函数。
【3】填充或拷贝vector时，应该使用赋值而不是拷贝构造函数 或 insert（）及 push_back（）
从一个旧的vector取出元素填充另一个vector时，常有四种方式：
1、赋值构造函数。
2、拷贝构造函数。
3、基于迭代器的insert函数。
4、基于循环的push_back函数。
示例代码如下：
#include <vector>
#include <ctime>
#include <iostream>
using namespace std; // 计时器
// 调用clock()函数实现，返回毫秒(ms)数
class TestProgramRunTimer
{
enum { kClockPerSecond = CLOCKS_PER_SEC }; // 每秒时钟的跳数 public:
TestProgramRunTimer()
: cost_time()
, start_time()
, end_time()
{
start();
} ~TestProgramRunTimer()
{} void reset()
{
cost_time = ;
start_time = ;
end_time = ;
} void start()
{
start_time = clock();
} void stop()
{
end_time = clock();
cost_time = (end_time - start_time) / (kClockPerSecond / 1000.0);
return;
} double cost()
{
return cost_time;
} protected:
double cost_time;
clock_t start_time;
clock_t end_time;
}; TestProgramRunTimer tt; struct BigTestStruct
{
int iValue;
float fValue;
long lValue;
double dValue;
char cNameArr[];
int iValArr[];
}; void FillVector(vector<BigTestStruct>& testVector)
{
for (int i = ; i < ; ++i)
{
BigTestStruct bt;
testVector.push_back(bt);
}
} void main()
{
// assign
vector<BigTestStruct> sourceVec0, destVec0;
FillVector(sourceVec0);
tt.start();
destVec0 = sourceVec0;
tt.stop();
cout << "assign :: " << tt.cost() << endl; // copy
vector<BigTestStruct> sourceVec1;
FillVector(sourceVec1);
tt.reset();
tt.start();
vector<BigTestStruct> destVec1(sourceVec1);
tt.stop();
cout << "copy :: " << tt.cost() << endl; // insert
vector<BigTestStruct> sourceVec2, destVec2;
FillVector(sourceVec2);
tt.reset();
tt.start();
destVec2.insert(destVec2.begin(), sourceVec2.begin(), sourceVec2.end());
tt.stop();
cout << "insert :: " << tt.cost() << endl; // push_back
vector<BigTestStruct> sourceVec3, destVec3;
FillVector(sourceVec3);
tt.reset();
tt.start();
vector<BigTestStruct>::iterator iter = sourceVec3.begin();
for (; iter != sourceVec3.end(); ++iter)
{
destVec3.push_back(*iter);
}
tt.stop();
cout << "push_back :: " << tt.cost() << endl; system("pause");
} // run out:
/*
assign :: 31
copy :: 78
insert :: 78
push_back :: 281
请按任意键继续. . .
*/
通过输出结果，可以看到vector赋值比insert和copy构造函数快，比push_back()更快。
为什么会这样？
赋值非常有效率，因为它知道要拷贝的vector有多大，然后只需要通过内存管理一次性拷贝vector内部的缓存。
所以，想高效填充vector：
首先应尝试使用assignment，然后再考虑基于迭代器的insert()或拷贝构造，最后考虑push_back。
【4】遍历vector元素时，避免使用迭代器。建议使用下标方式。
下面比较三种遍历方式，示例代码如下：
#include <vector>
#include <ctime>
#include <iostream>
using namespace std; #define MAXSIZE 100000 // 计时器
// 调用clock()函数实现，返回毫秒(ms)数
class TestProgramRunTimer
{
enum { kClockPerSecond = CLOCKS_PER_SEC }; // 每秒时钟的跳数 public:
TestProgramRunTimer()
: cost_time()
, start_time()
, end_time()
{
start();
} ~TestProgramRunTimer()
{} void reset()
{
cost_time = ;
start_time = ;
end_time = ;
} void start()
{
start_time = clock();
} void stop()
{
end_time = clock();
cost_time = (end_time - start_time) / (kClockPerSecond / 1000.0);
return;
} double cost()
{
return cost_time;
} protected:
double cost_time;
clock_t start_time;
clock_t end_time;
}; TestProgramRunTimer tt; struct BigTestStruct
{
int iValue;
float fValue;
long lValue;
double dValue;
char cNameArr[];
int iValArr[];
}; void FillVector(vector<BigTestStruct>& testVector)
{
for (int i = ; i < MAXSIZE; ++i)
{
BigTestStruct bt;
testVector.push_back(bt);
}
} // 使用下标[]运算符
void funSubscript()
{
vector<BigTestStruct> myVec;
FillVector(myVec);
tt.reset();
tt.start();
int sum = ;
for (unsigned i = ; i < MAXSIZE; ++i)
{
sum += myVec[i].iValue;
}
tt.stop();
cout << "funSubscript :: " << tt.cost() << endl;
} // 使用vector::at()成员函数
void funAt()
{
vector<BigTestStruct> myVec;
FillVector(myVec);
tt.reset();
tt.start();
int sum = ;
for (unsigned i = ; i < MAXSIZE; ++i)
{
sum += myVec.at(i).iValue;
}
tt.stop();
cout << "funAt :: " << tt.cost() << endl;
} // 使用迭代器
void funIter()
{
vector<BigTestStruct> myVec;
FillVector(myVec);
tt.reset();
tt.start();
int sum = ;
for (auto iter = myVec.begin(); iter != myVec.end(); ++iter)
{
sum += iter->iValue;
}
tt.stop();
cout << "funIter :: " << tt.cost() << endl;
} void main()
{
funAt();
funSubscript();
funIter(); system("pause");
} // run out:
/*
funAt :: 16
funSubscript :: 3
funIter :: 78
请按任意键继续. . .
*/
相比较后，强烈建议使用下标或者at()成员函数，可见迭代器（迭代器的设计主要为了算法通用）的效率最低。
【5】尽量避免在vector前部插入元素。
下面对比一下向list和vector两种容器前插入数据的效率，示例代码如下：
#include <list>
#include <vector>
#include <ctime>
#include <iostream>
using namespace std; #define MAXSIZE 10000 // 计时器
// 调用clock()函数实现，返回毫秒(ms)数
class TestProgramRunTimer
{
enum { kClockPerSecond = CLOCKS_PER_SEC }; // 每秒时钟的跳数 public:
TestProgramRunTimer()
: cost_time()
, start_time()
, end_time()
{
start();
} ~TestProgramRunTimer()
{} void reset()
{
cost_time = ;
start_time = ;
end_time = ;
} void start()
{
start_time = clock();
} void stop()
{
end_time = clock();
cost_time = (end_time - start_time) / (kClockPerSecond / 1000.0);
return;
} double cost()
{
return cost_time;
} protected:
double cost_time;
clock_t start_time;
clock_t end_time;
}; TestProgramRunTimer tt; struct BigTestStruct
{
int iValue;
float fValue;
long lValue;
double dValue;
char cNameArr[];
int iValArr[];
}; void FillVector(vector<BigTestStruct>& testVector)
{
for (int i = ; i < MAXSIZE; ++i)
{
BigTestStruct bt;
testVector.insert(testVector.begin(), bt);
}
} void FillList(list<BigTestStruct>& testList)
{
for (int i = ; i < MAXSIZE; ++i)
{
BigTestStruct bt;
testList.insert(testList.begin(), bt);
}
} void main()
{
list<BigTestStruct> myList;
vector<BigTestStruct> myVec;
tt.reset();
tt.start();
FillList(myList);
tt.stop();
cout << "FillList :: " << tt.cost() << endl; tt.reset();
tt.start();
FillVector(myVec);
tt.stop();
cout << "FillVector :: " << tt.cost() << endl; system("pause");
} // run out:
/*
FillList :: 47
FillVector :: 12658
请按任意键继续. . .
*/
任何在 vetor 前部部做的插入操作其复杂度都是 O(n) 的。
在前部插入数据十分低效，因为 vector 容器中的每个元素项都必须为新插入的元素项腾出空间而被复制移动。
如果在应用 vector 时需要从前部连续插入很多元素，那可能需要重新评估你的总体架构。
【6】向vector容器插入元素时使用emplace_back而不是push_back。
对比示例代码如下：
#include <vector>
#include <ctime>
#include <iostream>
using namespace std; #define MAXSIZE 10000 // 计时器
// 调用clock()函数实现，返回毫秒(ms)数
class TestProgramRunTimer
{
enum { kClockPerSecond = CLOCKS_PER_SEC }; // 每秒时钟的跳数 public:
TestProgramRunTimer()
: cost_time()
, start_time()
, end_time()
{
start();
} ~TestProgramRunTimer()
{} void reset()
{
cost_time = ;
start_time = ;
end_time = ;
} void start()
{
start_time = clock();
} void stop()
{
end_time = clock();
cost_time = (end_time - start_time) / (kClockPerSecond / 1000.0);
return;
} double cost()
{
return cost_time;
} protected:
double cost_time;
clock_t start_time;
clock_t end_time;
}; TestProgramRunTimer tt; struct BigTestStruct
{
int iValue;
float fValue;
long lValue;
double dValue;
char cNameArr[];
int iValArr[];
}; void FV_ByPushBack(vector<BigTestStruct>& testVector)
{
tt.reset();
tt.start();
for (int i = ; i < MAXSIZE; ++i)
{
BigTestStruct bt;
testVector.push_back(bt);
}
tt.stop();
cout << "FV_ByPushBack :: " << tt.cost() << endl;
} void FV_ByEmplaceBack(vector<BigTestStruct>& testVector)
{
tt.reset();
tt.start();
for (int i = ; i < MAXSIZE; ++i)
{
BigTestStruct bt;
testVector.emplace_back(bt);
}
tt.stop();
cout << "FV_ByEmplaceBack :: " << tt.cost() << endl;
} void main()
{
vector<BigTestStruct> myVec1, myVec2;
FV_ByPushBack(myVec1);
FV_ByEmplaceBack(myVec2); system("pause");
} // run out:
/*
FV_ByPushBack :: 31
FV_ByEmplaceBack :: 16
请按任意键继续. . .
*/
通过结果分析，“安置”函数比插入函数性能更好。
关于emplace_back与push_back两者的区别，请参见随笔《emplace_back与push_back的区别》
Good Good Study, Day Day Up.
顺序 选择 循环 总结