How to correctly implement custom iterators and const iterators

Question

I have a custom container class for which I d like to write the iterator and const iterator classes   I never did this before and I failed to find an appropriate how-to  What are the guidelines regarding iterator creation  and what should I be aware of    I d also like to avoid code duplication  I feel that const iterator and iterator share many things  should one subclass the other      Foot note  I m pretty sure Boost has something to ease this but I can t use it here  for many stupid reasons

User · Answer

I don t know if Boost has anything that would help   My preferred pattern is simple  take a template argument which is equal to value type  either const qualified or not  If necessary  also a node type  Then  well  everything kind of falls into place   Just remember to parameterize  template-ize  everything that needs to be  including the copy constructor and operator    For the most part  the semantics of const will create correct behavior   template lt  class ValueType  class NodeType  gt  struct my iterator    std  iterator lt  std  bidirectional iterator tag  T  gt        ValueType  amp operator      return cur- gt payload         template lt  class VT2  class NT2  gt      friend bool operator             my iterator const  amp lhs  my iterator lt  VT2  NT2  gt  const  amp rhs            etc   private      NodeType  cur       friend class my container      my iterator  NodeType         private constructor for begin  end     typedef my iterator lt  T  my node lt  T  gt   gt  iterator  typedef my iterator lt  T const  my node lt  T  gt  const  gt  const iterator

User · Answer

Check this below code  it works  define MAX BYTE RANGE 255  template  lt typename T gt  class string   public      typedef char  pointer      typedef const char  const pointer      typedef   gnu cxx    normal iterator lt pointer  string gt  iterator      typedef   gnu cxx    normal iterator lt const pointer  string gt  const iterator       string     length 0                  size t size   const               return length            void operator  const pointer value                if  value    nullptr              throw std  invalid argument  quot value cannot be null quot            auto count   strlen value           if  count  gt  0               M copy value  count             void operator  const string  amp value                if  value length    0               M copy value buf  value length             iterator begin                 return iterator buf             iterator end                 return iterator buf   length             const iterator begin   const               return const iterator buf             const iterator end   const               return const iterator buf   length             const pointer c str   const               return buf             string                private      unsigned char length      T buf MAX BYTE RANGE        void  M copy const pointer value  size t count                memcpy buf  value  count           length   count

User · Answer

Choose type of iterator which fits your container  input  output  forward etc  Use base iterator classes from standard library  For example  std  iterator with random access iterator tag These base classes define all type definitions required by STL and do other work  To avoid code duplication iterator class should be a template class and be parametrized by  value type    pointer type    reference type  or all of them  depends on implementation   For example      iterator class is parametrized by pointer type template  lt typename PointerType gt  class MyIterator          iterator class definition goes here     typedef MyIterator lt int  gt  iterator type  typedef MyIterator lt const int  gt  const iterator type    Notice iterator type and const iterator type type definitions  they are types for your non-const and const iterators    See Also  standard library reference  EDIT  std  iterator is deprecated since C  17  See a relating discussion here

User · Answer

Boost has something to help  the Boost Iterator library   More precisely this page  boost  iterator adaptor   What s very interesting is the Tutorial Example which shows a complete implementation  from scratch  for a custom type    template  lt class Value gt  class node iter     public boost  iterator adaptor lt          node iter lt Value gt                    Derived         Value                              Base         boost  use default                 Value         boost  forward traversal tag       CategoryOrTraversal      gt     private      struct enabler         a private type avoids misuse   public      node iter           node iter  iterator adaptor  0          explicit node iter Value  p          node iter  iterator adaptor  p             iterator convertible to const iterator  not vice-versa     template  lt class OtherValue gt      node iter          node iter lt OtherValue gt  const amp  other         typename boost  enable if lt              boost  is convertible lt OtherValue  Value  gt              enabler          gt   type   enabler                 node iter  iterator adaptor  other base         private      friend class boost  iterator core access      void increment     this- gt base reference     this- gt base  - gt next            The main point  as has been cited already  is to use a single template implementation and typedef it

User · Answer

They often forget that iterator must convert to const iterator but not the other way around  Here is a way to do that   template lt class T  class Tag   void gt  class IntrusiveSlistIterator      public std  iterator lt std  forward iterator tag  T gt        typedef SlistNode lt Tag gt  Node      Node  node    public      IntrusiveSlistIterator Node  node        T amp  operator    const      T  operator- gt    const       IntrusiveSlistIterator amp  operator          IntrusiveSlistIterator operator   int        friend bool operator   IntrusiveSlistIterator a  IntrusiveSlistIterator b       friend bool operator   IntrusiveSlistIterator a  IntrusiveSlistIterator b           one way conversion  iterator - gt  const iterator     operator IntrusiveSlistIterator lt T const  Tag gt    const       In the above notice how IntrusiveSlistIterator lt T gt  converts to IntrusiveSlistIterator lt T const gt   If T is already const this conversion never gets used

