C++中向量初始化的性能

Question

假设您从另一个容器初始化一个向量:

main()
{
    list<int> L { 0, 1, 2 };
    vector<int> V ( L.begin(), L.end() );
    copy ( V.begin(), V.end(), ostream_iterator<int> ( cout, " " ) );
    cout << endl;
}

矢量大小是设置一次,还是在初始化期间动态调整大小？(在此示例中不是问题,因为源代码很少,但如果源包含很多元素,则可能会出现问题.)

Answer 1

您正在std::vector使用两个迭代器(以及一个隐藏的allocator参数)调用模板化构造函数.这就是相关标准引用的内容:

23.3.6.2向量构造函数,复制和赋值[vector.cons]

template <class InputIterator> 
vector(InputIterator first, InputIterator last, const Allocator& = Allocator());

9效果:使用指定的分配器构造一个等于[first,last]范围的向量.

10复杂性:仅对N的复制构造函数进行N次调用(其中N是第一个和最后一个之间的距离),如果迭代器的第一个和最后一个是正向,双向或随机访问类别,则不进行重新分配.它使命令N调用T的复制构造函数和命令log(N)重新分配,如果它们只是输入迭代器.

因为您从std::list(双向迭代器)初始化,所以只有一个分配.

从标准输入OTOH读取是使用输入迭代器完成的,然后可能有多个重新分配.请注意,元素在内存中移动的平均次数仍然是O(1)(由于指数内存分配策略).