c++ - 我正在尝试为我的 DynamicArray 类创建一个迭代器。为什么 STL 排序不适用于我的迭代器？

Question

我已经创建了一个 DynamicArray 类并为它实现了一个迭代器。我的一个 .cpp 文件采用 n 长度的 DynamicArray 填充随机值，并且应该使用 STL 排序对其进行排序。但是，我已经修修补补了几个小时，每当尝试使用 begin() 和 end() 作为参数运行排序时，总是会遇到此错误:

no type named 'value_type' in 'struct std::iterator_traits<DynamicArray<double>::iterator>'

我将提供我的 DynamicArray 原型(prototype)以供引用:

template<class T>
class DynamicArray {
public:
  static T dummy;
  class iterator { // iterator for begin() and end() functions
  private:
    T* ptr;
  public:
    iterator() { ptr = NULL; } // constructor, sets pointer to NULL
    iterator( T* p ) { ptr = p; } // parameterized constructor, sets pointer to data in DynamicArray
    const T& operator*() const { return *ptr; } // pointer operator, returns pointer
    void operator++() { if( ptr ) ptr++; } // pre-increment operator, increments pointer
    void operator++( int ) { if( ptr ) ptr++; } // post-increment operator, increments pointer
    bool operator!=( const iterator & other ) { return ptr != other.ptr; } // does not equal operator
  };
private:
  T* data;
  bool* inUse;
  unsigned int size;
  unsigned int capacity;
public:
  DynamicArray();
  DynamicArray( const DynamicArray<T> & );
  virtual ~DynamicArray();
  DynamicArray<T> & operator=( const DynamicArray<T> & );
  T operator[]( unsigned int index ) const;
  T& operator[]( unsigned int index );
  unsigned int getSize() const;
  unsigned int getCapacity() const;
  bool containsKey( unsigned int index ) const;
  void deleteKey( unsigned int index );
  iterator begin() const { return iterator( data ); }
  iterator end() const { return iterator( data + size ); }
  vector<unsigned int> keys() const;
  void clear();
private:
  void copy( const DynamicArray<T> & );
  void deleteIt();
  void setCapacity( unsigned int newCap = 10 );
};

这个错误是什么意思？我该如何解决？提前致谢。

Answer 1

您的迭代器不满足迭代器的 C++ 库要求。这不像简单地命名一个东西那么容易 iterator , 为了创建一个迭代器。在 C++ 标准中，对迭代器的要求超过 30 页。

几乎在所有情况下，实现自定义迭代器的最简单方法是继承 std::iterator模板。该模板采用两个必需参数和三个可选参数，以合成自定义迭代器的所有必需属性。

简要查看您的迭代器代码，在我看来您几乎可以支持前向迭代器的要求，因此请尝试从 std::iterator<std::forward_iterator_tag,T> 继承您的迭代器类.

我之所以说“差不多”是因为你的 operator++运营商坏了。他们的返回值是错误的，后自增版本也是错误的。这可能会阻止您的迭代器使用 C++ 库中的某些算法正常工作，直到您修复此问题。但是您最大的问题是缺乏所需迭代器特征的实现。