vector插入n个相同元素性能对比

写了一段测试程序对比插入n个相同元素到一个vector中消耗的时间,顺便总结一些相关概念。

插入相同元素测试代码

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
std::vector<int32> vec1,vec2,vec3,vec4,vec5;
int32 count = 5;

uint64 startTick = 0;
uint64 endTick = 0;

std::cout << "push back:" << std::endl;
startTick = CTS::getMsTimeStamp();
for(int32 i = 0; i < count; ++i){
vec1.push_back(1);
}
endTick = CTS::getMsTimeStamp();
std::cout << "cost time: " << endTick - startTick << std::endl;
std::cout << "----------------------------" << std::endl;

std::cout << "emplace back:" << std::endl;
startTick = CTS::getMsTimeStamp();
for(int32 i = 0; i < count; ++i){
vec2.emplace_back(1);
}
endTick = CTS::getMsTimeStamp();
std::cout << "cost time: " << endTick - startTick << std::endl;
std::cout << "----------------------------" << std::endl;

std::cout << "resize:" << std::endl;
startTick = CTS::getMsTimeStamp();
vec3.resize(count);
for(int32 i = 0; i < count; ++i){
vec3[i] = 1;
}
endTick = CTS::getMsTimeStamp();
std::cout << "cost time: " << endTick - startTick << std::endl;
std::cout << "----------------------------" << std::endl;

std::cout << "reserve:" << std::endl;
startTick = CTS::getMsTimeStamp();
vec4.reserve(count);
for(int32 i = 0; i < count; ++i){
vec4[i] = 1;
}
endTick = CTS::getMsTimeStamp();
std::cout << "cost time: " << endTick - startTick << std::endl;
std::cout << "----------------------------" << std::endl;

std::cout << "resize with value:" << std::endl;
startTick = CTS::getMsTimeStamp();
vec5.resize(count, 1);
endTick = CTS::getMsTimeStamp();
std::cout << "cost time: " << endTick - startTick << std::endl;
std::cout << "----------------------------" << std::endl;

CTS::printfVec(vec1);
CTS::printfVec(vec2);
CTS::printfVec(vec3);
CTS::printfVec(vec4);
std::cout << "vec4 size = " << vec4.size() << " cap = " << vec4.capacity() << std::endl;
CTS::printfVec(vec5);

以上5个vector分别用五种不同的方式插入count个相同元素,要注意的vec是已初始化过的。如果是未初始化的容器本身vector就有初始n个相同元素的构造函数,如下:

1
vector<int> vec(n, m);

意为,初始化包含n个值为m的vec。

回到上面代码,5个vector插入元素的方法分别为:

  1. 调用count次push_back函数
  2. 调用count次emplace_back函数
  3. 使用resize函数申请count个元素大小内存,在通过下标赋值
  4. 使用reserve函数申请count个元素大小内存,在通过下标赋值
  5. 使用resize函数申请count个元素大小内存同时使用其第二个参数赋上初始值

在count较小的情况下,五种方法基本上没有区别,当count值很大时,时间上就会有着较大的差别,如下:

以上结果为count为一千万时的结果,时间单位为秒。

可以看出,时间效率从上到下是越来越高的。

所以,首先得到结果,这个问题本身的答案是使用第五种方法,即使用带初始化值的resize函数

しかし(但是,发音西噶西,哈哈哈哈)!其实上面的五种方法中,第四种方法其实是不能完成我们的需求的,如果代码count为5,打印结果是:

vec4是没有元素被打印出来的,并且下方我打印出了它的size()capacity(),那么这两者包括这两个函数有什么区别呢?下面来简单对比一下。

vector的resize(),reserve(),size()和capacity()

基本概念

  1. capacity

    指容器在分配新的存储空间之前能存储的元素总数。

  2. size

    指当前容器所存储的元素个数

即capacity是容器可存储的最大总数,size是当前容器存储的个数。这样就比较明白了,至于两者之间差值的那些元素是什么情况,后续来说。可以先认为是未被初始化。

  1. resize
    既分配了空间,也创建了对象。

    这里空间就是capacity,对象就是容器中的元素。

  2. reserve
    reserve()表示容器预留空间,但不是真正的创建对象,需要通过insert()或push_back()等操作创建对象。

其实size()和capacity()没有更多需要介绍的地方,大家平时coding时直接调用即可。当然size()的使用频率相当高,通常进行遍历操作时,最外层的for循环的次数即为size()。