User · Answer

I m going to show you how you can easily define iterators for your custom containers  but just in case I have created a c  11 library that allows you to easily create custom iterators with custom behavior for any type of container  contiguous or non-contiguous   You can find it on Github  Here are the simple steps to creating and using custom iterators    Create your  custom iterator  class  Define typedefs in your  custom container  class    e g  typedef blRawIterator lt  Type  gt   iterator  e g  typedef blRawIterator lt  const Type  gt   const iterator   Define  begin  and  end  functions   e g  iterator begin   return iterator  amp m data 0      e g  const iterator cbegin  const return const iterator  amp m data 0       We re Done      Finally  onto defining our custom iterator classes   NOTE  When defining custom iterators  we derive from the standard iterator categories to let STL algorithms know the type of iterator we ve made   In this example  I define a random access iterator and a reverse random access iterator      -------------------------------------------------------------------    Raw iterator with random access   ------------------------------------------------------------------- template lt typename blDataType gt  class blRawIterator   public       using iterator category   std  random access iterator tag      using value type   blDataType      using difference type   std  ptrdiff t      using pointer   blDataType       using reference   blDataType amp    public       blRawIterator blDataType  ptr   nullptr  m ptr   ptr       blRawIterator const blRawIterator lt blDataType gt  amp  rawIterator    default       blRawIterator          blRawIterator lt blDataType gt  amp                   operator  const blRawIterator lt blDataType gt  amp  rawIterator    default      blRawIterator lt blDataType gt  amp                   operator  blDataType  ptr  m ptr   ptr return   this         operator                                    bool  const               if m ptr              return true          else             return false             bool                                        operator   const blRawIterator lt blDataType gt  amp  rawIterator const return  m ptr    rawIterator getConstPtr          bool                                        operator   const blRawIterator lt blDataType gt  amp  rawIterator const return  m ptr    rawIterator getConstPtr           blRawIterator lt blDataType gt  amp                   operator   const difference type amp  movement  m ptr    movement return   this        blRawIterator lt blDataType gt  amp                   operator-  const difference type amp  movement  m ptr -  movement return   this        blRawIterator lt blDataType gt  amp                   operator       m ptr return   this        blRawIterator lt blDataType gt  amp                   operator--   --m ptr return   this        blRawIterator lt blDataType gt                    operator   int  auto temp  this    m ptr return temp       blRawIterator lt blDataType gt                    operator-- int  auto temp  this  --m ptr return temp       blRawIterator lt blDataType gt                    operator  const difference type amp  movement  auto oldPtr   m ptr m ptr  movement auto temp  this  m ptr   oldPtr return temp       blRawIterator lt blDataType gt                    operator- const difference type amp  movement  auto oldPtr   m ptr m ptr- movement auto temp  this  m ptr   oldPtr return temp        difference type                             operator- const blRawIterator lt blDataType gt  amp  rawIterator  return std  distance rawIterator getPtr   this- gt getPtr           blDataType amp                                  operator    return  m ptr       const blDataType amp                            operator   const return  m ptr       blDataType                                  operator- gt    return m ptr        blDataType                                  getPtr  const return m ptr       const blDataType                            getConstPtr  const return m ptr    protected       blDataType                                  m ptr       -------------------------------------------------------------------    -------------------------------------------------------------------    Raw reverse iterator with random access   ------------------------------------------------------------------- template lt typename blDataType gt  class blRawReverseIterator   public blRawIterator lt blDataType gt    public       blRawReverseIterator blDataType  ptr   nullptr  blRawIterator lt blDataType gt  ptr        blRawReverseIterator const blRawIterator lt blDataType gt  amp  rawIterator  this- gt m ptr   rawIterator getPtr         blRawReverseIterator const blRawReverseIterator lt blDataType gt  amp  rawReverseIterator    default       blRawReverseIterator          blRawReverseIterator lt blDataType gt  amp            operator  const blRawReverseIterator lt blDataType gt  amp  rawReverseIterator    default      blRawReverseIterator lt blDataType gt  amp            operator  const blRawIterator lt blDataType gt  amp  rawIterator  this- gt m ptr   rawIterator getPtr   return   this        blRawReverseIterator lt blDataType gt  amp            operator  blDataType  ptr  this- gt setPtr ptr  return   this         blRawReverseIterator lt blDataType gt  amp            operator   const difference type amp  movement  this- gt m ptr -  movement return   this        blRawReverseIterator lt blDataType gt  amp            operator-  const difference type amp  movement  this- gt m ptr    movement return   this        blRawReverseIterator lt blDataType gt  amp            operator     --this- gt m ptr return   this        blRawReverseIterator lt blDataType gt  amp            operator--     this- gt m ptr return   this        blRawReverseIterator lt blDataType gt             operator   int  auto temp  this  --this- gt m ptr return temp       blRawReverseIterator lt blDataType gt             operator-- int  auto temp  this    this- gt m ptr return temp       blRawReverseIterator lt blDataType gt             operator  const int amp  movement  auto oldPtr   this- gt m ptr this- gt m ptr- movement auto temp  this  this- gt m ptr   oldPtr return temp       blRawReverseIterator lt blDataType gt             operator- const int amp  movement  auto oldPtr   this- gt m ptr this- gt m ptr  movement auto temp  this  this- gt m ptr   oldPtr return temp        difference type                             operator- const blRawReverseIterator lt blDataType gt  amp  rawReverseIterator  return std  distance this- gt getPtr   rawReverseIterator getPtr           blRawIterator lt blDataType gt                    base   blRawIterator lt blDataType gt  forwardIterator this- gt m ptr     forwardIterator  return forwardIterator        -------------------------------------------------------------------    Now somewhere in your custom container class   template lt typename blDataType gt  class blCustomContainer   public     The typedefs      typedef blRawIterator lt blDataType gt               iterator      typedef blRawIterator lt const blDataType gt         const iterator       typedef blRawReverseIterator lt blDataType gt        reverse iterator      typedef blRawReverseIterator lt const blDataType gt  const reverse iterator                                                                                              public      The begin end functions      iterator                                       begin   return iterator  amp m data 0         iterator                                       end   return iterator  amp m data m size          const iterator                                 cbegin   return const iterator  amp m data 0         const iterator                                 cend   return const iterator  amp m data m size          reverse iterator                               rbegin   return reverse iterator  amp m data m size - 1         reverse iterator                               rend   return reverse iterator  amp m data -1          const reverse iterator                         crbegin   return const reverse iterator  amp m data m size - 1         const reverse iterator                         crend   return const reverse iterator  amp m data -1                                                                                                       This is the pointer to the        beginning of the data        This allows the container        to either  view  data owned        by other containers or to        own its own data        You would implement a  create         method for owning the data        and a  wrap  method for viewing        data owned by other containers      blDataType                                     m data

