当前头文件是迭代器库(Containers library)的部分内容。

迭代器库(参考手册) ​迭代器库(标准)

  • 迭代器原语

    iterator_traits 为查询迭代器信息提供了统一的接口(Interface)
    input_iterator_tag 这是一个空类,表明迭代器类型为输入迭代器,是一个标签类型(Tag type)
    output_iterator_tag 这是一个空类,表明迭代器类型为输出迭代器,是一个标签类型
    forward_iterator_tag 这是一个空类,表明迭代器类型为正向迭代器,是一个标签类型
    bidirectional_iterator_tag 这是一个空类,表明迭代器类型为双向迭代器,是一个标签类型
    random_access_iterator_tag 这是一个空类,表明迭代器类型为随机访问迭代器,是一个标签类型
    iterator 迭代器类型的基类

    迭代器适配器

    reverse_iterator 用于逆序遍历的迭代器适配器(Adaptor)
    move_iterator C++11 用于解引用(Dereference)到一个右值引用(Rvalue reference)的迭代器适配器
    back_insert_iterator 用于在容器末尾插入元素的迭代器适配器
    front_insert_iterator 用于在容器开头插入元素的迭代器适配器
    insert_iterator 用于在容器任意位置插入元素的迭代器适配器

    流迭代器

    istream_iterator 用于从 basic_istream 中读取数据的输入(Input)迭代器
    ostream_iterator 用于写入数据到 basic_ostream 的输出(Output)迭代器
    istreambuf_iterator 用于从 basic_streambuf 中读取数据的输入迭代器
    ostreambuf_iterator 用于写入数据到 basic_streambuf 的输出迭代器
  • 迭代器适配器

    make_move_iterator C++11 创建一个 move_iterator
    back_inserter 创建一个 back_insert
    front_inserter 创建一个 front_insert_iterator
    inserter 创建一个 insert_iterator

    迭代器操作

    advance 以指定距离向前移动(Advance)一个迭代器
    distance 返回两个迭代器之间的距离
    next C++11 递增一个迭代器
    prev C++11 递减一个迭代器

    范围访问

    begin C++11 返回指向容器起始位置的迭代器(iterator)
    cbegin C++14 返回指向容器起始位置的常迭代器(const_iterator)
    end C++11 返回指向容器末尾位置的迭代器
    cend C++14 返回指向容器末尾位置的常迭代器
    rbegin C++14 返回指向容器逆序起始位置的逆序迭代器(reverse_iterator)
    crbegin C++14 返回指向容器逆序起始位置的常逆序迭代器(const_reverse_iterator)
    rend C++14 返回指向容器逆序末尾位置的逆序迭代器
    crend C++14 返回指向容器逆序末尾位置的常逆序迭代器

    非成员操作

    operator==
    operator!=
    operator<
    operator<=
    operator>
    operator>=
    比较两个底层迭代器
    operator+ 向前移动迭代器
    operator- 计算两个迭代器适配器之间的距离
    operator==
    operator!=
    operator<
    operator<=
    operator>
    operator>=
    比较两个底层(逆序)迭代器
    operator+ 向前移动(逆序)迭代器
    operator- 计算两个(逆序)迭代器适配器之间的距离
    operator==
    operator!=
    比较两个输入流迭代器
    operator==
    operator!=
    比较两个输入流缓存迭代器
  • namespace std {
        // primitives:
        template<class Iterator> struct iterator_traits;
        template<class T> struct iterator_traits<T*>;
        template<class Category, class T, class Distance = ptrdiff_t,
        class Pointer = T*, class Reference = T&> struct iterator;
     
        struct input_iterator_tag { };
        struct output_iterator_tag { };
        struct forward_iterator_tag: public input_iterator_tag { };
        struct bidirectional_iterator_tag: public forward_iterator_tag { };
        struct random_access_iterator_tag: public bidirectional_iterator_tag { };
     
        // iterator operations:
        template <class InputIterator, class Distance>
            void advance(InputIterator& i, Distance n);
        template <class InputIterator>
            typename iterator_traits<InputIterator>::difference_type
            distance(InputIterator first, InputIterator last);
        template <class ForwardIterator>
            ForwardIterator next(ForwardIterator x,
                typename std::iterator_traits<ForwardIterator>::difference_type n = 1);
        template <class BidirectionalIterator>
            BidirectionalIterator prev(BidirectionalIterator x,
                typename std::iterator_traits<BidirectionalIterator>::difference_type n = 1);
     
        // predefined iterators:
        template <class Iterator> class reverse_iterator;
     
        template <class Iterator1, class Iterator2>
            bool operator==(
                const reverse_iterator<Iterator1>& x,
                const reverse_iterator<Iterator2>& y);
        template <class Iterator1, class Iterator2>
            bool operator<(
                const reverse_iterator<Iterator1>& x,
                const reverse_iterator<Iterator2>& y);
        template <class Iterator1, class Iterator2>
            bool operator!=(
                const reverse_iterator<Iterator1>& x,
                const reverse_iterator<Iterator2>& y);
        template <class Iterator1, class Iterator2>
            bool operator>(
                const reverse_iterator<Iterator1>& x,
                const reverse_iterator<Iterator2>& y);
        template <class Iterator1, class Iterator2>
            bool operator>=(
                const reverse_iterator<Iterator1>& x,
                const reverse_iterator<Iterator2>& y);
        template <class Iterator1, class Iterator2>
            bool operator<=(
                const reverse_iterator<Iterator1>& x,
                const reverse_iterator<Iterator2>& y);
     
        template <class Iterator1, class Iterator2>
            auto operator-(
                const reverse_iterator<Iterator1>& x,
                const reverse_iterator<Iterator2>& y) ->decltype(y.base() - x.base());
        template <class Iterator>
            reverse_iterator<Iterator>
            operator+(
                typename reverse_iterator<Iterator>::difference_type n,
                const reverse_iterator<Iterator>& x);
     
        template <class Container> class back_insert_iterator;
        template <class Container>
            back_insert_iterator<Container> back_inserter(Container& x);
     
        template <class Container> class front_insert_iterator;
        template <class Container>
            front_insert_iterator<Container> front_inserter(Container& x);
     
        template <class Container> class insert_iterator;
        template <class Container>
            insert_iterator<Container> inserter(Container& x, typename Container::iterator i);
     
        template <class Iterator> class move_iterator;
        template <class Iterator1, class Iterator2>
            bool operator==(
                const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
        template <class Iterator1, class Iterator2>
            bool operator!=(
                const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
        template <class Iterator1, class Iterator2>
            bool operator<(
                const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
        template <class Iterator1, class Iterator2>
            bool operator<=(
                const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
        template <class Iterator1, class Iterator2>
            bool operator>(
                const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
        template <class Iterator1, class Iterator2>
            bool operator>=(
                const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
     
        template <class Iterator1, class Iterator2>
            auto operator-(
                const move_iterator<Iterator1>& x,
                const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base());
        template <class Iterator>
            move_iterator<Iterator> operator+(
                typename move_iterator<Iterator>::difference_type n, 
                const move_iterator<Iterator>& x);
        template <class Iterator>
            move_iterator<Iterator> make_move_iterator(const Iterator& i);
     
        // stream iterators:
        template <class T, class charT = char, class traits = char_traits<charT>,
                class Distance = ptrdiff_t>
            class istream_iterator;
        template <class T, class charT, class traits, class Distance>
            bool operator==(const istream_iterator<T,charT,traits,Distance>& x,
                const istream_iterator<T,charT,traits,Distance>& y);
        template <class T, class charT, class traits, class Distance>
            bool operator!=(const istream_iterator<T,charT,traits,Distance>& x,
                const istream_iterator<T,charT,traits,Distance>& y);
     
        template <class T, class charT = char, class traits = char_traits<charT> >
            class ostream_iterator;
     
        template<class charT, class traits = char_traits<charT> >
            class istreambuf_iterator;
        template <class charT, class traits>
            bool operator==(const istreambuf_iterator<charT,traits>& a,
                const istreambuf_iterator<charT,traits>& b);
        template <class charT, class traits>
            bool operator!=(const istreambuf_iterator<charT,traits>& a,
                const istreambuf_iterator<charT,traits>& b);
     
        template <class charT, class traits = char_traits<charT> >
            class ostreambuf_iterator;
     
        // range access:
        template <class C> auto begin(C& c) -> decltype(c.begin());
        template <class C> auto begin(const C& c) -> decltype(c.begin());
        template <class C> auto end(C& c) -> decltype(c.end());
        template <class C> auto end(const C& c) -> decltype(c.end());
        template <class T, size_t N> T* begin(T (&array)[N]);
        template <class T, size_t N> T* end(T (&array)[N]);
    }
  • template<class Iterator> struct iterator_traits {
        typedef typename Iterator::difference_type      difference_type;
        typedef typename Iterator::value_type           value_type;
        typedef typename Iterator::pointer              pointer;
        typedef typename Iterator::reference            reference;
        typedef typename Iterator::iterator_category    iterator_category;
    };
     
    template<class T> struct iterator_traits<T*> {
        typedef ptrdiff_t                   difference_type;
        typedef T                           value_type;
        typedef T*                          pointer;
        typedef T&                          reference;
        typedef random_access_iterator_tag  iterator_category;
    };
     
    template<class T> struct iterator_traits<const T*> {
        typedef ptrdiff_t                   difference_type;
        typedef T                           value_type;
        typedef const T*                    pointer;
        typedef const T&                    reference;
        typedef random_access_iterator_tag  iterator_category;
    };
  • 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;
    };
  • struct input_iterator_tag { };
    struct output_iterator_tag { };
    struct forward_iterator_tag: public input_iterator_tag { };
    struct bidirectional_iterator_tag: public forward_iterator_tag { };
    struct random_access_iterator_tag: public bidirectional_iterator_tag { };
  • template <class Iterator>
    class reverse_iterator : public
        iterator<typename iterator_traits<Iterator>::iterator_category,
        typename iterator_traits<Iterator>::value_type,
        typename iterator_traits<Iterator>::difference_type,
        typename iterator_traits<Iterator>::pointer,
        typename iterator_traits<Iterator>::reference> {
    public:
        typedef Iterator                                            iterator_type;
        typedef typename iterator_traits<Iterator>::difference_type difference_type;
        typedef typename iterator_traits<Iterator>::reference       reference;
        typedef typename iterator_traits<Iterator>::pointer         pointer;
     
        reverse_iterator();
        explicit reverse_iterator(Iterator x);
        template <class U> reverse_iterator(const reverse_iterator<U>& u);
        template <class U> reverse_iterator& operator=(const reverse_iterator<U>& u);
     
        Iterator base() const; // explicit
        reference operator*() const;
        pointer operator->() const;
     
        reverse_iterator& operator++();
        reverse_iterator  operator++(int);
        reverse_iterator& operator--();
        reverse_iterator  operator--(int);
     
        reverse_iterator  operator+ (difference_type n) const;
        reverse_iterator& operator+=(difference_type n);
        reverse_iterator  operator- (difference_type n) const;
        reverse_iterator& operator-=(difference_type n);
     
        /*unspecified*/ operator[](difference_type n) const;
    protected:
        Iterator current;
    private:
        Iterator deref_tmp; // exposition only
    };
  • template <class Container>
    class back_insert_iterator :
        public iterator<output_iterator_tag,void,void,void,void> {
    protected:
        Container* container;
    public:
        typedef Container container_type;
     
        explicit back_insert_iterator(Container& x);
        back_insert_iterator<Container>&
            operator=(const typename Container::value_type& value);
        back_insert_iterator<Container>&
            operator=(typename Container::value_type&& value);
     
        back_insert_iterator<Container>& operator*();
        back_insert_iterator<Container>& operator++();
        back_insert_iterator<Container>  operator++(int);
    };
  • template <class Container>
    class front_insert_iterator :
        public iterator<output_iterator_tag,void,void,void,void> {
    protected:
        Container* container;
    public:
        typedef Container container_type;
     
        explicit front_insert_iterator(Container& x);
        front_insert_iterator<Container>&
        operator=(const typename Container::value_type& value);
        front_insert_iterator<Container>&
        operator=(typename Container::value_type&& value);
     
        front_insert_iterator<Container>& operator*();
        front_insert_iterator<Container>& operator++();
        front_insert_iterator<Container>  operator++(int);
    };
  • template <class Container>
    class insert_iterator :
        public iterator<output_iterator_tag,void,void,void,void> {
    protected:
        Container*                   container;
        typename Container::iterator iter;
    public:
        typedef Container container_type;
     
        insert_iterator(Container& x, typename Container::iterator i);
        insert_iterator<Container>&
        operator=(const typename Container::value_type& value);
        insert_iterator<Container>&
        operator=(typename Container::value_type&& value);
     
        insert_iterator<Container>& operator*();
        insert_iterator<Container>& operator++();
        insert_iterator<Container>& operator++(int);
    };
  • template <class Iterator>
    class move_iterator {
    public:
        typedef Iterator                                            iterator_type;
        typedef typename iterator_traits<Iterator>::difference_type difference_type;
        typedef Iterator                                            pointer;
        typedef typename iterator_traits<Iterator>::value_type      value_type;
        typedef typename iterator_traits<Iterator>::iterator_category
                                                                    iterator_category;
        typedef value_type&&                                        reference;
     
        move_iterator();
        explicit move_iterator(Iterator i);
        template <class U> move_iterator(const move_iterator<U>& u);
        template <class U> move_iterator& operator=(const move_iterator<U>& u);
     
        iterator_type base() const;
        reference operator*() const;
        pointer operator->() const;
     
        move_iterator& operator++();
        move_iterator  operator++(int);
        move_iterator& operator--();
        move_iterator  operator--(int);
     
        move_iterator   operator+(difference_type n) const;
        move_iterator&  operator+=(difference_type n);
        move_iterator   operator-(difference_type n) const;
        move_iterator&  operator-=(difference_type n);
        /*unspecified*/ operator[](difference_type n) const;
     
    private:
        Iterator current; // exposition only
    };