resize和reverse区别

  1. reserve()只修改capacity大小,不修改size大小;
  2. resize()既修改capacity大小,也修改size大小。

有如下示例代码:

1
2
3
4
5
6
7
8
9
10
11
vector<int> a;

a.reserve(100);
a.resize(50);
cout<<a.size()<<" "<<a.capacity()<<endl;
a.resize(150);
cout<<a.size()<<" "<<a.capacity()<<endl;
a.reserve(50);
cout<<a.size()<<" "<<a.capacity()<<endl;
a.resize(50);
cout<<a.size()<<" "<<a.capacity()<<endl;

结果如下:

可以看出,和如上所说的一样。且最后一个操作表明,resize一个原来capacity更大的vector时,capacity不会被缩小,只有size会被resize所修改。

还有一种实验,我们一直push_backcount个元素一直打印这两个值,会发现,部分情况下size等于capacity,但大部分情况下capacity会大于size。这也是因为vector动态分配空间所导致的。那么这样刚好说下为什么,最上面代码使用push_backemplace_back效率远低于resize的原因。

push_back过程

push_back是向容器vec尾部插入一个元素,如果此时size小于cap,则直接插入即可。如果此时size已经等于cap,那么STL会重新申请一块两倍于此时cap容量的连续内存,先将之前的内存拷贝到此处,再在其尾部插入这个新元素。所以,从零开始一个一个插入元素势必会进行巨量的这个过程,也就带来了大量的时间花销。

此外,对于vector每次扩容是否是两倍的这个说法,网上也有些不同的说法,在此不细究,我自己试验下来,小数目情况下确实是两倍。非两倍情况可能是STL版本或者数量大的情况不一样。附测试代码和结果,环境为linux+gcc9.2

1
2
3
4
5
vector<int> vec6;
for(int i = 0; i < 20; ++i){
vec6.push_back(i);
cout<< "size: " <<vec6.size()<<" cap: "<<vec6.capacity()<<endl;
}

emplace_back()和push_back()的区别

上面代码第一第二种方法虽然差距很小,但仍然还是有一点细微的时间差距。在此也记录一下这两者之间的区别。

对于最终结果来说,这两个函数是一样的,都是将一个元素插入到容器最后。

其中emplace_back()函数是C++11新增加的,那么既然功能完全一样,C++11引入它的原因是什么呢。

emplace_back()push_back() 的区别,就在于底层实现的机制不同。push_back() 向容器尾部添加元素时,首先会创建这个元素,然后再将这个元素拷贝或者移动到容器中(如果是拷贝的话,事后会自行销毁先前创建的这个元素);而 emplace_back() 在实现时,则是直接在容器尾部创建这个元素,省去了拷贝或移动元素的过程。有如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <vector> 
#include <iostream>
using namespace std;
class testDemo
{
public:
testDemo(int num):num(num){
std::cout << "调用构造函数" << endl;
}
testDemo(const testDemo& other) :num(other.num) {
std::cout << "调用拷贝构造函数" << endl;
}
testDemo(testDemo&& other) :num(other.num) {
std::cout << "调用移动构造函数" << endl;
}
private:
int num;
};

int main()
{
cout << "emplace_back:" << endl;
std::vector<testDemo> demo1;
demo1.emplace_back(2);

cout << "push_back:" << endl;
std::vector<testDemo> demo2;
demo2.push_back(2);
}

运行结果为:

1
2
3
4
5
emplace_back:
调用构造函数
push_back:
调用构造函数
调用移动构造函数

在此基础上,尝试将 testDemo 类中的移动构造函数注释掉,再运行程序会发现,运行结果变为:

1
2
3
4
5
emplace_back:
调用构造函数
push_back:
调用构造函数
调用拷贝构造函数

由此可以看出,push_back() 在底层实现时,会优先选择调用移动构造函数,如果没有才会调用拷贝构造函数。

显然完成同样的操作,push_back() 的底层实现过程比 emplace_back() 更繁琐,换句话说,emplace_back() 的执行效率比 push_back() 高。因此,在实际使用时,建议优先选用emplace_back()。

但是,由于 emplace_back() 是 C++ 11 标准新增加的,如果程序要兼顾之前的版本,还是应该使用 push_back()。且对于基础类型或者内容很小的类来说,这两者也不会带来太大的性能差异。

参考文章

C++ STL vector添加元素(push_back()和emplace_back())详解