User · Answer

There are plenty of good answers but I created a template header I use that is quite concise and easy to use   To add an iterator to your class it is only necessary to write a small class to represent the state of the iterator with 7 small functions  of which 2 are optional    include  lt iostream gt   include  lt vector gt   include  iterator tpl h   struct myClass     std  vector lt float gt  vec        Add some sane typedefs for STL compliance    STL TYPEDEFS float      struct it state       int pos      inline void begin const myClass  ref    pos   0        inline void next const myClass  ref      pos        inline void end const myClass  ref    pos   ref- gt vec size          inline float amp  get myClass  ref    return ref- gt vec pos         inline bool cmp const it state amp  s  const   return pos    s pos            Optional to allow operator--   and reverse iterators      inline void prev const myClass  ref    --pos           Optional to allow  const iterator       inline const float amp  get const myClass  ref  const   return ref- gt vec pos               Declare typedef     iterator   begin   and end   functions    SETUP ITERATORS myClass  float amp   it state        Declare typedef     reverse iterator   rbegin   and rend   functions    SETUP REVERSE ITERATORS myClass  float amp   it state        Then you can use it as you would expect from an STL iterator   int main       myClass c1    c1 vec push back 1 0     c1 vec push back 2 0     c1 vec push back 3 0      std  cout  lt  lt   iterator    lt  lt  std  endl    for  float amp  val   c1        std  cout  lt  lt  val  lt  lt          1 0 2 0 3 0        std  cout  lt  lt   reverse iterator    lt  lt  std  endl    for  auto it   c1 rbegin    it    c1 rend      it        std  cout  lt  lt   it  lt  lt          3 0 2 0 1 0         I hope it helps

[c++] How to correctly implement custom iterators and const_iterators?

Examples related to c++

Examples related to iterator

Examples related to const-iterator