STLソースノートの型別抽出技法(2)
6311 ワード
1.iterator_category
(1)Input Iterator:このような反復器が指すオブジェクトは,外部接続の変更を許さず,読み取り専用である.
(2)Output Iterator:書き込みのみ.
(3)Forward Iterator:「書き込み型」アルゴリズムは,この反復器によって形成される区間で読み書き動作を可能にする.
(4)Bidirectional Iterator:双方向移動可能.いくつかのアルゴリズムでは、Bidirectional Iteratorを使用することができる反復器区間を逆方向に訪問する必要があります.
(5)Random Access Iterator:最初の4つの反復器はポインタの一部のみを提供する能力(最初の3つはoperator++,operator--)をサポートし、5つ目はすべてのポインタの算術能力をカバーする.p+n、p−n、p[n]、p 1−p 2、p 1
2.std::iteratorの保証
仕様に適合するためには、traits抽出を容易にするために、任意の反復器が必要です.そうしないと、STLアーキテクチャ全体とは異なり、STLコンポーネントとうまく組み合わせることができない可能性があります.STLは、各反復器が継承する標準的なiterator classを定義し、統一されたローを保証します.
iterator classにはメンバーは含まれていません.純粋な型別定義なので、継承は負担になりません.後の3つのパラメータにはデフォルト値があります.したがって、心得反復器は2つのパラメータを提供するだけでよい.
template
struct ListIter:public std: iterator
{...........}
3.__type_traits
タイプは大まかに2つあります.1つはclassでカプセル化され、そのコピーには時間がかかります.例えば、深さのコピーが必要で、safe copyingが必要です.つまり、構造関数を呼び出してコピーを完了する必要があります.もう1つはいわゆるPOD(plain old data)で、一般的にbuild-inタイプかc式のstructタイプで、このタイプはメモリブロックをコピーしてコピーするだけでいいので、bitwise copyingやtrival construct/deconstruct/copy/assignmentの概要があります.
SGI STLで使用_type_traitsは、コンパイル中にオブジェクトをコピーするかmemcpyを直接呼び出すかを決定し、効率を向上させることができます.SGI STLのソースコードを見てください.
struct __true_type {};
struct __false_type {};
template //primariy template
struct __type_traits {
typedef __true_type this_dummy_member_must_be_first;
typedef __false_type has_trivial_default_constructor;
typedef __false_type has_trivial_copy_constructor;
typedef __false_type has_trivial_assignment_operator;
typedef __false_type has_trivial_destructor;
typedef __false_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits { //full specialization
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
次に、使い方を見てみましょうtype_trairt:
[cpp] view plain copy
template
inline ForwardIterator __uninitialized_copy(InputIterator first, InputIterator last,
ForwardIterator result, T*) {
typedef typename __type_traits::is_POD_type is_POD;
return __uninitialized_copy_aux(first, last, result, is_POD());
}
template inline ForwardIterator
__uninitialized_copy_aux(InputIterator first, InputIterator last,
ForwardIterator result, __true_type) {
return copy(first, last, result);//STLアルゴリズムcopyには乾坤があり、PODタイプに対してmemmoveを呼び出し、iterator_も含まれている.traitの使用}
template
ForwardIterator __uninitialized_copy_aux(InputIterator first, InputIterator last,
ForwardIterator result, __false_type) {
ForwardIterator cur = result;
for ( ; first != last; ++first, ++cur)
construct(&*cur, *first);
return cur;
}
}
(1)Input Iterator:このような反復器が指すオブジェクトは,外部接続の変更を許さず,読み取り専用である.
(2)Output Iterator:書き込みのみ.
(3)Forward Iterator:「書き込み型」アルゴリズムは,この反復器によって形成される区間で読み書き動作を可能にする.
(4)Bidirectional Iterator:双方向移動可能.いくつかのアルゴリズムでは、Bidirectional Iteratorを使用することができる反復器区間を逆方向に訪問する必要があります.
(5)Random Access Iterator:最初の4つの反復器はポインタの一部のみを提供する能力(最初の3つはoperator++,operator--)をサポートし、5つ目はすべてのポインタの算術能力をカバーする.p+n、p−n、p[n]、p 1−p 2、p 1
コンパイル反復器の動的選択を提供するために、STLは5つのタグ用のタイプを定義し、反復器に関連する関数を呼び出すと、対応する反復器の特性に合致する関数を選択することができます.5つの反復器はそれぞれ次のとおりです.
struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag: public input_iterator_tag{};
struct bidirection_iterator_tag: public forward_iterator_tag{};
struct random_access_iterator_tag: public bidirection_iterator_tag{};
これらのclassはタグとしてのみ使用され、スペースを占有しません.
//advance()
// ,
template<class InputIterator,class Distance>
inline void__advance(InputIterator& i,Distance n,input_iterator_tag)
{while(n--)++i;}
template<class ForwardIterator,class Distance>
inline void__advance(ForwardIterator& i,Distance n,forward_iterator_tag)
{
__advance(i,n,input_iterator_tag);
}
template<class BidirectionalIterator,class Distance>
inline void__advance(BidirectionalIterator& i,Distance n,bidirectional_iterator_tag)
{
if(n>=0)while(n--)++i;
else while(n++)--i;
}
template<class RandomAccessIterator,class Distance>
inline void__advance(RandomAccessIterator& i,Distance n,random_access_iterator_tag)
{
i+=n;
}
// ,InputIterator
template<class InputIterator,class Distance>
inline void advance(InputIterator& i,Distance n)
{
//
// iterator_category iterator_traits
__advance( i,n,iterator_traits<InputIterator>::iterator_category());
}
2.std::iteratorの保証
仕様に適合するためには、traits抽出を容易にするために、任意の反復器が必要です.そうしないと、STLアーキテクチャ全体とは異なり、STLコンポーネントとうまく組み合わせることができない可能性があります.STLは、各反復器が継承する標準的なiterator classを定義し、統一されたローを保証します.
template<
class Category,
class T,
class Distance = ptrdiff_t,
class Pointer = T*,
class Reference = T&
>
struct iterator{
typedef Category iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference ;
};
iterator classにはメンバーは含まれていません.純粋な型別定義なので、継承は負担になりません.後の3つのパラメータにはデフォルト値があります.したがって、心得反復器は2つのパラメータを提供するだけでよい.
template
struct ListIter:public std: iterator
{...........}
3.__type_traits
タイプは大まかに2つあります.1つはclassでカプセル化され、そのコピーには時間がかかります.例えば、深さのコピーが必要で、safe copyingが必要です.つまり、構造関数を呼び出してコピーを完了する必要があります.もう1つはいわゆるPOD(plain old data)で、一般的にbuild-inタイプかc式のstructタイプで、このタイプはメモリブロックをコピーしてコピーするだけでいいので、bitwise copyingやtrival construct/deconstruct/copy/assignmentの概要があります.
SGI STLで使用_type_traitsは、コンパイル中にオブジェクトをコピーするかmemcpyを直接呼び出すかを決定し、効率を向上させることができます.SGI STLのソースコードを見てください.
struct __true_type {};
struct __false_type {};
template
struct __type_traits {
typedef __true_type this_dummy_member_must_be_first;
typedef __false_type has_trivial_default_constructor;
typedef __false_type has_trivial_copy_constructor;
typedef __false_type has_trivial_assignment_operator;
typedef __false_type has_trivial_destructor;
typedef __false_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
次に、使い方を見てみましょうtype_trairt:
[cpp] view plain copy
template
inline ForwardIterator __uninitialized_copy(InputIterator first, InputIterator last,
ForwardIterator result, T*) {
typedef typename __type_traits
return __uninitialized_copy_aux(first, last, result, is_POD());
}
template
__uninitialized_copy_aux(InputIterator first, InputIterator last,
ForwardIterator result, __true_type) {
return copy(first, last, result);//STLアルゴリズムcopyには乾坤があり、PODタイプに対してmemmoveを呼び出し、iterator_も含まれている.traitの使用}
template
ForwardIterator __uninitialized_copy_aux(InputIterator first, InputIterator last,
ForwardIterator result, __false_type) {
ForwardIterator cur = result;
for ( ; first != last; ++first, ++cur)
construct(&*cur, *first);
return cur;
}
}