Generic Random Access Iterator

• Download GenericCPPLib.zip - 30.4 KB
• Download source from GitHub

Introduction

Implementing some sequence-of-objects user type, which should be used with the standart templated algorithms or C++11 range-based loops, requiring your type to support its own iterators, making it iterable.

Background

C++ iterator concept is well described here - this information can help you to better understand the provided code.

Descripton

Generic Random Access Iterator (GRAI) is a complete iterator type:

Random-access iterators are iterators that can be used to access (AND modify if 'Constant' is false)
  elements at an arbitrary offset position relative to the element they point to,
    offering the same functionality as pointers (to constants if 'Constant' is true)

The key features of this class (as they are described in the header module):

1) functionality (bidirectional + random access)
2) safety (the ONLY way to invalidate an iterator is to destroy the related container object)
3) versatility (CAN provide mutable/read-only access AND switch direction/container at the real time)
4) commonality (CAN be used with the multiple container types which satisfies the requirements)

One thing i think i should mention more detail: when using the STL container's iterators it is vital to understand why & where your iterator can be invalidated (using invalid iterator is a fast and perfect way to meet the undefined behaviour which in fact leads to such nice things like access violation error / general protection fault / segmentation fault). Considering you have a view years experience using C++, i'm sure you know how it feels.

Fortunately, the situations where iterator invalidation can possibly occur is well described, for example using std::vector::insert can lead to it:

If a reallocation happens, all iterators, pointers and references related to the container are invalidated.
Otherwise, only those pointing to position and beyond are invalidated, with all iterators, pointers and references to elements before position guaranteed to keep referring to the same elements they were referring to before the call.

My iterator class is based upon using a subscript operator of the handled sequence, always examing the sequence actual length before acessing the required element, ensuring that no operation upon container can invalidate the related iterator. That determines both strengths and weaknesses (and, of course, the requirments to the user type):

'TContainerType' should support the following properties, fileds AND methods:
'value_type', 'operator[]()', 'size()', 'empty()'

Using an indexing operator obviously assuming user type handling the contiguous sequence (like std::vector or std::string, for example) or at least provides an affective indexation routine (like std::deque or QT QList).

The very imprtant thing is that (according to the Random Access Iterator Concept) a RandomAccessIterator is a BidirectionalIterator that can be moved to point to any element in constant time. Through the iterator itself is moving its internal position in the constant time:

GenericRAIterator& operator+=(const difference_type shift) throw() {
  setPos(getShiftedPos(shift)); // updated pos.
  return *this;
}
// ...
void setPos(const decltype(pos_) pos = 0) throw() {
  pos_ = pos;
}
// ...
auto getShiftedPos(const difference_type shift = 0U) const throw() -> decltype(pos_) {
  return pos_ + (reversed_ ? -shift : shift);
}

while dereferencing an iterator, the controlled sequence can provide access to the element by index in (for example) linear time (like std::list) so, obviously, dereferecing will have a linear time too:

TMutableValueType& operator*() const throw() {
  return at(pos()); // curr. pos
}

TMutableValueType& at(const decltype(pos_) pos = pos_) const throw() {
  static TMutableValueType DUMMY; // will be zeroised (default created) as a static

  if (container()) {
    #pragma warning(disable: 4018) // signed/unsigned mismatch: 'pos > containerPtr->size()'
    if (pos < 0 || pos > container()->size()) {
      return DUMMY; // attempt to dereference a before-begin OR past-the-end iterato
    }
    #pragma warning(default: 4018)
    return (*container())[pos];
  }
  return DUMMY; // attempt to dereference an unlinked (singular) iterator
}

Also, the size() and empty() routines of the user type should of course have a constant O(1) complexity, through i really hope there is no such implementations, which have a polynomial complexity of this operations, at least in the observable universe.

GRAI traits:

1) dereferenceable (even in 'past-the-end', 'before-begin' OR singular/invalidated state, returning ref. to the mock obj. in those cases)
2) incrementable
3) swappable: meet the requirements of 'MoveAssignable' and 'MoveConstructible'

(MoveAssignable, MoveConstructible)

GRAI template options:

template <typename TContainerType, class TContainerElemType,
          const bool Reversed = false, const bool Constant = true>

Reversed is used to create a reversed iterators to support the standart routines:

rbegin

Return reverse iterator to reverse beginning (public member function )

rend

Return reverse iterator to reverse end (public member function )

Constant used to create a none-mutable iterators for

cbegin 

Return const_iterator to beginning (public member function )

cend 

Return const_iterator to end (public member function )

Both of them used to support the following functions:

crbegin 

Return const_reverse_iterator to reverse beginning (public member function )

crend 

