我正在尝试为我的DynamicArray类创建一个迭代器。为什么STL排序不能与我的迭代器一起工作？

Question

我已经创建了一个DynamicArray类，并为它实现了一个迭代器。我的一个.cpp文件接受一个长度为n的DynamicArray，其中填充了随机值，并且应该使用STL DynamicArray对其进行排序。然而，我已经修补了几个小时，每次尝试使用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++库中的某些算法正常工作，直到您修复此问题为止。但是您最大的问题是缺少所需迭代器特征的实现。