3

我想使用 C++std::vector输入迭代器构造函数来构建一个连续整数数组，如下所示：

std::vector<unsigned> indexes(boost::counting_iterator<unsigned>(0U),
                              boost::counting_iterator<unsigned>(10000U));

但是，我想知道它的时间复杂度是否与迭代器之间的距离成正比，或者由于重复调整大小以增加向量，它是否可能具有额外的对数分量？换句话说，构造函数是否查看两个迭代器之间的距离？由于构造函数参数不是随机访问迭代器，我不确定距离可以计算吗？

如果它会反复调整大小，是否有比这更好的解决方案来避免这种情况：

std::vector<unsigned> indexes;

indexes.reserve(10000U);

for (unsigned idx = 0; idx < 10000U; ++idx) {
  indexes.push_back(idx);
}
4

1 回答 1

4

时间复杂度是std::vector(InputIterator first, InputIterator last)线性的吗？

简而言之，是的。

该标准vector(InputIterator, InputIterator)在 §23.3.6.2 中保证以下内容：

复杂性：仅对 T 的复制构造函数进行 N 次调用（其中 N 是 first 和 last 之间的距离），如果迭代器 first 和 last 是前向、双向或随机访问类别，则不进行重新分配。如果它们只是输入迭代器，它会对 T 的复制构造函数和 order log(N) 重新分配进行 order N 调用。

基本上，对于前向、双向或随机访问迭代器，您不应该期望从使用reserve()第二个示例中看到任何性能提升；构造函数会自动为您执行此操作。

对于普通的输入迭代器，reserve()会加快速度，但不会超过一个常数因子。log(n)重新分配仍将在总O(n)时间内完成，因此构造向量的总时间也将是O(n).

于 2013-03-20T17:26:51.943 回答