template<class InputIterator, class OutputIterator> OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result) { while(first != last) *result++ = *first++; return result; }
STLは、すべての通常のC ++プログラムで使用される最も基本的なライブラリです。 したがって、アルゴリズムの最も効率的な実装を提供する必要があります。 そして、多くの点で効果的です：
- 実行速度
- コンパイラ生成のコードサイズ
- メモリ消費
- コンパイル速度
実行速度
テンプレートをインスタンス化する型の機能を考慮すると、コードを高速化できます。 たとえば、型に単純なコピーコンストラクタがある場合、バイト単位でコピーできます。 また、オブジェクトが連続メモリ領域にある場合、コンストラクターを繰り返し呼び出す代わりに、古き良きC関数memmoveを使用できます。これは、データを特に迅速にコピーするベクトルプロセッサ命令を使用できます。 memcpyは重複しないメモリ領域でのみ機能するため、std :: copy実装ではmemcpyを使用できないことに注意してください。したがって、std :: copyの2つの実装を作成します。1つは簡単にコピーされるタイプ用に高速で、もう1つは他のすべてに汎用です。
SFINAE
そして、ここに「置換の失敗はエラーではない」として知られる助けがあります。 テンプレートパラメータの置換時に誤った式が取得された場合、これはエラーではありません。 コンパイラはパターンを無視して、検索を続行する必要があります。 テンプレート関数の場合、特定のテンプレートがすでに選択されていて、検索を続行する場所がない場合、関数の本体ではなくプロトタイプで誤った式が見つかることが重要です。 これを行う最も簡単な方法は、std :: enable_ifを使用することです。std :: enable_if
Enable_if自体は非常に単純です。 これは、整数定数と型からのテンプレートです。 定数がtrueの場合、typeという名前のネストされた型の宣言が含まれ、そうでない場合は空です。 // Define a nested type if some predicate holds. // Primary template. /// enable_if template<bool, typename _Tp = void> struct enable_if { }; // Partial specialization for true. template<typename _Tp> struct enable_if<true, _Tp> { typedef _Tp type; };
種類 std::enable_if<, Type>::type
定義され、タイプTypeになりますが、条件がtrueの場合のみです。 次のように使用します。 // template<class T> std::enable_if<false, T>::type get_t() {return T();} // template<class T> std::enable_if<true, T>::type get_t() {return T();}
型特性
上記のすべてを理解するためには、タイプに応じて定数が必要です。 それらは型特性と呼ばれます。 これらは、テンプレートがインスタンス化される型に応じて値trueまたはfalseをとる静的定数パブリックプロパティ値を持つテンプレート構造です。 それらの一部は、テンプレートの部分的な特殊化を使用して説明され、一部はコンパイラーによって実装され、一部は他の型の特性に対する式として構築されます。std ::コピーの特別な実装
ユニバーサル実装の前に、これを追加します： template<class T> // gcc 4.5 std::is_trivially_copiable, //inline typename std::enable_if<std::is_trivially_copiable<T>::value, T*>::type inline typename std::enable_if<std::is_trivial<T>::value, T*>::type copy(T* first, T* last, T* result) { const ptrdiff_t num = last - first; memmove(result, first, sizeof(T) * num); return result + num; }
簡単にコピーされた型への3つのポインターでcopyが呼び出された場合、コンパイラーはこの最適化された実装を適用します。 それ以外の場合、このテンプレートは無視され、ユニバーサルバージョンが使用されます。
実際のライブラリでは、標準ではstd :: copyに2つのテンプレートパラメーターがあると記載されているため、すべてが少し複雑になります。 プログラマがそれらを明示的に指定した場合、最適化されたオプションを選択する必要があります。 したがって、さまざまな実装がサービス名の下に記述されており、std :: move自体には、最適な実装を選択するコードがあります。 これは非常に簡略化されたバージョンです。
#include <type_traits> #include <cstring> // : C++11. // C++03 type_traits ( ) // . // is_simple, memmove, . // . template<bool is_simple> struct __do_copy; // , _. // . // , // . std::copy template<> struct __do_copy<true> { // // , // memmove . template<class InputIterator, class OutputIterator> static inline OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result) { typedef typename std::iterator_traits<InputIterator>::value_type ValueType; const std::ptrdiff_t num = last - first; memmove(result, first, sizeof(ValueType) * num); return result + num; } }; template<> struct __do_copy<false> { // template<class InputIterator, class OutputIterator> static inline OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result) { while(first != last) *result++ = *first++; return result; } }; // trait // STL template<typename, typename> struct are_same : public std::false_type {}; template<typename Tp> struct are_same<Tp, Tp>: public std::true_type {}; template<class InputIterator, class OutputIterator> inline InputIterator copy( InputIterator first, InputIterator last, OutputIterator result) { // typename , value_type // , , . . typedef typename std::iterator_traits<InputIterator>::value_type ValueTypeI; typedef typename std::iterator_traits<OutputIterator>::value_type ValueTypeO; const bool is_simple = ( std::is_trivial<ValueTypeI>::value && std::is_pointer<InputIterator>::value && std::is_pointer<OutputIterator>::value && are_same<ValueTypeI, ValueTypeO>::value); // return __do_copy<is_simple>::do_copy(first, last, result); }
さらに、GNU STLは別の最適化を使用します：ランダムアクセスイテレーターの場合、forループを使用して反復回数を計算します。 コンパイラはこのようなサイクルを展開して、プログラムの速度を向上させることができます。 生成されたコードのサイズ
記事の冒頭のテンプレートは、新しいタイプごとに完全に新しいコードを生成することに注意してください。 2番目のテンプレートは、ポインターの1つの減算と1つの加算に縮退し、memmoveの実装はすべてのタイプに共通です。 つまり、プログラムの高速化に加えて、プログラムのサイズが小さくなります。 コンテナでも同様のトリックを使用できます。保存された型に依存しない部分はテンプレートから削除され、一般的な実装が使用されます。 たとえば、std ::リストの実装では、データを格納するテンプレート構造にはデータ自体のみが含まれます。 近隣へのリンクとそれらに対する操作は、継承元の非テンプレートクラスに実装されます。ライブラリ関数を使用する
この記事の教訓は単純です。できるだけ標準ライブラリが提供するアルゴリズムを使用してください。 プログラムをより効率的で理解しやすく柔軟にします。標準ライブラリの開発者は、通常のコードでは手に入らない最適化を適用できるため、 より効果的です。 12種類のプラットフォームでオブジェクトをコピーするいくつかの実装を作成してサポートする準備ができていませんか？ アプリケーションプログラマには、この時間はありません。
同僚に馴染みのあるプリミティブを使用して、短い高レベルのコードを書くことができるため、 より理解しやすくなります。
時期尚早な最適化を行う必要がなく、自分で書くよりも一般的なアルゴリズムを使用するため、 より柔軟です。