How to implement an STL-style iterator and avoid common pitfalls

Question

I made a collection for which I want to provide an STL-style  random-access iterator  I was searching around for an example implementation of an iterator but I didn t find any  I know about the need for const overloads of    and   operators  What are the requirements for an iterator to be  STL-style  and what are some other pitfalls to avoid  if any    Additional context  This is for a library and I don t want to introduce any dependency on it unless I really need to  I write my own collection to be able to provide binary compatibility between C  03 and C  11 with the same compiler  so no STL which would probably break

User · Answer

And now a keys iterator for range-based for loop.

template<typename C>
class keys_it
{
    typename C::const_iterator it_;
public:
    using key_type        = typename C::key_type;
    using pointer         = typename C::key_type*;
    using difference_type = std::ptrdiff_t;

    keys_it(const typename C::const_iterator & it) : it_(it) {}

    keys_it         operator++(int               ) /* postfix */ { return it_++         ; }
    keys_it&        operator++(                  ) /*  prefix */ { ++it_; return *this  ; }
    const key_type& operator* (                  ) const         { return it_->first    ; }
    const key_type& operator->(                  ) const         { return it_->first    ; }
    keys_it         operator+ (difference_type v ) const         { return it_ + v       ; }
    bool            operator==(const keys_it& rhs) const         { return it_ == rhs.it_; }
    bool            operator!=(const keys_it& rhs) const         { return it_ != rhs.it_; }
};

template<typename C>
class keys_impl
{
    const C & c;
public:
    keys_impl(const C & container) : c(container) {}
    const keys_it<C> begin() const { return keys_it<C>(std::begin(c)); }
    const keys_it<C> end  () const { return keys_it<C>(std::end  (c)); }
};

template<typename C>
keys_impl<C> keys(const C & container) { return keys_impl<C>(container); }

Usage:

std::map<std::string,int> my_map;
// fill my_map
for (const std::string & k : keys(my_map))
{
    // do things
}

That's what i was looking for. But nobody had it, it seems.

You get my OCD code alignment as a bonus.

As an exercise, write your own for values(my_map)

User · Answer

First of all you can look here for a list of the various operations the individual iterator types need to support   Next  when you have made your iterator class you need to either specialize std  iterator traits for it and provide some necessary typedefs  like iterator category or value type  or alternatively derive it from std  iterator  which defines the needed typedefs for you and can therefore be used with the default std  iterator traits   disclaimer  I know some people don t like cplusplus com that much  but they provide some really useful information on this

User · Answer

Here is sample of raw pointer iterator   You shouldn t use iterator class to work with raw pointers    include  lt iostream gt   include  lt vector gt   include  lt list gt   include  lt iterator gt   include  lt assert h gt   template lt typename T gt  class ptr iterator       public std  iterator lt std  forward iterator tag  T gt        typedef ptr iterator lt T gt   iterator      pointer pos   public      ptr iterator     pos  nullptr         ptr iterator T  v    pos  v          ptr iterator           iterator  operator   int     postfix              return pos           iterator amp  operator           prefix                 pos   return  this        reference operator     const                      return  pos         pointer   operator- gt    const                      return pos         iterator  operator   difference type v    const   return pos    v        bool      operator   const iterator amp  rhs  const   return pos     rhs pos         bool      operator   const iterator amp  rhs  const   return pos     rhs pos         template lt typename T gt  ptr iterator lt T gt  begin T  val    return ptr iterator lt T gt  val       template lt typename T  typename Tsize gt  ptr iterator lt T gt  end T  val  Tsize size    return ptr iterator lt T gt  val    size      Raw pointer range based loop workaround  Please  correct me  if there is better way to make range based loop from raw pointer   template lt typename T gt  class ptr range       T  begin       T  end   public      ptr range T  ptr  size t length    begin  ptr   end  ptr   length    assert begin   lt   end          T  begin   const   return begin         T  end   const   return end         template lt typename T gt  ptr range lt T gt  range T  ptr  size t length    return ptr range lt T gt  ptr  length       And simple test  void DoIteratorTest         const static size t size   10      uint8 t  data   new uint8 t size                    Only for iterator test         uint8 t n    0           auto first   begin data           auto last   end data  size           for  auto it   first  it    last    it                         it   n                          It s prefer to use the following way          for  const auto amp  n   range data  size                         std  cout  lt  lt    char     lt  lt  static cast lt char gt  n   lt  lt  std  endl                                   Only for iterator test         ptr iterator lt uint8 t gt  first data           ptr iterator lt uint8 t gt  last first   size           std  vector lt uint8 t gt  v1 first  last               It s prefer to use the following way          std  vector lt uint8 t gt  v2 data  data   size                       std  list lt std  vector lt uint8 t gt  gt  queue           queue  emplace back begin data   end data  size            queue  emplace back data  data   size

