c++ - vector::iterator または list::iterator の代わりに「任意の種類の入力反復子」を返す

Question

有向グラフを格納するためのデータ構造を C++ で実装したいとします。アークは、STL コンテナーのおかげでノードに格納されます。STL のような方法で、ユーザーがノードのアークを反復処理できるようにしたいと考えています。

私が抱えている問題は、具体的なクラスで実際に使用する STL コンテナーを Node クラス (実際には抽象基本クラスになる) で公開したくないということです。したがって、メソッドが std::list::iterator または std::vector::iterator を返すようにしたくありません...

私はこれを試しました：

class Arc;

typedef std::iterator<std::random_access_iterator_tag, Arc*> ArcIterator;  // Wrong!

class Node {
public:
  ArcIterator incomingArcsBegin() const {
    return _incomingArcs.begin();
  }
private:
  std::vector<Arc*> _incomingArcs;
};

しかし、vector::const_iterator を使用して ArcIterator を作成することはできないため、これは正しくありません。では、この ArcIterator は何でしょうか?

STL のカスタムイテレータに関するこの論文を見つけましたが、役に立ちませんでした。今日はちょっと重いかな…;)

score 8 · Accepted Answer

これを試して：

class Arc;
class Node {
private:
  std::vector<Arc*> incoming_;
public:
  typedef std::vector<Arc*>::iterator iterator;
  iterator incoming_arcs_begin()
  { return incoming_.begin(); }
};

そして、コードの残りの部分で Node::iterator を使用します。コンテナーを変更する場合は、1 つの場所で typedef を変更する必要があります。(ストレージ (この場合はベクトル) の追加の typedef を使用して、これをさらに一歩進めることができます。)

const の問題については、vector の const_iterator をイテレータとして定義するか、vector のように二重反復子型 (const および非 const バージョン) を定義します。

score 3 · Accepted Answer

Adobe のを見てくださいany_iterator。このクラスは、基になるイテレータ型を抽象インターフェイスの背後に隠す型消去と呼ばれる手法を使用します。注意: を使用するとany_iterator、仮想ディスパッチにより実行時のペナルティが発生します。

score 1 · Accepted Answer

ビジターパターンを使用し、関係を逆にすることを検討してください。グラフ構造にデータのコンテナーを要求する代わりに、グラフにファンクターを与え、グラフがそのファンクターをデータに適用できるようにします。

ビジターパターンは、グラフで一般的に使用されるパターンです。ビジターの概念に関するブーストのグラフライブラリドキュメントを確認してください。

score 1 · Accepted Answer

あなたがやろうとしていることと同様に、ストレートSTLを介してこれを行う方法があるべきだと思います。

そうでない場合は、独自のイテレーターを定義したり、他のオブジェクトをイテレーターに適応させたりできる、ブーストのイテレーターファサードとアダプターの使用を検討することをお勧めします。

score 1 · Accepted Answer

イテレータがに基づいているという事実を隠すには、std::vector<Arc*>::iteratorにデリゲートするイテレータクラスが必要ですstd::vector<Arc*>::iterator。std::iteratorこれはしません。

コンパイラの C++ 標準ライブラリのヘッダーファイルを見ると、、などstd::iteratorの typedef を定義するクラスだけが必要な場合を除き、それ自体ではあまり役に立たないことがわかります。iterator_categoryvalue_type

Doug T. が回答で述べたように、boost ライブラリにはイテレータを簡単に記述できるクラスがあります。特に、イテレータが逆参照時にではなくboost::indirect_iteratorを返すようにしたい場合に役立つ場合があります。ArcArc*

score 0 · Accepted Answer

Nodeクラスをテンプレート化し、その中でiteratorとconst_iteratorの両方をtypedefすることができます。

例えば：

class Arc {};

template<
  template<class T, class U> class Container = std::vector,
  class Allocator = std::allocator<Arc*>
>
class Node
{
  public:
    typedef typename Container<Arc*, Allocator>::iterator ArcIterator;
    typedef typename Container<Arc*, Allocator>::Const_iterator constArcIterator;

    constArcIterator incomingArcsBegin() const {
      return _incomingArcs.begin();
    }

    ArcIterator incomingArcsBegin() {
      return _incomingArcs.begin();
    }
  private:
    Container<Arc*, Allocator> _incomingArcs;
};

私はこのコードを試していませんが、それはあなたにアイデアを与えます。ただし、ConstArcIteratorを使用すると、Arc自体の変更ではなく（たとえば、非constメソッドによる）Arcへのポインターの変更が許可されないことに注意する必要があります。

score 0 · Accepted Answer

ヘッダーファイル VECTOR を調べました。

vector<Arc*>::const_iterator

のtypedefです

allocator<Arc*>::const_pointer

それはあなたの ArcIterator でしょうか? お気に入り：

typedef allocator<Arc*>::const_pointer ArcIterator;

score 0 · Accepted Answer

C++0x では、自動型決定でこれを行うことができます。

新しい規格では、これ
for (vector::const_iterator itr = myvec.begin(); itr != myvec.end(); ++itr
をこれに置き換えることができます
for (auto itr = myvec.begin(); itr != myvec.end(); ++itr)

同様に、適切な反復子を返し、それをauto変数に格納することができます。

新しい標準が導入されるまでは、クラスをテンプレート化するか、リスト/ベクターの要素にアクセスするための抽象インターフェイスを提供する必要があります。たとえば、イテレータをメンバー変数に格納し、やなどのメンバー関数を提供することでこれを行うことができbegin()ますnext()。もちろん、これは一度に 1 つのループだけが要素を安全に反復できることを意味します。

score 0 · Accepted Answer

連続したストレージがあることが保証されているためstd::vector、これを実行しても問題ありません。

class Arc;
typedef Arc* ArcIterator;

class Node {
public:
    ArcIterator incomingArcsBegin() const {
        return &_incomingArcs[0]
    }

    ArcIterator incomingArcsEnd() const {
        return &_incomingArcs[_incomingArcs.size()]
    }
private:
    std::vector<Arc*> _incomingArcs;
};

基本的に、ポインターはランダムアクセス反復子のように十分に機能するため、十分な代替手段となります。

score 0 · Accepted Answer

そのクラスのクライアントに、その下でベクターを使用していることを本当に知られたくないが、何らかの方法でそれを反復処理できるようにしたい場合は、すべてのメソッドを std に転送するクラスを作成する必要があります。 ::ベクトル::イテレータ。

別の方法は、ノードが使用するコンテナのタイプに基づいてノードをテンプレート化することです。次に、クライアントは、使用するように指示したため、使用しているコンテナーのタイプを明確に認識します。

個人的には、ベクターをカプセル化してユーザーから離すことは通常は意味がないと思いますが、それでもそのインターフェースのほとんど (または一部) を提供します。カプセル化層が薄すぎて、実際に利点を提供できません。

c++ - vector::iterator または list::iterator の代わりに「任意の種類の入力反復子」を返す

10 に答える 10

Related

Reference