Home > OS >  What is my random access iterator missing?
What is my random access iterator missing?

Time:03-25

Consider the following code:

#include <iterator>
#include <iostream>

struct Node {
  static Node mNode;
};  
        
Node Node::mNode;
    
struct DeepNodeRange {};
    
class DeepNodeIter
{ 
public:
  using iterator_category = std::random_access_iterator_tag;
  using value_type = Node*;
  using difference_type = std::ptrdiff_t;
      
  DeepNodeIter() = default;
      
  DeepNodeIter(DeepNodeRange& deepNodeRange, bool end = false) :
    mDeepNodeRange(&deepNodeRange), mIdx(0), mEnd(end) {}
        
  Node* operator[](int idx) const { return &Node::mNode; }
    
  Node* operator*() const { return &Node::mNode; }
    
  Node* operator->() { return &Node::mNode; }
      
  DeepNodeIter& operator  ()
  {
    mIdx  ;
    mEnd = (mIdx > 10);
      
    return *this; 
  }

  DeepNodeIter operator  ([[maybe_unused]] int val)
  {
    auto tmp(*this);
    operator  ();

    return tmp;
  }

  DeepNodeIter& operator--()
  {
    mIdx--;
    mEnd = (mIdx > 10);

    return *this;
  }

  DeepNodeIter operator--([[maybe_unused]] int val)
  {
    auto tmp(*this);
    operator--();

    return tmp;
  }

  DeepNodeIter& operator =(int val)
  {
    mIdx  = val;
    mEnd = (mIdx > 10);

    return *this;
  }

  DeepNodeIter& operator-=(int val)
  {
    mIdx -= val;
    mEnd = (mIdx > 10);

    return *this;
  }

  int operator (const DeepNodeIter& other) const
  {
    return mIdx   other.mIdx;
  }

  int operator-(const DeepNodeIter& other) const
  {
    return mIdx - other.mIdx;
  }

  DeepNodeIter operator (int val) const
  {
    auto tmp(*this);
    tmp.mIdx  = val;
    return tmp;
  }

  DeepNodeIter operator-(int val) const
  {
    auto tmp(*this);
    tmp.mIdx -= val;
    return tmp;
  }

  bool operator==(const DeepNodeIter& iter) const { return iter.mEnd == mEnd; }

  bool operator!=(const DeepNodeIter& iter) const { return iter.mEnd != mEnd; }

  bool operator<(const DeepNodeIter& iter) const { return iter.mIdx < mIdx; }

  bool operator<=(const DeepNodeIter& iter) const { return iter.mIdx <= mIdx; }

  bool operator>(const DeepNodeIter& iter) const { return iter.mIdx > mIdx; }

  bool operator>=(const DeepNodeIter& iter) const { return iter.mIdx >= mIdx; }

protected:
  DeepNodeRange* mDeepNodeRange;

  int mIdx;

  bool mEnd;
};

static_assert(std::random_access_iterator<DeepNodeIter>);

int main() {
  DeepNodeRange deepNodeRange;

  DeepNodeIter i(deepNodeRange);
  DeepNodeIter j(deepNodeRange);
  std::cout << (i - j) << std::endl;
}

It results in the following compile error:

b.cpp:122:20: error: static assertion failed
  122 | static_assert(std::random_access_iterator<DeepNodeIter>);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
b.cpp:122:20: note: constraints not satisfied
In file included from include/c  /11.1.0/bits/stl_iterator_base_types.h:71,
                 from include/c  /11.1.0/iterator:61,
                 from b.cpp:1:
include/c  /11.1.0/bits/iterator_concepts.h:625:13:   required for the satisfaction of 'sized_sentinel_for<_Iter, _Iter>' [with _Iter = DeepNodeIter]
include/c  /11.1.0/bits/iterator_concepts.h:627:8:   in requirements with 'const _Iter& __i', 'const _Sent& __s' [with _Sent = DeepNodeIter; _Iter = DeepNode
include/c  /11.1.0/bits/iterator_concepts.h:629:13: note: the required expression '(__s - __i)' is invalid
  629 |       { __s - __i } -> same_as<iter_difference_t<_Iter>>;
      |         ~~~~^~~~~
include/c  /11.1.0/bits/iterator_concepts.h:630:13: note: the required expression '(__i - __s)' is invalid
  630 |       { __i - __s } -> same_as<iter_difference_t<_Iter>>;
      |         ~~~~^~~~~
cc1plus: note: set '-fconcepts-diagnostics-depth=' to at least 2 for more detail

I checked and my iterator fulfills all the requires for LegacyRandomIterator. What am I missing here?

CodePudding user response:

Two problems: Your operator- does not return difference_type and your operator signature is all wrong. Regarding the latter, the two types being added must be your iterator and its difference_type, in either order, implying that it must necessarily be a pair of (possibly friend) free functions.

friend DeepNodeIter operator (difference_type n, DeepNodeIter it)
{
    return it  = n;
}

friend DeepNodeIter operator (DeepNodeIter it, difference_type n)
{
    return it  = n;
}

difference_type operator-(const DeepNodeIter& other) const
{
    return mIdx - other.mIdx;
}

Online Demo

Also while it won't make the concept fail, the concept assumes that operator[] also takes difference_type.

CodePudding user response:

The addition and subtraction operators need to use 'difference_type' and alternative addition and subtraction operator needed to be defined outside of the class definition because one of the requirements for the concept is that their arguments can be switched around.

Here's the fixed version of your code:

    #include <iterator>
    #include <iostream>
    
    struct Node {
      static Node mNode;
    };  
            
    Node Node::mNode;
        
    struct DeepNodeRange {};
        
    class DeepNodeIter
    { 
    public:
      using iterator_category = std::random_access_iterator_tag;
      using value_type = Node*;
      using difference_type = std::ptrdiff_t;
          
      DeepNodeIter() = default;
          
      DeepNodeIter(DeepNodeRange& deepNodeRange, bool end = false) :
        mDeepNodeRange(&deepNodeRange), mIdx(0), mEnd(end) {}
            
      Node* operator[](int idx) const { return &Node::mNode; }
        
      Node* operator*() const { return &Node::mNode; }
        
      Node* operator->() { return &Node::mNode; }
          
      DeepNodeIter& operator  ()
      {
        mIdx  ;
        mEnd = (mIdx > 10);
          
        return *this; 
      }
    
      DeepNodeIter operator  ([[maybe_unused]] int val)
      {
        auto tmp(*this);
        operator  ();
    
        return tmp;
      }
    
      DeepNodeIter& operator--()
      {
        mIdx--;
        mEnd = (mIdx > 10);
    
        return *this;
      }
    
      DeepNodeIter operator--([[maybe_unused]] int val)
      {
        auto tmp(*this);
        operator--();
    
        return tmp;
      }
    
      DeepNodeIter& operator =(difference_type val)
      {
        mIdx  = val;
        mEnd = (mIdx > 10);
    
        return *this;
      }
    
      DeepNodeIter& operator-=(difference_type val)
      {
        mIdx -= val;
        mEnd = (mIdx > 10);
    
        return *this;
      }
    
      difference_type operator (const DeepNodeIter& other) const
      {
        return mIdx   other.mIdx;
      }
    
      difference_type operator-(const DeepNodeIter& other) const
      {
        return mIdx - other.mIdx;
      }
    
      DeepNodeIter operator (difference_type val) const
      {
        auto tmp(*this);
        tmp.mIdx  = val;
        return tmp;
      }
    
      DeepNodeIter operator-(difference_type val) const
      {
        auto tmp(*this);
        tmp.mIdx -= val;
        return tmp;
      }
    
      bool operator==(const DeepNodeIter& iter) const { return iter.mEnd == mEnd; }
    
      bool operator!=(const DeepNodeIter& iter) const { return iter.mEnd != mEnd; }
    
      bool operator<(const DeepNodeIter& iter) const { return iter.mIdx < mIdx; }
    
      bool operator<=(const DeepNodeIter& iter) const { return iter.mIdx <= mIdx; }
    
      bool operator>(const DeepNodeIter& iter) const { return iter.mIdx > mIdx; }

  bool operator>=(const DeepNodeIter& iter) const { return iter.mIdx >= mIdx; }

protected:
  DeepNodeRange* mDeepNodeRange;

  int mIdx;

  bool mEnd;
};

DeepNodeIter operator (DeepNodeIter::difference_type val, DeepNodeIter const& self)
{
  return self   val;
}

DeepNodeIter operator-(DeepNodeIter::difference_type val, DeepNodeIter const& self)
{
  return self   val;
}

static_assert(std::random_access_iterator<DeepNodeIter>);

int main() {
  DeepNodeRange deepNodeRange;

  DeepNodeIter i(deepNodeRange);
  DeepNodeIter j(deepNodeRange);
  std::cout << (i - j) << std::endl;
}
  •  Tags:  
  • c
  • Related