使用cpp STL都不会不知道迭代器，那迭代器到底是什么呢？

在http://www.cplusplus.com 中对迭代器的定义为：An iterator is any object that, pointing to some element in a range of elements (such as an array or a container), has the ability to iterate through the elements of that range using a set of operators (with at least the increment (++<) operators). 即迭代器就是指向一系列元素中的某一个元素，它能通过一系列操作迭代访问其中的元素。另外，需要注意的是cpp中的迭代器虽然绝大多数的本质就是指针，但并不是所有的迭代器都是指针，也有可能是其他形式，并且不保证迭代器具有指针的所有功能，比如input 和 output iterator就是一种单向受限的迭代器，执行--操作没有任何意义。cpp中，根据迭代器实现的不同功能，大体可以把迭代器分为5大类，具体各个类支持什么操作，查看迭代器。

现在重点看看cpp中vector中的迭代器，vector的迭代器是一个random access iterator，即随机访问迭代器，具有指针的所有操作。现在看看sgi源码中关于迭代器的实现(stl 3.3)。首先看看iterator的类型定义：

  typedef _Tp value_type;
  typedef value_type* iterator;
  typedef const value_type* const_iterator; 

其中_Tp是范型参数类型,比如声明vector<int>，则_Tp为int，根据类型定义，很显然vector中的iterator 本质就是一个指针，vector<int>::iterator其实就是int *类型。

看vector的方法begin() 和 end（）

  iterator begin() { return _M_start; }
  const_iterator begin() const { return _M_start; }
  iterator end() { return _M_finish; }
  const_iterator end() const { return _M_finish; }
  

可以看到，begin和end方法直接返回_M_start 和_M_finish，这两个私有属性就是iterator类型，即指针，前者指示。由于vector实现本质就是一个动态数组，_M_start则指示数组第一个元素,而_M_finish则指示数组最后一个元素的下一个单元,注意是下一个元素，因此_M_finish指向的单元不能访问，只是一个哨兵。vector更新时（比如初始化、push_back,pop_back等）都需要不断的维护这两个指针（实际上是3个，还有个_M_end_of_storage用于指示当前已分配内存的最后一个单元），而vector中的很多方法也是需要利用这两个指针的，比如以下方法：

  size_type size() const
    { return size_type(end() - begin()); }
  size_type capacity() const
    { return size_type(_M_end_of_storage - begin()); }
  bool empty() const
    { return begin() == end(); }

我们也可以发现，既然是迭代器指针，那就存在不安全性，有可能越界访问，更有可能所引用的迭代器是失效的，即在返回迭代器后，又对容器进行了修改，而这些都需要用户自己注意，库并没有对这些进行检查。java在这方面会比较好点。

根据以上模拟一个简单的vector（只有push_back 和 pop_back方法），对vector原理会更清楚些：

template <class T> class vector {
	public:
		typedef T value_type;
		typedef size_t size_type;
		typedef ptrdiff_t difference_type;
		typedef value_type* iterator;
		typedef value_type* pointer;
		typedef value_type& reference;
		iterator begin() {
			return M_start;
		}
		iterator end() {
			return M_end;
		}
		size_type size() {
			return size_type(end() - begin());
		}
		size_type capacity() {
			return size_type(end_of_storage-begin());
		}
		bool empty() {
			return begin() == end();
		}
		reference operator[](size_type n) {
			return *(begin() + n);
		}
		vector() {
			M_start = M_end = end_of_storage = 0;
		}
		vector(size_type n) {
			M_start = new T[n]();
			M_end = M_start;
			end_of_storage = M_start + n;
		}
		~vector() {
			destroy(begin(), end());
			delete[] M_start;
		}
		void push_back(value_type i) {
			if (M_end < end_of_storage) {
				*M_end++ = i;
				return;
			}
			size_type old_capacity = capacity();
			size_type new_capacity = old_capacity == 0 ? 16 : old_capacity << 1;
			iterator new_M_start = new T[new_capacity]();
			iterator new_M_end = new_M_start;
			iterator iter;
			for(iter = begin(); iter != end(); ++iter) {
				*new_M_end++ = *iter;
			}
			delete [] M_start;
			M_start = new_M_start;
			M_end = new_M_end;
			end_of_storage = M_start + new_capacity;
			*M_end++ = i;
		}
		void pop_back() {
			if (begin() == end())
				return;
			--M_end;
			destroy(M_end);
		}
	private:
		iterator M_start;
		iterator M_end;
		iterator end_of_storage;
		void destroy(pointer p) {
			p->~T();
		}
		void destroy(iterator start, iterator end)
		{
			iterator iter;
			for (iter = start; iter != end; iter++)
			{
				iter->~T();
			}
		}
};

分配内存时按照原有内存2倍关系分配，即如果当前分配了8B, 则下次分配16B，这样能够减少频繁内存分配，提高性能。可以不难看出，在访问元素时，无论是用迭代器还是[ ]运算符，都没有进行越界检测。

看看java的迭代器,主要是看看与cpp中vector迭代器的不同。

java支持迭代，必须实现Iterator接口，该接口定义为：

public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove();
}

该接口只有三个方法，实现该接口必须实现这三个方法。 下面看看ArrayList如何实现该接口，从而了解其原理。 ArrayList 的iterator方法：

public Iterator<E> iterator() {
            return Itr();
        }

看来只好再看看ArrayList的基类 AbstractList,可以发现其实 Itr是AbstractList的私有内部类，其实现为：

private class Itr implements Iterator<E> {
        /**
         * Index of element to be returned by subsequent call to next.
         */
        int cursor = 0;

        /**
         * Index of element returned by most recent call to next or
         * previous.  Reset to -1 if this element is deleted by a call
         * to remove.
         */
        int lastRet = -1;

        /**
         * The modCount value that the iterator believes that the backing
         * List should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size();
        }

        public E next() {
		/* 检查列表是否被修改过 */
            checkForComodification();
            try {
                int i = cursor;
                E next = get(i);
                lastRet = i;
                cursor = i + 1;
                return next;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
		    /* 调用外部类的remove方法 */
                AbstractList.this.remove(lastRet);
                if (lastRet < cursor)
                    cursor--;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException e) {
                throw new ConcurrentModificationException();
            }
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

我们发现java中的迭代器是通过实现Iterator接口实现的，为了方便访问内部属性，一般声明为一个实现Iterator的内部类，因为内部类能够访问外部类的所有属性和方法。而实现方法也很简单，就是用一个cursor游标标识当前位置。我们也发现，java中迭代器比cpp中迭代器更安全，首先能够保证不会越界访问，另外还会检查是否原来的实例被修改过，即保证迭代器是有效的。

• 相关文章
• 全局相关文章