Iterator

概念

迭代器是不是一个特定的类型，它实际上是一组对类型的要求。

最基本要求就是从一个端点出发，下一步、下一步地到达另一个端点。

输出容器内容的时候，实际上就对容器的 begin 和 end 成员函数返回的对象类型提出了要求。

假设前者返回的类型是 I，后者返回的类型是 S，这些要求是：

  • I 对象支持 * 操作，解引用取得容器内的某个对象。
  • I 对象支持 ++，指向下一个对象。
  • I 对象可以和 I 或 S 对象进行相等比较，判断是否遍历到特定位置（在 S 的情况下是是否结束了遍历）。

注意在 C++17 之前，begin 和 end 返回的类型 I 和 S 必须是相同的。从 C++17 开始，I 和 S 可以是不同的类型。这带来了更大的灵活性和更多的优化可能性。

基本迭代器的要求：

  • 对象可以被拷贝构造、拷贝赋值和析构。
  • 对象支持 * 运算符。
  • 对象支持前置 ++ 运算符。
img
img

迭代器通常是对象。但需要注意的是，指针可以满足上面所有的迭代器要求，因而也是迭代器。因为本来迭代器就是根据指针的特性，对其进行抽象的结果。vector 的迭代器，在很多实现里就直接是使用指针的。

常用迭代器

顺序容器都定义了嵌套的 iterator 类型和 const_iterator 类型。iterator 可写入，const_iterator 类型不可写入，这些迭代器都被定义为输入迭代器或其派生类型：

  • vector::iterator 和 array::iterator 可以满足到连续迭代器contiguous iterator。
  • deque::iterator 可以满足到随机访问迭代器random-access iterator（内存只有部分连续）。
  • list::iterator 可以满足到双向迭代器bidirectional iterator（链表不能快速跳转）。
  • forward_list::iterator 可以满足到前向迭代器forward iterator（单向链表不能反向遍历）。

输出迭代器 back_inserter 返回的类型 back_inserter_iterator ；可以很方便地在容器的尾部进行插入操作。

ostream_iterator，方便我们把容器内容拷贝到一个输出流。

vector<int> v1 {1, 2, 3, 4};
vector<int> v2;
copy(v1.begin(), v1.end(), back_inserter(v2));
m_print_single(v2); //1 2 3 4
copy(v2.begin(), --v2.end(), ostream_iterator<int>(cout, " ")); //1 2 3

自定义迭代器

C++ 里有些固定的类型要求规范。对于一个迭代器，需要定义下面的类型：

class istream_reader{
    class iterator{
        public:
            // 迭代器之间距离的类型，ptrdiff_t是种标准做法（指针间差值的类型），没什么特别作用
            typedef ptrdiff_t difference_type;
            typedef string value_type;
            typedef const value_type* pointer;
            typedef const value_type& reference;
            // 标识这个迭代器的类型是 input iterator（输入迭代器）
            typedef input_iterator_tag iterator_category;
    };
};

作为只能读一次的输入迭代器，有个特殊的麻烦（前向迭代器或其衍生类型没有）：到底应该让 * 负责读取还是 ++ 负责读取。这里让 ++ 负责读取，* 负责返回读取的内容。这个 iterator 类需要有一个数据成员指向输入流，一个数据成员来存放读取的结果。

class istream_reader{
    class iterator{
        public:
        	// ......
        	// 默认构造将：istream_t清空
            iterator() noexcept:istream_t(nullptr){}
        
			//带参构造：传入输出流设置istream_t
            explicit iterator(istream& _istream_t): istream_t(&_istream_t)
            {
                ++*this;
            }
        
			// 迭代器指向的文本行的引用和指针
            reference operator*() const noexcept
            {
                return str_t;
            }
            pointer operator->() const noexcept
            {
                return &str_t;
            }
			
        	// ++读取输入流
            iterator& operator++() 
            {
                getline(*istream_t, str_t);
                if(!*istream_t){
                    istream_t = nullptr;
                }
                return *this;
            }

            iterator operator++(int)
            {
                iterator it(*this);
                ++*this;
                return it;
            }

        private:
            istream* istream_t;
            string str_t;
    };
};

这里在构造函数里调用了 ++，确保在构造后调用 * 运算符时可以读取内容，符合日常先使用 *、再使用 ++ 的习惯。一旦文件读取到尾部（或出错），则 istream_t被清空，回到默认构造的情况。

迭代器之间的比较主要考虑文件有没有读到尾部的情况。

bool operator==(const iterator& it) const noexcept
{
    return istream_t == it.istream_t;
}

bool operator!=(const iterator& it) const noexcept
{
    return !operator==(it);
}

istream_reader 的定义。

class istream_reader{
public:
    class iterator{
        // ......
    };

    istream_reader() noexcept:istream_t(nullptr){}

    explicit istream_reader(istream& _istream_t) noexcept:istream_t(&_istream_t){}

    iterator begin()
    {
        return iterator(*istream_t);
    }

    iterator end() const noexcept
    {
        return iterator();
    }

private:
    istream* istream_t;
};

测试

for(const string& s : istream_reader(cin)){
    cout << s << endl;
}

目前这个输入迭代器在构造里调用了++，多一次构造就可能读到意料之外的结果。