c++ - std :: vectorは成長時にスワップ関数を呼び出しますか？常にまたは一部のタイプのみ？

Question

私の知る限り、ベクトルのベクトル（std::vector< std::vector<int> >）を使用できます。これは、内部的に要素がコピーされないため非常に効率的ですが、メモリバッファーのコピーが含まれていないため、はるかに高速です。私は正しいですか？

std::vectorスワップ機能を正確に利用するのはいつですか？C++標準ではそれについて何も見つかりません。バッファの再割り当て中に発生しますか？

私はそれを見つけるためにいくつかのテストをしましたが、失敗しました。カスタムデータ型のスワップ関数がまったく呼び出されません。

編集：これが私のテストプログラムです。

score 8 · Accepted Answer

この主張を裏付けるリンクはありませんが、私の知る限り、Microsoft C++ で配布されている STL 実装は、内部の非標準のマジックアノテーションを使用してvector(および他の STL コレクション) を有能なスワップとしてマークするため、そうしvector<vector<>>ません。内部ベクトルをコピーしますが、それらを交換します。VC9 まで、つまり VC10 では右辺値参照に切り替わります。クロスコンパイラの方法がなく、コードが特定のコンパイラバージョンでのみ機能するため、同じ方法で独自のクラスをマークすることはできないと思います。

編集：<vector>VC9のヘッダーをざっと見て、これを見つけました：

    // vector implements a performant swap
template <class _Ty, class _Ax>
    class _Move_operation_category<vector<_Ty, _Ax> >
    {
    public:
        typedef _Swap_move_tag _Move_cat;
    };

実験のために、このクラスを独自の型に特化することもできますが、前述したように、これは STL バージョン固有であり、VC10 では廃止されます。

score 3 · Accepted Answer

ベクターの使用は許可されていないと思いますswap（ADLで発見）。私が見つけることが明示的に禁止されているわけではありませんが、ベクトルの値の型に関する要件は CopyConstructible および Assignable です。どちらもswap有効な操作 (オプションの操作であっても) を持っていません。また、スワップがオーバーロードされているかどうかを判断する標準的な手段もありません。おそらくそれは使用できますstd::swap(または、存在する場合は特殊化) 必要に応じて、そのパラメーターに同じ要件があるため: CopyConstructible および Assignable (および名前空間 std 内の関数の UDT の特殊化は、ジェネリックテンプレートの定義された動作を実装する必要があります)。ただし、これは再割り当てには役立ちません。なぜなら、交換する「空の」オブジェクトを構築する必要があり、ベクトルは、その値の型がデフォルトで構築可能である必要があるという独自の権限を決定できないためです。それは必要ありません。

型 T に操作が必要ない場合、たとえコンパイラが何らかの方法でそれが存在すると精神的に判断したとしても、それは実行されないと仮定するのは合理的だと思います。C++ では、何かがインターフェイスを実装するために定義された適切な関数を持っているからといって、そのインターフェイスのセマンティクスを実装していると主張するわけではありません。関数の動作がインターフェイスにとって期待どおりであると主張しているのは、セマンティクスを要求するコンテキストでそれを渡すまではありません。標準ではswap、 vector の値の型に対して行儀の良いを要求していないため、 vector の実装では、swapが定義されているという理由だけでよりも優れているとは想定できませんoperator=。

それは仕様の意図についての私の解釈にすぎませんが、どちらにしても決定的なものは見つかりません。

23.2.4.3/4 は手がかりを与えます。について話すときerase、「 T の代入演算子は、消去された要素の後のベクトル内の要素の数に等しい回数呼び出されます」と書かれています。swapしたがって、 vector を使用して、消去後にベクトルの末尾を前方にシフトすることは明示的に禁止されています。使用する必要がありoperator=ます。これは、著者がすべてに使用することを期待しているという強いヒントだと思います。そうでなければ、デフォルトのコンストラクターを必要とせずに実際に使用できる 1 つのケースでoperator=禁止するほど不注意ではなかったでしょう。swap

また、あなたと jdv によって説明された、コンテナーのコンテナーの場合、スワッピングから得られる大きな利益があるという Microsoft のポイントもわかります。「テンプレートマジック」が整形式の C++ プログラムに干渉しない限り、型がvector にスワップを指示する手段を提供する実装に問題はありません。

たとえば、名前にアンダースコアが 2 つ付いた型特性テンプレートを持っている可能性があります。その名前を使用する効果は実装定義であるため、すべての賭けは無効です。C++ 標準は、そのテンプレートを特化したプログラムで std::vector がどのように動作するかについて何も述べていません。プログラムで予約名を使用すると、実装は vector を定義して、すべての標準的なケアにoperator=、swap、またはを使用できます。aubergine

