iterator 的一些特殊用法

C++ 迭代器

字数统计: 846阅读时长: 3 min

 2021/05/19   Share

iterator 的一些特殊用法

本文章基于 VS2019 创作。

std::iterator 这是一个基类模板，可用于从其派生迭代器类。它不是迭代器类，并且不提供迭代器应具有的任何功能。

该基类仅提供了一些构件类型，这实际上是不存在于任何迭代器类型（迭代器类型没有具体的构件的要求）所需的，但由于它们限定所需默认成员，他们可能是有用的，iterator_traits 类模板自动生成适当的实例（并且这样的实例化是必需适用于所有的迭代器类型）。

std::iterator 被定义为：

template <class Category, class T, class Distance = ptrdiff_t, class Pointer = T*, class Reference = T&>
struct iterator {
    typedef T         value_type;		//元素的类型
    typedef Distance  difference_type;	//两个迭代器之间的距离
    typedef Pointer   pointer;			//元素的指针
    typedef Reference reference;		//元素的引用
    typedef Category  iterator_category;//迭代器类型
};

itertor 在 vector const iterator 中的实际运用：

template <class _Myvec>
class _Vector_const_iterator : public _Iterator_base {
public:
#ifdef __cpp_lib_concepts
    using iterator_concept = contiguous_iterator_tag;
#endif // __cpp_lib_concepts
    using iterator_category = random_access_iterator_tag;
    using value_type        = typename _Myvec::value_type;
    using difference_type   = typename _Myvec::difference_type;
    using pointer           = typename _Myvec::const_pointer;
    using reference         = const value_type&;
   	......
};

这五个属性不止在 iterator 中有定义。其中有四个属性在容器中也有定义（除了 iterator_category 其他都有定义）。

template <class _Ty, class _Alloc = allocator<_Ty>>
class vector { // varying size array of values
private:
    ......
    using _Alty_traits = allocator_traits<_Alty>;
    ......
public:
	......
    using value_type      = _Ty;
    using pointer         = typename _Alty_traits::pointer;
    using reference       = _Ty&;
    using difference_type = typename _Alty_traits::difference_type;
	......
};

1 迭代器的种类（iterator_category）

一共有 5 种 iterator_category 分别为：

input_iterator：istream 独有的迭代器。
output_iterator：ostream 独有的迭代器。
forward_iterator：继承自 input_iterator，单向走的迭代器，只能走一个，不能跳。如 forward_list、单向 list 的 hashtable。
bidirectional_iterator：继承自 forward_iterator，双向走的迭代器，只能走一个，不能跳。如 list、 rb-tree、双向 list 的 hashtable。
random_access_iterator：继承自 bidirectional_iterator，可以跳的迭代器。如 array、 vector、 deque。

2 迭代器的萃取机（iterator_traits）

traits 是一个萃取机，萃取各个迭代器的特性。这里所谓的迭代器特性，指的是迭代器的相应类别（iterator_category）。当然，若要这个萃取机 traits 能够有效运作，每一个迭代器必须遵循约定，自行定义出相应类别。这是一个约定，谁不遵守这个约定，谁就不能兼容与 STL 这个大家庭。

在这里插入图片描述

3 iterator 的部分操作

3.1 advance

使迭代器前进 n 位。

源码：

template <class _InIt, class _Diff>
_CONSTEXPR17 void advance(_InIt& _Where, _Diff _Off) { // increment iterator by offset
    if constexpr (_Is_random_iter_v<_InIt>) {
        _Where += _Off;
    }
    else {
        if constexpr (is_signed_v<_Diff>) {
            if constexpr (_Is_bidi_iter_v<_InIt>) {
                for (; _Off < 0; ++_Off) {
                    --_Where;
                }
            }
            else {
                _STL_ASSERT(_Off >= 0, "negative advance of non-bidirectional iterator");
            }
        }

        for (; 0 < _Off; --_Off) {
            ++_Where;
        }
    }
}

示例：

#include <vector>
#include <iostream>
#include <iterator>
using namespace std;
int main() {
	vector<int> a{ 0,1,2,3,4,5 };

	auto it = a.begin();
	cout << *it << endl;
    //第一参数位迭代器，第二参数为前进的位数
	//使迭代器前进 n 位
	advance(it, 5);
	cout << *it << endl;

	advance(it, -3);
	cout << *it << endl;

	return 0;
}

输出：

1
2
3

0
5
2

3.2 distance

计算 begin 和 end 之间的元素数。

示例：

#include <vector>
#include <iostream>
#include <iterator>
using namespace std;
int main() {
	vector<int> a{ 0,1,2,3,4,5 };

	cout << distance(a.begin(), a.end());

	return 0;
}