STL -- Insert Iterator 简单分析

在 Mon 20 July 2015 发布于 STL 分类

【以下代码都来自 SGI STL -- stl_iterator.h】

工作中STL用的很多, 多次用到insert iterator系列函数,但是一直都没有注意过为什么要这么用。只是知道inserter是'插入',front_inserter是'头插',back_inserter是'尾插'。当然这些叫法只是为我自己记住怎么使用这系列的函数。本着知其然知其所以然,本篇文章将简单的分析下Insert Iterator的实现细节。 现看inserter的这个函数的实现吧:

template <class _Container, class _Iterator>
inline
insert_iterator<_Container> inserter(_Container& __x, _Iterator __i)
{
    typedef typename _Container::iterator __iter;
    return insert_iterator<_Container>(__x, __iter(__i));
}

inserter是一个模版函数,模版参数_Container_Iterator一看就知道需要传入的参数肯定是个容器和一个迭代器。但是这不是重点,重点是它的返回值。inserter返回的是 类型为insert_iterator<_Container>的模版迭代器, 它是一个Output Iterator。让我们看看其源码:

template<class _Container>
class insert_iterator {
protected
    _Container* container; //保存的是指针, 不能是值类型
    typename _Container::iterator iter;
public:
    typedef _Container               container_type;
    // 表明这个迭代器是 Output Iterator类型的迭代器
    typedef output_iterator_tag      iterator_category;
    typedef void                     value_type;
    typedef void                     difference_type;
    typedef void                     pointer;
    typedef void                     reference;

    // 容器是按引用传入,但是初始化却是取地址
    insert_iterator(_Container& __x, typename _Container::iterator __i)
        : container(& __x), iter(__i) {}
    // 玩的小把戏,调用_Container的成员函数insert,即在当前位置iter插入,insert函数返回的是插入后,插入元素在该_Container的地址,完成了插入元素的过程
    insert_iterator<_Container>&
    operator=(const typename _Container::value_type& __value) {
        iter = container->insert(iter, __value);
        // 指向下个迭代地址
        ++iter;
        //返回自身
        return *this;
    }
    // 下面这三个操作符重载都返回的是自身, 等会可以看看为什么要这么做
    insert_iterator<_Container>& operator*() {return *this;}
    insert_iterator<_Container>& operator++() {return *this;}
    insert_iterator<_Container>& operator++(int) {return *this;}
}

上面我们知道,因为insert_iteratorOutput Iterator 类型的迭代器,可以用在参数类型为Output Iterator的算法中。我们看看在 cppreference上关于copy的给出其可能的实现:

template<class InputIt, class OutputIt>
OutputIt copy(InputIt first, InputIt last, 
              OutputIt d_first)
{
    while (first != last) {
    //*d_first++就是返回自身
    //执行了重载=运算符号的逻辑
        *d_first++ = *first++;
    }
    return d_first;
}

这个实现的重点在*d_first++ = *first++;, 我想你在看到这行代码的时候肯定应该想到了insert_iterator为什么要那样实现四个运算符号的重载逻辑了吧。况且其类型为Output Iterator的迭代器。可以进行的操作为write only(只可写)。就不难理解为什么这样去实现操作符的重载了。front_inserterback_inserterinserter实现的机制没有什么两样(具体请看源码)。需要注意的是,在使用容器的时候,要清楚知道哪些容器有以下成员函数: insertfront_insert, back_insert