迭代器中使用的模式

Question

我熟悉C++ STL迭代器的用法,例如

for(map<pair<int,int>>::iterator it=m.begin(); it!=m.end(); ++it)
  int  a = it->first;
  int b = it->second;

但我不知道其中的内在细节.有人可以向我解释一下吗？无论是C++,Java,C#还是Python.

Answer 1

在C++中,迭代器进入容器类似于指向数组的指针(我假设你熟悉指针).有迭代器的不同的口味,但最后它们指代元件的容器(通过解引用运营商内的只是一种方法*和->)和横切于容器中的元素.

重要的部分不是实施,而是概念.您不需要知道如何实现列表或向量中的迭代器(或者在许多情况下它们之间的区别),只需知道它提供的操作.迭代器进入不同的容器将有不同的实现(对于一个列表,它将跟随next节点中的一些指针,对于一个映射,它将跟随平衡树的right子或parent指针.事实上,迭代器可以以不同的方式实现到同一容器中(并且一些编译器对任何给定的容器都有多个实现),具体取决于编译标志或模式.但重要的是,你真的不关心它们是什么,只是它们允许你做什么.

举个简单的例子,在g ++中,STL实现std::vector包含三个指针,如:

//...
class vector {
   T * _b;  // beginning of allocated memory
   T * _e;  // one past the last inserted element 
   T * _c;  // one past the end of the allocated memory
//...
}

这样size() = (_e - _b) / sizeof(T)和capacity = (_c - _b) / sizeof(T).使用vector的这个实现,您可以使用原始指针作为迭代器:

//...
class vector {
public:
   typedef T* iterator;
   T* begin() { return _b; }
   T* end() { return _e; }
//...
}

但是你也可以构建更复杂(更慢但更安全)的迭代器实现,比如在迭代器失效时将触发断言的已检查迭代器(此代码仅为了示例目的而过于简化):

template <typename T>
class checked_iterator {
public:
   checked_iterator( std::vector<T> & v, std::size_t e )
      : _check_begin(v._b), _vector(v), _pos( v._b + e )
   {}
   T& operator*() {
      assert( _check_begin == _vector._b && "Dereferencing an invalidated iterator");
      return *_pos; 
   }
   // ...
private:
   T * _pos;
   T const * const _check_begin;
   std::vector<T>& _vector;
};

此迭代器实现将检测取消引用无效迭代器(仅在整个向量重定位的情况下,但通过存储更多数据,它可以执行完整检查)并将在仍在开发中时中止不正确的程序的执行.从用户的角度来看,它将是一个简单的RandomAccessIterator(它应该是,这是矢量迭代器的要求)但在幕后它将提供一种识别其他难以检测的错误的机制.

这是VS编译器中的方法:在调试模式下(并且取决于编译器标志),它将使用缓慢安全的迭代器,这将有助于通过无效的迭代器检测访问(对于向量,只要将元素添加到向量中,迭代器就会失效)容器).同时,更改编译器标志可以获得生产系统更快的普通原始指针实现,但调试无效迭代器使用会更加困难.

在Java和C#中,它们实际上是实现一些简单操作的对象(在Java中hasNext(),next()并且remove())允许横向整个容器隐藏容器的实现方式.它们非常相似,其意图是从用户代码封装在特定容器上执行的操作.

一个重要的区别是,在这两种情况下,您都可以使用它们迭代整个容器,但在c ++中它们是可比较的,您可以将任意两个迭代器迭代到同一个容器中.例如,在包含城市电话簿的地图中,您可以使用操作将迭代器放入以ac开头的第一个名称,并使用另一个搜索来获取名称以"d"开头的第一个元素(假设名称排序)并且您可以使用任何STL(或您自己的)算法与这两个迭代器一起仅对该子集执行操作.