浅谈cpp中vector中的迭代器

int32位 posted @ Oct 30, 2013 08:59:19 AM in c/cpp , 2353 阅读
转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!

使用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中迭代器更安全,首先能够保证不会越界访问,另外还会检查是否原来的实例被修改过,即保证迭代器是有效的。

 

转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!
  • 无匹配
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter