9

不必要な再割り当てを避けるために「予約」を使用することをお勧めします (Effective STL の項目 14)。

std::vector<int> v1;
v1.reserve(1000);

for (int i = 0; i < 1000; i++)
    v1.push_back(i);

assignを呼び出すときに同じルールが適用されますか?

std::vector<int> v2;
//v2.reserve(v1.size()); // Better to do this?
v2.assign(v1.begin(), v1.end());
4

2 に答える 2

7

電話をかけるかどうかは、reserve以下によって異なります。

  • イテレータタイプ：入力イテレータの場合、実装はサイズを推測できません
  • ライブラリの品質：「より良い」イテレータに特化していない可能性があります
  • パフォーマンスが保守性を低下させる価値があるかどうか

3つのポイントを順番に見ていきましょう。

1）イテレータタイプ

このassignメソッドは、少なくともInputIteratorモデルに準拠する必要がある2つのイテレーターを使用します。問題は、このモデルが純粋なソース（ネットワークからのバイトなど）を表すことです。モデルから何かを2回消費する可能性があります。その結果、2つInputIteratorの場合、データを抽出せずにそれらの間の距離を計算することはできません（データがまったく必要ない場合を除きますが、それが割り当ての目的ではありません）。したがって、最初に「予約」することはできません。

std::distanceこれは、少なくともを必要とするという事実によって示されていFowardIteratorます。

2）実装の品質

私は、標準が実際に「より良い」イテレータ（少なくともモデル化ForwardIterator）に対して、実装がassign範囲を2回歩くことを義務付けているとは思いません。メモリ帯域幅によって制限される計算（巻き戻し時間が非常に遅いテープでその情報を読み取ることを想像してください）では、これは実際にはよりコストがかかります。

ただし、多くの実装（libc ++など、以下を参照）は、必要に応じて適切な量のメモリを予約するために最初に呼び出すassignように特殊化されます。ForwardIteratorstd::distance

注：ちなみに、同じことが大量挿入にも当てはまります。

3）メンテナンス負担

利益が得られる可能性があるにもかかわらず、あなたは（おそらく無意識のうちに）ここで情報を複製していることに注意してください。

size_t size = std::distance(begin, end);

if (begin != end) ++begin; // new line

v.reserve(size);
v.assign(begin, end);

新しい行の出現により、コードが突然わずかに不正確になる様子をご覧ください。それが機能しないというわけではありませんが、意図された最適化はもはやそれほど正しくありません：あなたは今予約しすぎています！

個人的には、標準ライブラリの実装が正しいことをすることを信頼します。それらを書いている人は私よりもはるかに多くの経験を持っています。

そして、それが実際にアプリケーションで特定されたボトルネックである場合は、いつでも自分のやり方を試すことができます。メソッドを作成reserve_and_assignして、それが何をするのかを明確にし、それが優れているかどうかを測定するだけです。

参考までに、ここにlibc++の実装があります。

template <class _Tp, class _Allocator>
template <class _InputIterator>
typename enable_if
<
     __is_input_iterator  <_InputIterator>::value &&
    !__is_forward_iterator<_InputIterator>::value,
    void
>::type
vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
{
    clear();
    for (; __first != __last; ++__first)
        push_back(*__first);
}

template <class _Tp, class _Allocator>
template <class _ForwardIterator>
typename enable_if
<
    __is_forward_iterator<_ForwardIterator>::value,
    void
>::type
vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
{
    typename iterator_traits<_ForwardIterator>::difference_type __new_size = _VSTD::distance(__first, __last);
    if (static_cast<size_type>(__new_size) <= capacity())
    {
        _ForwardIterator __mid = __last;
        bool __growing = false;
        if (static_cast<size_type>(__new_size) > size())
        {
            __growing = true;
            __mid =  __first;
            _VSTD::advance(__mid, size());
        }
        pointer __m = _VSTD::copy(__first, __mid, this->__begin_);
        if (__growing)
            __construct_at_end(__mid, __last);
        else
            this->__destruct_at_end(__m);
    }
    else
    {
        deallocate();
        allocate(__recommend(static_cast<size_type>(__new_size)));
        __construct_at_end(__first, __last);
    }
}
于 2012-07-01T16:05:04.427 に答える
7

コンパイラ/stlはそこにいくつのアイテムが含まれるかを知っているので（実際のデータをコピーする前に必要な量自体が）、実際には必要ない場合がv1あります。std::vectorv2reserve

ただし、一般的なケースでは、入力コンテナ（ ）がアイテムの数を認識しておらず、手元に数があるreserve場合は、事前に必要な量を把握しておくと意味があります。v1

于 2012-07-01T14:53:20.207 に答える