3

std::vectorC ++入力イテレーターコンストラクターを使用して、次のような連続する整数の配列を作成したいと思います。

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

ただし、イテレータ間の距離に比例する時間計算量があるのか​​、それともベクトルを大きくするためにサイズ変更を繰り返すことで追加の対数成分を持つことができるのか、疑問に思っています。言い換えると、コンストラクターは2つのイテレーター間の距離を調べますか？コンストラクター引数はランダムアクセスイテレーターではないので、距離を計算できるかどうかわかりませんか？

サイズが繰り返し変更される場合、それを回避するためのより良い解決策はありますか？

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回の呼び出しのみを行い、イテレーターの最初と最後が順方向、双方向、またはランダムアクセスカテゴリの場合は再割り当てを行いません。Tのコピーコンストラクターに対してオーダーNの呼び出しを行い、入力イテレーターである場合はオーダーログ（N）の再割り当てを行います。

reserve()基本的に、順方向、双方向、またはランダムアクセスのイテレータの場合、2番目の例のように使用することでパフォーマンスが向上することを期待するべきではありません。コンストラクターが自動的にこれを行います。

プレーンな入力イテレータの場合、reserve()処理速度は向上しますが、一定の係数を超えることはありません。log(n)再割り当ては引き続きO(n)合計時間で行われるため、ベクトルを構築する合計時間もになりますO(n)。

于 2013-03-20T17:26:51.943 に答える