C++のイテレータカテゴリはどのように機能しますか？

Question

私はイテレータの実装を理解しようとした、およびソースで遊んでいる間、私はこの文を見た：

typedef output_iterator_tag iterator_category; 

私はクラス内でどのようにこの作品のtypedefを理解していませんか？それは何の副作用ですか？誰もがこれで私を歩くことができますか？

Answer 1

この回答が得られにくいので、一般的なプログラミングを読む必要があります。

「出力イテレータ」は、特定のイテレータが一致する概念です。この概念の実現である各反復子には、それに関連する特定の機能があります。それは相続のようなものですが、そうではありません。

C++には、概念を表すものはありません（C++ 0xに追加された提案でしたが、作成に失敗しました）。その場合、 "タグ"とイテレータタイプを関連付けるために、さまざまなテンプレート構造が必要です。 output_iterator_tag型をイテレータに関連付けることによって、イテレータ型がOutputIteratorコンセプトを実現すると主張しています。

これは、可能な限り最適化されたアルゴリズムと一般的なアルゴリズムを作成する場合に非常に重要になります。たとえば、反復子を使用して、この能力を持たないソートよりも任意の値（つまり、1以外）でインクリメントまたはデクリメントできるソートを実行する方が効率的です。さらに、新しいイテレータを得るためには、イテレータの能力に応じて異なるオペレーションが必要になります。このようなアルゴリズムを書くには、 "tag dispatching"を使います。これをさらに詳しく説明すると、std :: advanceの実装（テストされていない）は、+演算子を持つイテレータと++演算子しかなく、両方のバージョンで可能な限り速いイテレータの両方で動作します。それはおそらくバグだらけですので、メモリからだ

template < typename RandomAccessIterator > 
RandomAccessIterator advance(RandomAccessIterator it 
          , int amount 
          , random_access_iterator_tag) 
{ return it + amount; } 

template < typename ForwardIterator > 
ForwardIterator advance(ForwardIterator it, int amount, forward_iterator_tag) 
{ 
    for (;amount; --amount) ++it; 
    return it; 
} 

template < typename Iterator > 
Iterator advance(Iterator it, int amount) 
{ 
    typedef typename std::iterator_traits<Iterator>::iterator_tag tag; 
    advance(it, amount, tag()); 
} 

は（おそらくタイプ間違っさえの束を持っている）...それはアイデアです。イテレータータグは、空であり、概念を互いに洗練するのとまったく同じ方法で互いに継承するタイプです。例えば、ランダムアクセスイテレータは前方イテレータです。したがって、random_access_iterator_tagは、forward_iterator_tagの派生語である。関数オーバーロード解決規則のため、random_access_iterator_tagを関数に渡すと、forward_iterator_tagではなくその関数のバージョンに解決されます。

もう一度、一般的なプログラミングについてお読みください。 C++のフルパワーを利用することは不可欠です。

ああ、ついに... typedefはイテレータのクラス定義の中にあります。なぜなら、それを置くのに便利な場所だからです。デフォルトのiterator_traitsはそれを探すことができます。 rawポインタもイテレータであり、内部typedefを持つことができないため、その定義ではなくiterator_traitsを使用したいと思うでしょう。

Answer 2

output_iterator_tagは空のクラスです。その目的は、アルゴリズムが特定の規則に従い、特定の演算子を提供するイテレータの一般的な分類を識別できるようにすることです。これにより、アルゴリズムは、特定の条件下で、所与のアルゴリズムのより特殊化された実装を提供することが可能になる。 VS2010のヘッダ、例えば

、「STD ::距離」iterator_category 『に渡されたイテレータにtypedefさのアルゴリズムは、に応じて、2つの実装を持っているが』

のstd ::距離だけ入力イテレータを必要と2つのイテレータ間の距離を計算するためには、答えを計算するために線形の 'O（n）'時間がかかることがあります。

しかし、コンパイラはランダムアクセスイテレータが使用されていることを認識し、減算演算子を利用して一定時間 'O（1）'で距離を計算できます。

私はStephan T. Lavavejのvideoを見て、標準的なテンプレートライブラリでタイプ特性とその用途に少し触れることをお勧めします。