score 3 · Accepted Answer

std::vector は伝統的に、成長するときに要素を新しいメモリにコピー構築し、その後古い値を破棄します。ただし、右辺値参照とムーブセマンティクスを備えた今後の C++0x では、std::vector は要素を新しいメモリにムーブコンストラクトできます。これははるかに効率的です。文字列またはその他のコピーにコストのかかるデータのベクトルがある場合、それらをムーブ構築すると、基本的に保持されているデータへのポインターがコピーされ、ソースオブジェクトが空としてマークされます。これは、コピーや破棄に比べて非常に安価であり、move-constructable 型のコストのかかるベクトル再割り当ての問題を効果的に解決します。これは、言語に組み込まれている、説明したスワップ最適化とほとんど同じです。

score 1 · Accepted Answer

標準が何を言っているのか、正確にはわかりません。stl のデフォルトはコピーです。ベクトルのベクトルを頻繁に編集する場合、これは面白くありません。

ただし、必要な動作は Visual C++ の TR1 実装で実装されており、VS2008 の更新として利用できます (TR1 は C++ 0x 標準への前奏曲のようなものです)。彼らは、他の多くのコンパイラベンダーと同様に、Dinkumware から stl 実装を購入しているため、これが他のコンパイラで表示されることを期待できます。http://msdn.microsoft.com/en-us/library/bb982198.aspxを参照してください。

GCC を使用している場合、これは役に立ちませんが、おそらく他の人が教えてくれるでしょう。

[編集] 編集後に読んでみると、Microsoft が swap() 最適化は dinkimware の機能ではなく、Microsoft の機能であると主張していることがわかりました。少なくとも、このブログ投稿を読む方法は次のとおりです。

score 1 · Accepted Answer

基本的に、次のことを行うとどうなるかを尋ねています。

vector<int> v;
v.reserve(100);

この場合の libstdc++ の動作を例として見てみましょう。

template<typename _Tp, typename _Alloc> void vector<_Tp, _Alloc>::reserve(size_type __n) {
    if (__n > this->max_size())
        __throw_length_error(__N("vector::reserve"));
    if (this->capacity() >= __n)
        return;

    const size_type __old_size = size();
    pointer __tmp = _M_allocate_and_copy(__n,
        _GLIBCXX_MAKE_MOVE_ITERATOR(this->_M_impl._M_start),
        _GLIBCXX_MAKE_MOVE_ITERATOR(this->_M_impl._M_finish));
    std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, _M_get_Tp_allocator());
    _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
    this->_M_impl._M_start = __tmp;
    this->_M_impl._M_finish = __tmp + __old_size;
    this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
}

ここで重要な呼び出しは_M_allocate_and_copy です

template<typename _ForwardIterator> pointer _M_allocate_and_copy(size_type __n, _ForwardIterator __first, _ForwardIterator __last) {
    pointer __result = this->_M_allocate(__n);
    std::__uninitialized_copy_a(__first, __last, __result, _M_get_Tp_allocator());
    return __result;
}

ここで重要な呼び出しはstd::__uninitialized_copy_aです

template<typename _InputIterator, typename _ForwardIterator, typename _Allocator> _ForwardIterator __uninitialized_copy_a(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _Allocator& __alloc) {
    _ForwardIterator __cur = __result;
    for (; __first != __last; ++__first, ++__cur)
        __alloc.construct(&*__cur, *__first);
    return __cur;
}

これはconstructを呼び出しています。ご覧のとおり、コピーコンストラクターを使用しています。

void construct ( pointer p, const_reference val ) {
    new ((void*)p) T (val);
}

したがって、再割り当てが発生すると、ベクター内のすべての要素にコピーコンストラクターが呼び出されます。

score 0 · Accepted Answer

残念ながら、C++ 0x 標準について議論する際に swap 関数の使用が見落とされていました。

私の意見では、スワップは言語レベルで知られている基本的な機能であるべきです。言語に右辺値参照を追加するための多くの論理的根拠を解決します。

関数から std::vector を返すか、temporary から代入すると、コピーの代わりにスワップを使用できます。コンテナはそれを使用して再割り当てを最適化できます。

ああ。:(

score -2 · Accepted Answer

非常に大きなベクトルがあり、それを解放したい場合は、swap 関数を使用して空のベクトルと交換できます。これは、STL コンテナを使用するときにメモリ領域を解放する非常に効率的な方法です。

c++ - std :: vectorは成長時にスワップ関数を呼び出しますか？常にまたは一部のタイプのみ？

7 に答える 7

Related

Reference