容器 - vector (2)

上一章：容器 - vector (1)
目录

1，iterator的作用

通过iterator，可以对一个数据体的集合进程遍历访问，而遍历的规则可以有iterator自身行为决定。比如对于连续集合或者列表集合，可以定义为前向遍历或者后向遍历，对于树结构可以进行前序，中序或者后序遍历等。

2， C++ 中的iterator

C++ 中的iterator类型，可以分为如下部分，具体链接C++Reference:

3，vector的iterator

那么对于vector iterator，要实现什么呢？
vector是一个连续存储的数组，在没有iterator的情况下，我们一般通过指针+索引来遍历一个数组。因此对于一个vector iterator，要实现以下几点基本功能：

（1）增加或者减少，可对比指针的++p或者--p
（2）随机索引，可对比指针的p+n
（3）通用属性，比如访问数据，比较，开始结束等

有了上面3点目标，我们就可以开始着手写代码了，其实就是实现一个Random Access的iterator。

template<typename T>
class MyVector
{
...
public:
    class iterator
    {
        T* p_;
    public:
        iterator() : p_(nullptr){}
        iterator(T*p ) : p_(p) {}
        iterator(const iterator& it) : p_(it.p_) {}
        iterator& operator=(const iterator& it) {p_ = it.p_; return *this;}
        iterator operator++ () {++p_; return p_;}
        iterator operator-- () {--p_; return p_;}
        iterator operator++ (int) {T* p = p_; ++p_; return p;}
        iterator operator-- (int) {T* p = p_; --p_;  return p;}
        bool operator ==(const iterator& it) {return it.p_ == p_;}
        bool operator !=(const iterator& it) {return !(it.p_ == p_);}
        T& operator *() {return *p_;}
        T* operator ->() {return p_;}
    };

    iterator begin() {return iterator(array_);}
    iterator end() {return iterator(array_ + length_);}
};

测试代码如下：

    MyVector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    std::cout << v.size() << v[0]  << v[1] << v[2] << std::endl;
    v.push_back(1);
    std::cout << v.size() << std::endl;
    for (MyVector<int>::iterator it = v.begin(); it != v.end(); ++it)
    {
        std::cout << "it = " << *it << std::endl;
    }

至此，一个基本的vector已经完成。

目录