イテレータend（）を呼び出して実装できますか？

Question

まず、私は本当に（私の講師による）ので、ここでの短い実装はリングが何であるかを見せて、インターネット上で

template<typename Key, typename Info> 
class Ring 
{ 
struct Node // structure for storing the data 
{ 
    Key k; 
    Info inf; 

    Node* next; 
    Node* prev; 
}; 

Node* any; // pointer to a node belonging to the ring, NULL if the ring is empty 
}; 

をリングデータ構造に関する多くの情報を見つけることができませんそれは循環リストに似ていますが、any構造内の任意の要素を指すことができますが、私たちは追加する順番に気をつけません。

私がすでに行っているプロジェクトの主なタスクの他に、このようなその、

for(auto it = r1.begin(); it != r1.end(); ++it)  // r1 is a ring 
{ cout << *it << ' '; } 

は正常に動作します。リング全体を印刷します。

それは可能ですか？イテレーターのend（）は、次の要素が追加される場所を指している必要があり、そのような点はありません。 any（begin（）と同じ）に設定すると、ループはまったく実行されず、any->prevに設定されている場合、最後の要素は省略されます。

アイデアはありますか？これはどのように実装できますか？それとも不可能なのでしょうか？

Answer 1

end()は、環の文脈で意味がありません。「最後の要素を過ぎたもの」という環の位置を特定することはできません。これはend()です。

リングを反復する慣用方法は、2つのイテレータを任意の点から反対方向に送り、両方のイテレータが到達し、そのうちの1つが同じ要素を処理した後に終了することです。

Answer 2

次いで一つの項目リング用

、begin()及びend()両方のノードを参照する必要がある場合、begin()とend()は明らかに同じノードを指し、それは、最初の反復の前に出口にループを引き起こすので、それらが等しいとすることができません。

したがって、これらのイテレータでは、それらが参照するノードに関して等価を定義することはできません。

I.e.適切な方法でイテレータの等価性を定義するだけです。

---

多くの場合、終了イテレータは単なるデフォルト構築イテレータです。

これは新しいことではありません。

---

例：

#include <assert.h>   // assert.h 
#include <iterator>   // std::(iterator, forward_iterator_tag) 
#include <utility>   // std::(pair) 

namespace cppx { 
    class Non_copyable 
    { 
    private: 
     Non_copyable(Non_copyable const&) = delete; 
     auto operator=(Non_copyable const&) -> Non_copyable& = delete; 
    public: 
     auto operator=(Non_copyable&&) {} 
     Non_copyable() {} 
     Non_copyable(Non_copyable&&) {} 
    }; 
} // namespace cppx 

namespace my { 
    using std::pair; 
    using std::iterator; 
    using std::forward_iterator_tag; 

    template< class Key, class Value > 
    class Ring 
     : public cppx::Non_copyable 
    { 
    public: 
     using Pair = pair<Key, Value>;  // Movable 

    private: 
     struct Node    // For storing the data 
     { 
      // Key key; 
      // Value value; 
      Pair kv; 

      Node* next; 
      Node* prev; 
     }; 

     class Iterator 
      : public iterator<forward_iterator_tag, Pair> 
     { 
     private: 
      Node* p_first_; 
      Node* p_current_; 

      auto is_end() const -> bool { return p_first_ == nullptr; } 

      void advance() 
      { 
       p_current_ = p_current_->next; 
       if(p_current_ == p_first_) 
       { 
        p_first_ = nullptr; 
        assert(is_end()); 
       } 
      } 

     public: 
      friend 
      auto operator==(Iterator const& a, Iterator const& b) 
       -> bool 
      { return !!a.p_first_ == !!b.p_first_ and a.p_current_ == b.p_current_; } 

      friend 
      auto operator!=(Iterator const& a, Iterator const& b) 
       -> bool 
      { return not(a == b); } 

      auto operator++() 
       -> Iterator& 
      { 
       advance(); 
       return *this; 
      } 

      auto operator++(int) 
       -> Iterator 
      { 
       Iterator result = *this; 
       advance(); 
       return result; 
      } 

      auto operator*() const 
       -> Pair const& 
      { return p_current_->kv; } 

      auto operator->() const 
       -> Pair const* 
      { return &p_current_->kv; } 

      Iterator(Node* p, bool be_end = false) 
       : p_first_(be_end? nullptr : p) 
       , p_current_(p) 
      {} 
     }; 

     Node* p_current_;  // Node in the ring, 0 if the ring is empty. 

    public: 
     // TODO: add new node, before current node if any. 
     void add(Pair kv); 

     // TODO: advance n positions, backward for negative n. 
     void advance(int const n = 1); 

     // TODO: a unique id for current position. 
     auto current_position() const -> void const*; 

     auto is_empty() const -> bool; 

     auto current() const -> Pair const&; 

     auto begin() const -> Iterator  { return {p_current_}; } 
     auto end() const -> Iterator  { return {p_current_, true}; } 

     Ring(): p_current_() {} 

     Ring(Ring&& other) 
      : p_current_(other.p_current_) 
     { other.p_current_ = nullptr; } 
    }; 
} // namespace my 

#include <iostream> 
using namespace std; 

auto operator<<(ostream& stream, my::Ring<int, int>::Pair const& kv) 
    -> ostream& 
{ return stream << "{" << kv.first << ", " << kv.second << "}"; } 

auto main() 
    -> int 
{ 
    using Ring = my::Ring<int, int>; 

    Ring r; 
    for(int i : {3, 1, 4, 1, 5, 9, 2, 6, 5, 4}) 
    { 
     r.add({i, i*i}); 
    } 

    // Output via explicit iteration. 
    auto const first = r.current_position(); 
    do 
    { 
     if(r.current_position() != first) { cout << ", "; } 
     cout << r.current(); 
     r.advance(); 
    } while(r.current_position() != first); 
    cout << "\n"; 

    // Output via range based `for` using `begin` and `end` iterators. 
    int count = 0; 
    for(Ring::Pair const& kv : r) 
    { 
     if(count++ > 0) { cout << ", "; } 
     cout << kv; 
    } 
    cout << "\n"; 
} 

出力：

 
{3, 9}, {1, 1}, {4, 16}, {1, 1}, {5, 25}, {9, 81}, {2, 4}, {6, 36}, {5, 25}, {4, 16} 
{3, 9}, {1, 1}, {4, 16}, {1, 1}, {5, 25}, {9, 81}, {2, 4}, {6, 36}, {5, 25}, {4, 16}