User · Answer

http   www cplusplus com reference std iterator  has a handy chart that details the specs of    24 2 2 of the C  11 standard   Basically  the iterators have tags that describe the valid operations  and the tags have a hierarchy   Below is purely symbolic  these classes don t actually exist as such   iterator       iterator const iterator amp         iterator        iterator amp  operator  const iterator amp        iterator amp  operator        prefix increment     reference operator    const      friend void swap iterator amp  lhs  iterator amp  rhs     C  11 I think     input iterator   public virtual iterator       iterator operator   int     postfix increment     value type operator    const      pointer operator- gt    const      friend bool operator   const iterator amp   const iterator amp        friend bool operator   const iterator amp   const iterator amp          once an input iterator has been dereferenced  it is    undefined to dereference one before that   output iterator   public virtual iterator       reference operator    const      iterator operator   int     postfix increment      dereferences may only be on the left side of an assignment   once an output iterator has been dereferenced  it is    undefined to dereference one before that   forward iterator   input iterator  output iterator       forward iterator         multiple passes allowed  bidirectional iterator   forward iterator       iterator amp  operator--      prefix decrement     iterator operator-- int     postfix decrement     random access iterator   bidirectional iterator       friend bool operator lt  const iterator amp   const iterator amp        friend bool operator gt  const iterator amp   const iterator amp        friend bool operator lt   const iterator amp   const iterator amp        friend bool operator gt   const iterator amp   const iterator amp         iterator amp  operator   size type       friend iterator operator  const iterator amp   size type       friend iterator operator  size type  const iterator amp        iterator amp  operator-  size type         friend iterator operator- const iterator amp   size type       friend difference type operator- iterator  iterator        reference operator   size type  const      contiguous iterator   random access iterator     C  17      elements are stored contiguously in memory    You can either specialize std  iterator traits lt youriterator gt   or put the same typedefs in the iterator itself  or inherit from std  iterator  which has these typedefs    I prefer the second option  to avoid changing things in the std namespace  and for readability  but most people inherit from std  iterator   struct std  iterator traits lt youriterator gt                typedef      difference type    almost always ptrdiff t     typedef      value type    almost always T     typedef      reference    almost always T amp  or const T amp      typedef      pointer    almost always T  or const T      typedef      iterator category     usually std  forward iterator tag or similar      Note the iterator category should be one of std  input iterator tag  std  output iterator tag  std  forward iterator tag  std  bidirectional iterator tag  or std  random access iterator tag  depending on which requirements your iterator satisfies   Depending on your iterator  you may choose to specialize std  next  std  prev  std  advance  and std  distance as well  but this is rarely needed   In extremely rare cases you may wish to specialize std  begin and std  end   Your container should probably also have a const iterator  which is a  possibly mutable  iterator to constant data that is similar to your iterator except it should be implicitly constructable from a iterator and users should be unable to modify the data   It is common for its internal pointer to be a pointer to non-constant data  and have iterator inherit from const iterator so as to minimize code duplication   My post at Writing your own STL Container has a more complete container iterator prototype

User · Answer

Thomas Becker wrote a useful article on the subject here   There was also this  perhaps simpler  approach that appeared previously on SO  How to correctly implement custom iterators and const iterators

User · Answer

