c++之vector

c++的STL中vector相关的操作和问题

实验平台Visual Studio 2013

1 size与capacity

size就是容器中元素的个数，而capacity指与分配给容器的内存容量，capacity>=size
size的增长是根据容器中插入的元素个数来来每次增长，而capacity则不同，当容器已预分配了一定内存后，若再添加元素超过了capacity，则capacity会增加原来的一半也就预分配原来一半的内存来增长
example：

vector<double> v1(1000,11);
cout << "Original" << endl;
cout << "size: " << v1.size() << " capacity" << v1.capacity() << endl;
v1.push_back(11);
cout << endl << "push_back(11)" << endl;
cout << "size: " << v1.size() << " capacity" << v1.capacity() << endl;

1.1 resize

改变size会改变原来vector的size，若resize比原来的小则容器保留size大小的元素多余的被删去，若resize比原来的大则容器多余size大小的元素默认初始化为0，若resize比原来capacity的小则容器capacity不变，
若resize比原来capacity的大则容器capacity每次增加为原来的一半直到不小于resize的大小
example：

vector<double> v1(1000,11);
cout << "Original" << endl;
cout << "size: " << v1.size() << " capacity: " << v1.capacity() << endl;
v1.push_back(11);
cout << endl << "push_back(11)" << endl;
cout << "size: " << v1.size() << " capacity" << v1.capacity() << endl;

v1.resize(800);
cout << endl << "resize(800)" << endl;
cout << "size: " << v1.size() << " capacity: " << v1.capacity() << endl;
cout << "v1[1000]=" << v1[1000] << endl;

v1.resize(1200);
cout << endl << "resize(1200)" << endl;
cout << "size: " << v1.size() << " capacity: " << v1.capacity() << endl;
cout << "v1[1000]=" << v1[1000] << endl;

v1.resize(2000);
cout << endl << "resize(2000)" << endl;
cout << "size: " << v1.size() << " capacity: " << v1.capacity() << endl;
cout << "v1[1000]=" << v1[1000] << endl;

这里面resize(800)后vector[1000]=11，这是因为这个地址保留了原来的值，这样月结访问是不安全的，后面resize(1200)后，默认初始化为了0。

1.2 reserve

reserve不会改变容器的size大小，若reserve大于原来的capacity则capacity变为增加的大小，反之则capacity不变
example：

vector<double> v1(1000,11);
cout << "Original" << endl;
cout << "size: " << v1.size() << " capacity: " << v1.capacity() << endl;
v1.push_back(11);
cout << endl << "push_back(11)" << endl;
cout << "size: " << v1.size() << " capacity" << v1.capacity() << endl;

v1.reserve(800);
cout << endl << "reserve(800)" << endl;
cout << "size: " << v1.size() << " capacity: " << v1.capacity() << endl;

v1.reserve(2000);
cout << endl << "reserve(2000)" << endl;
cout << "size: " << v1.size() << " capacity: " << v1.capacity() << endl;

说明：
由于capacity是逐渐增长的，为了减少多次预分配内存的开销，在使用容器时尽量使用resize来分配元素个数（预分配内存）

2 使用效率

2.2 vector赋值的效率

以下比较vector三种赋值方法的效率

DWORD start,end;
int i;

start= GetTickCount();
vector<double> v1;
for (i = 0; i < 10000000; ++i) 
       v1.push_back(i);
end = GetTickCount();
   cout << "使用push_back耗时：" << end - start << "ms" << endl;

start= GetTickCount(10000000);
vector<double> v2;
v2.resize(10000000);
for (i = 0; i < 10000000; ++i) 
       v2[i] = i;
end = GetTickCount();
   cout << "使用下标赋值耗时：" << end - start << "ms" << endl;

start= GetTickCount();
vector<double> v3;
i=0;
v3.resize(10000000);
for (auto k = v3.begin(); k < v3.end(); ++k)
{
       *k = i;
    ++i;
}
end = GetTickCount();
   cout << "使用迭代器赋值耗时：" << end - start << "ms" << endl;

可以看到
(a) 使用下标运算符的效率会比使用迭代器高一些。主要是在访问迭代器是要进行迭代器越位、有效性、是否指向同一容器等方面的判断，比较耗时。我们会发现使用push_back插入数据较慢，因为他会动态的分配内存（即动态增长capacity）

2.2 vector访问的效率

以下比较vector五种访问方法的效率

DWORD start,end;
vector<double> v1;
int temp; int i;
for (i = 0; i < 10000000; ++i) 
      v1.push_back(i);
cout << "vector size: " << v1.size() << endl;

//test 1
start= GetTickCount();
for (i = 0; i < v1.size(); ++i) 
{
    temp=v1[i];
}
end = GetTickCount();
cout << "使用[]运算符耗时：" << end - start << "ms" << endl;
//test 2
start= GetTickCount();
for (i = 0; i < v1.size(); ++i) 
{
    temp=v1.at(i);
}
end = GetTickCount();
cout << "使用at运算符耗时：" << end - start << "ms" << endl;
//test 3
start = GetTickCount();
for (auto k = v1.begin(); k < v1.end(); ++k)
{
    temp = *k;
}
end = GetTickCount();
cout << "使用迭代器（++k）耗时：" << end - start << "ms" << endl;
//test 4
start = GetTickCount();
for (auto k = v1.begin(); k < v1.end(); k++)
{
    temp = *k;
}
end = GetTickCount();
cout << "使用迭代器,使用k++，而不是++k：" << end - start << "ms" << endl;
//test 5
start = GetTickCount();
i = 0;
for (auto k = v1.begin(); i<v1.size(); ++i,++k)
{
    temp = *k;
}
end = GetTickCount();
cout << "使用迭代器,不使用end（）方法：" << end - start << "ms" << endl;

可以看到
(a) 使用下标运算符的效率会比使用迭代器高一些。主要是在访问迭代器是要进行迭代器越位、有效性、是否指向同一容器等方面的判断，比较耗时。我们会发现测试4就是验证我我们的假设，因为执行end（）函数是比较耗时的，所以我就不用它，发现迭代器访问会比下标还快。
(b)其中使用at运算符比迭代器快很多但还是没使用下标访问快，我们比较测试3和4的结果，会发现测试3比测试2慢了两倍，其实这个也就是为啥我们推荐在写：++k和k++的时候，能用++k，就用++k的原因。