c++ - リストの要素と次の要素へのイテレータ

Question

Bjarne が何を考えているかわかりません。

リスト反復子は、一般にリストの要素がそのリストの次の要素がどこにあるかを知らないため、要素への単純なポインターよりも複雑なものでなければなりません。したがって、リスト反復子はリンクへのポインターである可能性があります

リストのノードには、次のノードと前のノードへのポインターがあることを知っています。では、どのように「一般的にはわからない」のですか？

Answer 1

対照的に、のイテレータについて考えてみましょうstd::vector。おそらくしたくないかもしれませんが、基本的には単純なポインタとして実装できます。

template <class T>
class vector {
    T *data;
    size_t current_size;
    size_t alloc_size;
public:
    typedef T *iterator;
    iterator begin() { return data; }
    iterator end() { return data+current_size; }
    // ...
};

また、ベクトル内のデータは連続しているため、（たとえば）++イテレーターで実行すると、正しいことを実行します（ベクトル内の次の項目に移動します）。

リンクリストを使用すると、それほど単純にすることはできません。typedefイテレータをのエイリアスにした場合T *、正しく機能しません。イテレータで実行しようとすると++、必要に応じてリンクリスト内の次の要素に移動するのではなく、ポインタがインクリメントされます。

イテレータクラスにインテリジェンスを組み込む必要があります。これにより、operator ++（1つの例）は、単にインクリメントするのではなく、ポインタを「追跡」することができます。

template <class T>
class list { 

    class node { 
        T data;
        node *next;
        node *prev;
    };
public:
    class iterator {
        node *pos;
    public:
        iterator operator++() {
            return pos = pos->next;
        }
        iterator operator--() {
            return pos = pos->prev;
        }
    };
};

Answer 2

リスト ノードとリスト要素を混同しないでください。これはポインタかもしれませんが、要素と次/前のリンクを含むノードへのポインタです。それが要素への単なるポインターである場合、それを移動することはできません。(通常、それ自体をインクリメントするのではなく、次のポインターをフェッチするために operator++ をオーバーロードする必要があるため、単なるポインターである可能性は低いですが)。

これは、ノード == 要素である侵​​入型リストには当てはまりませんが、std::list ではありません。

// illustrative
template <typename ElementType>
struct list_node {
    ElementType element;
    list_node *next, *prev;
};