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

Question

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

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

我将提供我的 DynamicArray 原型以供参考：

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++ 库中的某些算法正常工作，直到您解决此问题。但是你最大的问题是缺乏所需的迭代器特征的实现。