泛型随机访问迭代器

• 下载 GenericCPPLib.zip - 30.4 KB
• 从GitHub下载源代码

引言

实现某些对象序列用户类型时，需要将其与标准模板算法或C++11 基于范围的循环一起使用，这要求您的类型支持其自己的迭代器，使其成为可迭代的。

背景

C++ 迭代器概念在此处有详细描述——此信息可以帮助您更好地理解所提供的代码。

描述

通用随机访问迭代器（GRAI）是一个完整的迭代器类型

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)

此类的关键特性（如头文件模块中描述的）

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)

有一件事我认为我应该更详细地提及：当使用STL容器的迭代器时，理解为什么以及在何处您的迭代器可能被失效至关重要（使用无效迭代器是遇到未定义行为的快速完美方法，这实际上会导致诸如访问冲突错误 / 一般保护错误 / 分段错误等令人愉快的事情）。考虑到您有几年使用C++的经验，我相信您知道这是什么感觉。

幸运的是，可能发生迭代器失效的情况已被很好地描述，例如使用std::vector::insert可能会导致它

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.

我的迭代器类基于使用所处理序列的下标运算符，在访问所需元素之前总是检查序列的实际长度，确保对容器的任何操作都不会失效相关的迭代器。这决定了它的优点和缺点（当然，还有对用户类型的要求）

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

使用索引运算符显然假设用户类型处理连续序列（例如std::vector或std::string），或者至少提供有效的索引例程（例如std::deque或QT QList）。

非常重要的一点是（根据随机访问迭代器概念），一个RandomAccessIterator是一个BidirectionalIterator，可以在常数时间内移动以指向任何元素。迭代器本身以常数时间移动其内部位置：

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);
}

当解引用迭代器时，受控序列可以以（例如）线性时间（如std::list）提供对元素的按索引访问，因此，显然，解引用也将具有线性时间

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
}

此外，用户类型的size()和empty()例程当然应该具有常数O(1)复杂度，尽管我真的希望没有这样的实现，这些操作具有多项式复杂度，至少在可观测宇宙中。

GRAI 特性

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'

(可移动赋值, 可移动构造)

GRAI 模板选项

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

Reversed 用于创建反向迭代器以支持标准例程

rbegin

返回反向起始迭代器（公共成员函数）

rend

返回反向结束迭代器（公共成员函数）

Constant 用于创建不可变迭代器

cbegin

返回指向开头的const_iterator（公共成员函数）

cend

返回指向末尾的const_iterator（公共成员函数）

两者都用于支持以下函数

crbegin

返回指向反向开头的const_reverse_iterator（公共成员函数）

crend

返回指向反向结尾的const_reverse_iterator（公共成员函数）

请注意，使用不同参数实例化的模板类会创建不同的类，因此对于编译器来说，const_reverse_iterator与标准（直接和可变）迭代器类型是完全不同的类型（尽管我们可以在运行时切换实际方向）。

实现细节

通过使用一个简单的类型帮助器来实现输入/输出工作模式的切换

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

迭代器的operator->应该返回一个指向调整后序列中当前元素的指针，但实际上我们不能简单地使用operator&来获取对象的地址，因为它可能被重载。尽管我希望这种情况非常罕见，但std::addressof（在此处也有提及）用于解决此问题。

值得一提的有趣之处是比较策略

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());
}

关系运算符使用此策略来完成实际工作

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);
}

策略本身使用来自CompareUtils模块的Compare函数对象

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;
  }
};

关于关系运算符，您应该知道并理解一个特殊时刻

（这是我们挚爱的C++的另一个黑暗角落，是的宝贝）

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)'

(可相等比较, 可小于比较)

此外，对于空容器，所有超出末尾（PE）和在开头之前（BB）的迭代器都被认为是相等的（即，由于空容器不能有“正常”迭代器——只有“PE”和“BB”，所以所有调整到空容器的迭代器都被认为是相等的）。这张图片将帮助您理解这个概念

迭代器对象能够在运行时切换调整后的容器实例

// 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();
}

此外，它可以在执行过程中反转自身方向，无论初始的“Reversed”模板选项如何

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

当然，对迭代器实例的所有操作都不是线程安全的。

完整代码太长，无法在此处粘贴，但您始终可以在GitHub 仓库中找到它（包含所有注释）。

测试代码

对于 Ideone 在线编译器：

// <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;
}

输出:

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

关注点

使用TypeHelpers模块的类。

这个模块只是我目前正在开发的使用C++11特性的库的一小部分，我决定将其设为public属性。

历史