Return const_reverse_iterator to reverse end (public member function )

Pay attention that the template class instantiated wit the diffirent params creates diffirent classes, so the <span style="background-color: rgb(255, 255, 255);">const_reverse_iterator</span> is a complitely different type for the compiler then the standart (direct and mutable) iterator type (through we can switch the actual direction at the real time).

Impementation details

Switching input / output mode of working is implemented by using a simple type helper:

typedef typename AddRemoveConst<TContainerType, Constant>::Type TMutableContainerType;
typedef typename AddRemoveConst<value_type, Constant>::Type TMutableValueType;

operator-> of an iterator should return a pointer to the current element of the adjusted sequence, but in fact we can not simply take an address of object using operator& as it can be overloaded. Through i hope it is a very rare situation, std::addressof (also here) is used to resolve this problem.

The interesting thing to mention is a comparison strategy:

template <const bool OtherReversed, const bool OtherConstant, const EComparisonType ComparisonType>
bool compare(const GenericRAIterator<TContainerType, value_type, OtherReversed, OtherConstant>& iter,
             const bool checkType = false) const throw()
{
  // constexpr ('returnValBasedOnEq' AND 'isEq')??
  auto returnValBasedOnEq = [&](const bool isEq) throw() { // ONLY if SHOULD NOT do actual compare
    switch (ComparisonType) {
      case EComparisonType::EQ:
      case EComparisonType::LESS_OR_EQ:
      case EComparisonType::GREATER_OR_EQ:
        return isEq;

      case EComparisonType::LESS:
      case EComparisonType::GREATER:
        return false;
    }
    return !isEq; // '!='
  };
    
  if (this == &iter) return returnValBasedOnEq(true); // same instance
    
  // Diff. type iters are diff. even if they linked to the same sequence [CAN NOT be comparable]
  if (checkType && reversed() != iter.reversed()) return returnValBasedOnEq(false);
    
  if (container() != iter.container())
    return returnValBasedOnEq(false); // diff. containers (diff. domains)
  if (!container()) return returnValBasedOnEq(true); // both a NONE-iterators (unlinked)
    
  // 'std::vector::end' - if the container is empty, this function returns the same as vector::begin
  // For an empty container 'begin' == 'end' AND so let the 'rbegin' == 'rend'
  //  AND ALL other iters are the same
  if (container()->empty()) return returnValBasedOnEq(true);
    
  const auto thisPosType = posType();
  if (EIterPosType::IPT_NORMAL == thisPosType) {
    auto thisPos = pos(), otherPos = iter.pos();
    if (reversed()) std::swap(thisPos, otherPos);
    return Compare<ComparisonType>()(thisPos, otherPos); // comparing absolute pos.
  }
  // Past-the-end OR before-begin: comparing relative pos.
  return Compare<ComparisonType>()(thisPosType, iter.posType());
}

Relational operators use this strategy to do the actual work:

template <const bool OtherReversed, const bool OtherConstant>
bool operator==(const GenericRAIterator<TContainerType, value_type,
                                        OtherReversed, OtherConstant>& iter) const throw() {
  return compare<OtherReversed, OtherConstant, EComparisonType::EQ>(iter);
}
  
template <const bool OtherReversed, const bool OtherConstant>
bool operator!=(const GenericRAIterator<TContainerType, value_type,
                                        OtherReversed, OtherConstant>& iter) const throw() {
  return !(*this == iter); // invoke 'operator==(const GenericRAIterator&)'
}
  
template <const bool OtherReversed, const bool OtherConstant>
bool operator<(const GenericRAIterator<TContainerType, value_type,
                                       OtherReversed, OtherConstant>& iter) const throw() {
  return compare<OtherReversed, OtherConstant, EComparisonType::LESS>(iter);
}
  
template <const bool OtherReversed, const bool OtherConstant>
bool operator>(const GenericRAIterator<TContainerType, value_type,
                                       OtherReversed, OtherConstant>& iter) const throw() {
  return compare<OtherReversed, OtherConstant, EComparisonType::GREATER>(iter);
}
  
template <const bool OtherReversed, const bool OtherConstant>
bool operator<=(const GenericRAIterator<TContainerType, value_type,
                                        OtherReversed, OtherConstant>& iter) const throw() {
  return compare<OtherReversed, OtherConstant, EComparisonType::LESS_OR_EQ>(iter);
}
  
template <const bool OtherReversed, const bool OtherConstant>
bool operator>=(const GenericRAIterator<TContainerType, value_type,
                                        OtherReversed, OtherConstant>& iter) const throw() {
  return compare<OtherReversed, OtherConstant, EComparisonType::GREATER_OR_EQ>(iter);
}

