迭代器分类

C++ STL 中根据移动能力将迭代器分成了 5 类：

Input Iterator 输入迭代器，只支持 operator++ 操作。
Output Iterator 输出迭代器，只支持 operator++ 操作。
Forward Iterator 前向迭代器，只支持 operator++ 操作。
Bidirectional Iterator 双向迭代器，支持 operator-- 和 operator++ 操作。
Random Access Iterator 随机访问迭代器，不仅支持 operator-- 和 operator++ 操作，还可以与整数进行算术运算。

int main()

{

    // 1.输入迭代器, 只能读缓冲区

    // 这样会直接进入读取状态一直读取int, 直到状态出错或遇到EOF

    // 比如输入了非数字, ctrl + d等等

    istream_iterator<int> initer(cin);

    int x = *initer;    // 从缓冲区读取第一个数到变量中

    // 2.输出迭代器, 只能写到某个地方

    ostream_iterator<int> oiter(cout, " ");  // 绑定到标准输出, 分隔符为空格字符串

    vector<int> v{1, 2, 3, 4};

    copy(v.begin(), v.end(), oiter);    // 输出1 2 3 4

    cout << endl;

    // 3.前向迭代器, unordered_xxx系列的关联式容器的迭代器就是这个类型的

    // 大部分能读能写, set 系列由于键值合一, 不能够写

    // map 中 key 不可更改, value 可以

    unordered_map<int, char> m{{1, 'a'}, {2, 'b'}};

    unordered_map<int, char>::iterator mit = m.begin();

    while (mit != m.end()) {

        mit->second = 'c';  // 可以修改 value

        ++mit;              // 不支持 operator--

    }

    // 4.双向迭代器, list 的迭代器就是该类型的

    list<int> l{1, 2, 3};

    list<int>::iterator lit = l.begin();    // 指向 1

    ++lit;  // 指向 2

    --lit;  // 回到 1

    *lit = 666;     // 更改

    // 5.随机访问迭代器, vector 和 deque 的迭代器就是该类型的

    // 例如输出 vecor 的最后一个元素

    vector<int>::iterator vit = v.begin();

    cout << *(vit + v.size() - 1) << endl;  // 支持与整数运算

    return 0;

}

忽略了头文件，自行添加。

编译器多态

C++ STL 中很多算法会根据迭代器参数的类型来选择最优的实现方法，以 advance 为例，它的作用是将给定的迭代器移动指定步数，实现如下：

template<typename InputIterator, typename Distance>

void advance(InputIterator& it, Distance n)

{

    // concept requirements -- taken care of in __advance

    typename iterator_traits<InputIterator>::difference_type d = n;

    std::__advance(i, d, std::__iterator_category(it));

}

可以看到它内部转调了 std::__advance，注意到它的第三个参数 std::__iterator_category(it)。

该方法根据传入的迭代器返回一个迭代器类型对象，一共 5 种，迭代器类型命名类似于 xxx_iterator_tag。

然后std::__advance共有如下版本：

针对输入迭代器的：

template<typename InputIterator, typename Distance>

void __advance(InputIterator& it, Distance n, input_iterator_tag)

{

    while (n--) ++it;

}

针对前向迭代器的：

template<typename InputIterator, typename Distance>

void __advance(InputIterator& it, Distance n, forward_iterator_tag)

{

     __advance(it, n, input_iterator_tag());	// 直接转调

}

针对双向迭代器的：

template<typename InputIterator, typename Distance>

void __advance(InputIterator& it, Distance n, bidirectional_iterator_tag)

{

    // 可以双向移动

    if (n >= 0)

        while (n--) ++it;

    else

        while (n++) --it;

}

针对随机访问迭代器的：

template<typename InputIterator, typename Distance>

void __advance(InputIterator& it, Distance n, random_access_iterator_tag)

{

    it += n;	// 直接加, 跳着走, 爽得一批

}

当我们调用 advance 时，编译器根据第三个参数（迭代器类型）选择最优模板。

巴特西

C++迭代器种类与编译期间多态

迭代器分类

编译器多态

最新文章

热门文章