I was trying to solve the problem of being able to iterate over several different text arrays all of which are stored within a memory resident database that is a large struct   The following was worked out using Visual Studio 2017 Community Edition on an MFC test application  I am including this as an example as this posting was one of several that I ran across that provided some help yet were still insufficient for my needs   The struct containing the memory resident data looked something like the following  I have removed most of the elements for the sake of brevity and have also not included the Preprocessor defines used  the SDK in use is for C as well as C   and is old    What I was interested in doing is having iterators for the various WCHAR two dimensional arrays which contained text strings for mnemonics   typedef struct  tagUNINTRAM          stuff deleted         WCHAR   ParaTransMnemo MAX TRANSM NO  PARA TRANSMNEMO LEN      prog  20        WCHAR   ParaLeadThru MAX LEAD NO  PARA LEADTHRU LEN        prog  21        WCHAR   ParaReportName MAX REPO NO  PARA REPORTNAME LEN        prog  22        WCHAR   ParaSpeMnemo MAX SPEM NO  PARA SPEMNEMO LEN        prog  23        WCHAR   ParaPCIF MAX PCIF SIZE                 prog  39        WCHAR   ParaAdjMnemo MAX ADJM NO  PARA ADJMNEMO LEN        prog  46        WCHAR   ParaPrtModi MAX PRTMODI NO  PARA PRTMODI LEN       prog  47        WCHAR   ParaMajorDEPT MAX MDEPT NO  PARA MAJORDEPT LEN         prog  48                stuff deleted   UNINIRAM    The current approach is to use a template to define a proxy class for each of the arrays and then to have a single iterator class that can be used to iterate over a particular array by using a proxy object representing the array   A copy of the memory resident data is stored in an object that handles reading and writing the memory resident data from to disk  This class  CFilePara contains the templated proxy class  MnemonicIteratorDimSize and the sub class from which is it is derived  MnemonicIteratorDimSizeBase  and the iterator class  MnemonicIterator   The created proxy object is attached to an iterator object which accesses the necessary information through an interface described by a base class from which all of the proxy classes are derived  The result is to have a single type of iterator class which can be used with several different proxy classes because the different proxy classes all expose the same interface  the interface of the proxy base class   The first thing was to create a set of identifiers which would be provided to a class factory to generate the specific proxy object for that type of mnemonic  These identifiers are used as part of the user interface to identify the particular provisioning data the user is interested in seeing and possibly modifying   const static DWORD PTR dwId TransactionMnemonic   1  const static DWORD PTR dwId ReportMnemonic   2  const static DWORD PTR dwId SpecialMnemonic   3  const static DWORD PTR dwId LeadThroughMnemonic   4    The Proxy Class  The templated proxy class and its base class are as follows  I needed to accommodate several different kinds of wchar t text string arrays  The two dimensional arrays had different numbers of mnemonics  depending on the type  purpose  of the mnemonic and the different types of mnemonics were of different maximum lengths  varying between five text characters and twenty text characters  Templates for the derived proxy class was a natural fit with the template requiring the maximum number of characters in each mnemonic  After the proxy object is created  we then use the SetRange   method to specify the actual mnemonic array and its range      proxy object which represents a particular subsection of the    memory resident database each of which is an array of wchar t    text arrays though the number of array elements may vary  class MnemonicIteratorDimSizeBase       DWORD PTR  m Type   public      MnemonicIteratorDimSizeBase DWORD PTR x          virtual  MnemonicIteratorDimSizeBase            virtual wchar t  begin     0      virtual wchar t  end     0      virtual wchar t  get int i    0      virtual int ItemSize     0      virtual int ItemCount     0       virtual DWORD PTR ItemType     return m Type        template  lt size t sDimSize gt  class MnemonicIteratorDimSize   public MnemonicIteratorDimSizeBase       wchar t      m begin  sDimSize       wchar t      m end  sDimSize    public      MnemonicIteratorDimSize DWORD PTR x    MnemonicIteratorDimSizeBase x   m begin 0   m end 0          virtual  MnemonicIteratorDimSize            virtual wchar t  begin     return m begin 0         virtual wchar t  end     return m end 0         virtual wchar t  get int i    return m begin i          virtual int ItemSize     return sDimSize        virtual int ItemCount     return m end - m begin         void SetRange wchar t   begin  sDimSize   wchar t   end  sDimSize             m begin   begin  m end   end              The Iterator Class  The iterator class itself is as follows  This class provides just basic forward iterator functionality which is all that is needed at this time  However I expect that this will change or be extended when I need something additional from it    class MnemonicIterator   private      MnemonicIteratorDimSizeBase    m p      we do not own this pointer  we just use it to access current item      int      m index                        zero based index of item      wchar t   m item                        value to be returned   public      MnemonicIterator MnemonicIteratorDimSizeBase  p    m p p           MnemonicIterator               a ranged for needs begin   and end   to determine the range         the range is up to but not including what end   returns      MnemonicIterator  amp  begin     m item   m p- gt get m index   0   return  this                       begining of range of values for ranged for  first item     MnemonicIterator  amp  end     m item   m p- gt get m index   m p- gt ItemCount     return  this          end of range of values for ranged for  item after last item      MnemonicIterator  amp  operator         m item   m p- gt get   m index   return  this                  prefix increment    p     MnemonicIterator  amp  operator     int i    m item   m p- gt get m index     return  this             postfix increment  p       bool operator     MnemonicIterator  amp p    return   this     p                                    minimum logical operator is not equal to     wchar t   operator     const   return m item                                                    dereference iterator to get what is pointed to      The proxy object factory determines which object to created based on the mnemonic identifier  The proxy object is created and the pointer returned is the standard base class type so as to have a uniform interface regardless of which of the different mnemonic sections are being accessed  The SetRange   method is used to specify to the proxy object the specific array elements the proxy represents and the range of the array elements   CFilePara  MnemonicIteratorDimSizeBase   CFilePara  MakeIterator DWORD PTR x        CFilePara  MnemonicIteratorDimSizeBase   mi   nullptr       switch  x        case dwId TransactionMnemonic                        CFilePara  MnemonicIteratorDimSize lt PARA TRANSMNEMO LEN gt   mk   new CFilePara  MnemonicIteratorDimSize lt PARA TRANSMNEMO LEN gt  x               mk- gt SetRange  amp m Para ParaTransMnemo 0    amp m Para ParaTransMnemo MAX TRANSM NO                mi   mk                    break      case dwId ReportMnemonic                        CFilePara  MnemonicIteratorDimSize lt PARA REPORTNAME LEN gt   mk   new CFilePara  MnemonicIteratorDimSize lt PARA REPORTNAME LEN gt  x               mk- gt SetRange  amp m Para ParaReportName 0    amp m Para ParaReportName MAX REPO NO                mi   mk                    break      case dwId SpecialMnemonic                        CFilePara  MnemonicIteratorDimSize lt PARA SPEMNEMO LEN gt   mk   new CFilePara  MnemonicIteratorDimSize lt PARA SPEMNEMO LEN gt  x               mk- gt SetRange  amp m Para ParaSpeMnemo 0    amp m Para ParaSpeMnemo MAX SPEM NO                mi   mk                    break      case dwId LeadThroughMnemonic                        CFilePara  MnemonicIteratorDimSize lt PARA LEADTHRU LEN gt   mk   new CFilePara  MnemonicIteratorDimSize lt PARA LEADTHRU LEN gt  x               mk- gt SetRange  amp m Para ParaLeadThru 0    amp m Para ParaLeadThru MAX LEAD NO                mi   mk                    break             return mi      Using the Proxy Class and Iterator  The proxy class and its iterator are used as shown in the following loop to fill in a CListCtrl object with a list of mnemonics  I am using std  unique ptr so that when the proxy class i not longer needed and the std  unique ptr goes out of scope  the memory will be cleaned up   What this source code does is to create a proxy object for the array within the struct which corresponds to the specified mnemonic identifier  It then creates an iterator for that object  uses a ranged for to fill in the CListCtrl control and then cleans up  These are all raw wchar t text strings which may be exactly the number of array elements so we copy the string into a temporary buffer in order to ensure that the text is zero terminated       std  unique ptr lt CFilePara  MnemonicIteratorDimSizeBase gt  pObj pFile- gt MakeIterator m IteratorType        CFilePara  MnemonicIterator pIter pObj get         provide the raw pointer to the iterator who doesn t own it       int i   0        CListCtrl index for zero based position to insert mnemonic      for  auto x   pIter                WCHAR szText 32      0           Temporary buffer           wcsncpy s szText  32  x  pObj- gt ItemSize             m mnemonicList InsertItem i  szText    i

User · Answer

I was am in the same boat as you for different reasons  partly educational  partly constraints   I had to re-write all the containers of the standard library and the containers had to conform to the standard  That means  if I swap out my container with the stl version  the code would work the same  Which also meant that I had to re-write the iterators    Anyway  I looked at EASTL  Apart from learning a ton about containers that I never learned all this time using the stl containers or through my undergraduate courses  The main reason is that EASTL is more readable than the stl counterpart  I found this is simply because of the lack of all the macros and straight forward coding style   There are some icky things in there  like  ifdefs for exceptions  but nothing to overwhelm you   As others mentioned  look at cplusplus com s reference on iterators and containers

User · Answer

The iterator facade documentation from Boost Iterator provides what looks like a nice tutorial on implementing iterators for a linked list   Could you use that as a starting point for building a random-access iterator over your container   If nothing else  you can take a look at the member functions and typedefs provided by iterator facade and use it as a starting point for building your own

[c++] How to implement an STL-style iterator and avoid common pitfalls?

Examples related to c++

Examples related to iterator

Examples related to const-iterator