The strategy itself uses Compare functor from the CompareUtils module:

enum EComparisonType {
  EQ,
  NOT_EQ,
  LESS,
  GREATER,
  LESS_OR_EQ,
  GREATER_OR_EQ
};

template <const EComparisonType>
// Functor
struct Compare {};

template<>
struct Compare<EComparisonType::EQ> {
  template <typename T, class U>
  bool operator()(const T& first, const U& second) throw() {
    return first == second;
  }
};

template<>
struct Compare<EComparisonType::NOT_EQ> {
  template <typename T, class U>
  bool operator()(const T& first, const U& second) throw() {
    return first != second;
  }
};

template<>
struct Compare<EComparisonType::LESS> {
  template <typename T, class U>
  bool operator()(const T& first, const U& second) throw() {
    return first < second;
  }
};

template<>
struct Compare<EComparisonType::LESS_OR_EQ> {
  template <typename T, class U>
  bool operator()(const T& first, const U& second) throw() {
    return first <= second;
  }
};

template<>
struct Compare<EComparisonType::GREATER> {
  template <typename T, class U>
  bool operator()(const T& first, const U& second) throw() {
    return first > second;
  }
};

template<>
struct Compare<EComparisonType::GREATER_OR_EQ> {
  template <typename T, class U>
  bool operator()(const T& first, const U& second) throw() {
    return first >= second;
  }
};

One special moment about relational operators you should know and understand:

(that is another dark corner of our beloved C++, yeah baby)

Note that for the types that are both 'EqualityComparable' AND 'LessThanComparable',
 the C++ standard library makes a distinction between
  'equality', which is the value of the expression 'a == b' AND
   'equivalence', which is the value of the expression '!(a < b) && !(b < a)'

(EqualityComparable, LessThanComparable)

Also, all past-the-end (PE) and before-begin (BB) iterators are considered equal for an empty conainer (i. e., as an empty container can't have 'normal' iterators - only 'PP' and 'BB', all iterators adjusted to the empty conainer are considered equal). This picture will help you to understand the concept:

An iterator object is capable to switch the adjusted container instance at the real time:

// Called with NO data provided will partially invalidate the iterator - 
//  partially invalid iterator will be left in the valid, BUT unlinked state
// Also resets pos.
void linkToTheContainer(TMutableContainerType* const container = nullptr) throw() {
  setContainer(container);
  reset();
}

Also, it can reverse it's own direction during execution regardless of the initial 'Reversed' template option:

void reverse() throw() {
  reversed_ = !reversed_;
}

And of course all operations upon an iterator instance is NOT thread safe.

Complete code is too long to pass it here, but you can always find it (with all the comments) in the GitHub repository.

Test code

For Ideone online compiler:

// <Include the code from TypeHelpers, CompareUtils and GenericRAIterator>

#include <cstring>
#include <iostream>

int main() {
    struct MyStr {
      MyStr(const char* str) throw() {
        if(str) {
          strcpy(buf, str);
          len = strlen(buf);
        }
      }
      
      char& operator[](const size_t idx) throw() {
        static char C = '\0';
        return idx >= len ? C : buf[idx];
      }
      
      const char& operator[](const size_t idx) const throw() {
        static const char C = '\0';
        return idx >= len ? C : buf[idx];
      }
      
      size_t size() const throw() {
        return len;
      }
      
      bool empty() const throw() {
        return !len;
      }
      
      size_t len = 0U;
      
      typedef char value_type;
      value_type buf[256U];
      
      typedef GenericRAIterator<MyStr, value_type, false, true> const_iterator;
      typedef GenericRAIterator<MyStr, value_type, true, true> const_reverse_iterator;
      
      const_iterator begin() const throw() {
        return std::move(const_iterator(this));
      }
      
      const_iterator end() const throw() {
        const_iterator iter(this);
        return std::move(iter += size()); // to past-the-end pos.
      }
      
      const_reverse_iterator rbegin() const throw() {
        return std::move(const_reverse_iterator(this, true));
      }
      
      const_reverse_iterator rend() const throw() {
        const_reverse_iterator iter(this, true);
        return std::move(iter += size()); // to before-begin pos.
      }
    } myStr = "we don't need no water!";
    
    for(const auto c : myStr) {
      std::cout << c;
    }
    std::cout << std::endl;
    
    auto iter = myStr.rbegin();
    const auto end = myStr.rend();
    for(; iter != end; ++iter) {
      std::cout << *iter;
    }
    return 0;
}

Output:

we don't need no water!
!retaw on deen t'nod ew

Points of Interest

Class using TypeHelpers module.

This module is just a small part of the library, which uses C++11 features and which I am working under now, I decided to make it a public property.

History