stl_iterator.h

#pragma once

#include <cstddef>  //ptrdiff_t定义
#include <iostream>

namespace MiniSTL {

//五种迭代器类型
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 {};

//为了避免遗忘记录traits，此基类以供自定义iterator继承之
template <class Category, class T, class Distance = ptrdiff_t,
          class Pointer = T *, class Reference = T &>
struct iterator {
    typedef Category iterator_category  ;
    typedef T value_type ;
    typedef Distance difference_type  ;
    typedef Pointer pointer;
    typedef Reference reference;
};

// traits 展现Iterator所有特性
template <class Iterator>
struct iterator_traits {
    typedef typename Iterator::iterator_category iterator_category;
    typedef typename Iterator::value_type value_type;
    typedef typename Iterator::difference_type difference_type;
    typedef typename Iterator::pointer pointer;
    typedef typename Iterator::reference reference;
};

//针对raw pointer设计的偏特化版本
template <class T>
struct iterator_traits<T *> {
    using iterator_category = random_access_iterator_tag;
    using value_type = T;
    using difference_type = ptrdiff_t;
    using pointer = T *;
    using reference = T &;
};

//针对pointer-to-const设计的偏特化版本
template <class T>
struct iterator_traits<const T *> {
    using iterator_category = random_access_iterator_tag;
    using value_type = T;
    using difference_type = ptrdiff_t;
    using pointer = const T *;
    using reference = const T &;
};

//书上这里写了value_type(const Iterator& )函数 返回的是value_type
// 感觉也没什么用 就不写了



//以下是别名 省的写好长的类型名
template <class Iterator>
using iterator_category_t =
    typename iterator_traits<Iterator>::iterator_category;

template <class Iterator>
using value_type_t = typename iterator_traits<Iterator>::value_type;

template <class Iterator>
using difference_type_t = typename iterator_traits<Iterator>::difference_type;

template <class Iterator>
using pointer_t = typename iterator_traits<Iterator>::pointer;

template <class Iterator>
using reference_t = typename iterator_traits<Iterator>::reference;

//以下为整组distance函数
template <class InputIterator>
inline difference_type_t<InputIterator> __distance(InputIterator first,
                                                   InputIterator last,
                                                   input_iterator_tag) {
    difference_type_t<InputIterator> n = 0;
    while (first != last) ++first, ++n;
    return n;
}
// 随机迭代器 可以直接减求距离
template <class InputIterator>
inline difference_type_t<InputIterator> __distance(InputIterator first,
                                                   InputIterator last,
                                                   random_access_iterator_tag) {
    return last - first;
}

// 利用函数重载 编译期就知道该调用哪个具体函数 根据tag
template <class InputIterator>
inline difference_type_t<InputIterator> distance(InputIterator first,
                                                 InputIterator last) {
    return __distance(first, last, iterator_category_t<InputIterator>());
}

//以下为整组advance函数
template <class InputIterator, class Distance>
inline void __advance(InputIterator &i, Distance n, input_iterator_tag) {
    while (n--) ++i;
}

template <class InputIterator, class Distance>
inline void __advance(InputIterator &i, Distance n,
                      bidirectional_iterator_tag) {
    if (n >= 0)
        while (n--) ++i;
    else
        while (n++) --i;
}

template <class InputIterator, class Distance>
inline void __advance(InputIterator &i, Distance n,
                      random_access_iterator_tag) {
    i += n;
}

template <class InputIterator, class Distance>
inline void advance(InputIterator &i, Distance n) {
    __advance(i, n, iterator_category_t<InputIterator>());
}

//以下为三种迭代器适配器
// insert
//reverse
// stream

// insert:back_insert,fornt_insert,insert
template <class Container>
class back_insert_iterator {
protected:
    Container *container;  //底层容器

public:
    using iterator_category = output_iterator_tag;
    using value_tyep = void;
    using difference_type = void;
    using pointer = void;
    using reference = void;

public:
    explicit back_insert_iterator(Container &value) : container(value) {}
    back_insert_iterator &operator=(
        const typename Container::value_type &value) {
        container->push_back(value);  //本质上是调用了push_back
        return *this;
    }

    //以下三个接口对back_insert_iterator无用，关闭功能(为什么不直接设为private？）
    back_insert_iterator operator*() { return *this; }
    back_insert_iterator operator++() { return *this; }
    back_insert_iterator operator++(int) { return *this; }
};

//以下是一个辅助函数，便于快速使用back_insert_iterator
template <class Container>
inline back_insert_iterator<Container> back_inserter(Container &x) {
    return back_insert_iterator<Container>(x);
}

// front_insert_iterator无法用于vector，因为后者不具备push_front
template <class Container>
class front_insert_iterator {
protected:
    Container *container;  //底层容器

public:
    using iterator_category = output_iterator_tag;
    using value_tyep = void;
    using difference_type = void;
    using pointer = void;
    using reference = void;

public:
    explicit front_insert_iterator(Container &value) : container(value) {}
    front_insert_iterator &operator=(
        const typename Container::value_type &value) {
        container->push_front(value);
        return *this;
    }

    //以下三个接口对back_insert_iterator无用，关闭功能(为什么不直接设为private？）
    front_insert_iterator operator*() { return *this; }
    front_insert_iterator operator++() { return *this; }
    front_insert_iterator operator++(int) { return *this; }
};

template <class Container>
inline front_insert_iterator<Container> front_inserter(Container &x) {
    return front_insert_iterator<Container>(x);
}

template <class Container>
class insert_iterator {
protected:
    Container *container;  //底层容器
    typename Container::iterator iter;

public:
    using iterator_category = output_iterator_tag;
    using value_tyep = void;
    using difference_type = void;
    using pointer = void;
    using reference = void;

public:
    insert_iterator(Container &value, typename Container::iterator i)
        : container(value), iter(i) {}
    insert_iterator &operator=(const typename Container::value_type &value) {
        container->insert(iter, value);  //调用insert
        ++iter;  //保证insert_iterator永远与目标贴合
        return *this;
    }

    //以下三个接口对back_insert_iterator无用，关闭功能(为什么不直接设为private？）
    insert_iterator operator*() { return *this; }
    insert_iterator operator++() { return *this; }
    insert_iterator operator++(int) { return *this; }
};

template <class Container, class Iterator>
inline insert_iterator<Container> inserter(Container &x, Iterator i) {
    return insert_iterator<Container>(x, i);
}

template <class Iterator>
class __reverse_iterator {
    template <class It>
    friend bool operator==(const __reverse_iterator<It> &,
                           const __reverse_iterator<It> &);
    template <class It>
    friend bool operator!=(const __reverse_iterator<It> &,
                           const __reverse_iterator<It> &);

protected:
    Iterator current;  //与之对应的正向迭代器

public:
    using iterator_category = iterator_category_t<Iterator>;
    using value_type = value_type_t<Iterator>;
    using difference_type = difference_type_t<Iterator>;
    using pointer = pointer_t<Iterator>;
    using reference = reference_t<Iterator>;

    using iterator_type = Iterator;   //正向迭代器
    using self = __reverse_iterator;  //反向迭代器

public:
    __reverse_iterator() {}
    explicit __reverse_iterator(iterator_type value) : current(value) {}
    __reverse_iterator(const self &value) : current(value.current) {}

    iterator_type base() const { return current; }
    reference operator*() const {
        Iterator temp = current;
        return *--temp;  //对逆向迭代器的取值等价于对应的正向迭代器后退一个单位取值
    }

    pointer operator->() const { return &(operator*()); }

    self &operator++() {
        --current;
        return *this;
    }

    self operator++(int) {
        self temp = *this;
        --current;
        return temp;
    }

    self &operator--() {
        ++current;
        return *this;
    }

    self operator--(int) {
        self temp = *this;
        ++current;
        return temp;
    }

    self operator+(difference_type n) const { return self(current - n); }

    self &operator+=(difference_type n) const {
        current -= n;
        return *this;
    }

    self operator-(difference_type n) const { return self(current + n); }

    self &operator-=(difference_type n) const {
        current += n;
        return *this;
    }

    reference operator[](difference_type n) const { return *(*this + n); }

    bool operator==(const self &rhs) const { return current == rhs.current; }
    bool operator!=(const self &rhs) const { return !((*this) == rhs); }
};

template <class Iterator>
inline bool operator==(const __reverse_iterator<Iterator> &lhs,
                       const __reverse_iterator<Iterator> &rhs) {
    return lhs.operator==(rhs);
}

template <class Iterator>
inline bool operator!=(const __reverse_iterator<Iterator> &lhs,
                       const __reverse_iterator<Iterator> &rhs) {
    return !(lhs == rhs);
}

template <class Iterator>
inline bool operator<(const __reverse_iterator<Iterator> &lhs,
                      const __reverse_iterator<Iterator> &rhs) {
    return rhs.base() < lhs.base();
}

template <class Iterator>
inline bool operator>(const __reverse_iterator<Iterator> &lhs,
                      const __reverse_iterator<Iterator> &rhs) {
    return rhs < lhs;
}

template <class Iterator>
inline bool operator<=(const __reverse_iterator<Iterator> &lhs,
                       const __reverse_iterator<Iterator> &rhs) {
    return !(rhs < lhs);
}

template <class Iterator>
inline bool operator>=(const __reverse_iterator<Iterator> &lhs,
                       const __reverse_iterator<Iterator> &rhs) {
    return !(lhs < rhs);
}

template <class Iterator>
inline typename __reverse_iterator<Iterator>::difference_type operator-(
    const __reverse_iterator<Iterator> &lhs,
    const __reverse_iterator<Iterator> &rhs) {
    return rhs.base() - lhs.base();
}

template <class Iterator>
inline __reverse_iterator<Iterator> operator+(
    typename __reverse_iterator<Iterator>::difference_type n,
    const __reverse_iterator<Iterator> &x) {
    return __reverse_iterator<Iterator>(x.base() - n);
}

// stream:input_stream,output_stream

template <class T, class Distance = ptrdiff_t>
class istream_iterator {
protected:
    std::istream *stream;
    T value;
    bool end_marker;
    void read() {
        end_marker = (*stream) ? true : false;
        if (end_marker) *stream >> value;
        //完成输入后，stream状态可能发生了改变，再次判定
        end_marker = (*stream) ? true : false;
    }

public:
    using iterator_category = input_iterator_tag;
    using value_tyep = T;
    using difference_type = Distance;
    using pointer = const T *;  //由于身为input_iterator，采用const较为保险
    using reference = const T &;

    istream_iterator() : stream(&std::cin), end_marker(false) {}
    istream_iterator(std::istream &s) : stream(&s) { read(); }

    reference operator*() const { return value; }
    pointer operator->() const { return &(operator*()); }

    istream_iterator &operator++() {
        read();
        return *this;
    }

    istream_iterator operator++(int) {
        istream_iterator temp = *this;
        read();
        return temp;
    }
};

template <class T>
class ostream_iterator {
protected:
    std::ostream *stream;
    const char *interval;  //输出间隔符

public:
    using iterator_category = output_iterator_tag;
    using value_tyep = void;
    using difference_type = void;
    using pointer = void;
    using reference = void;

    ostream_iterator() : stream(&std::cout), interval(nullptr) {}
    ostream_iterator(std::ostream &s, const char *c)
        : stream(&s), interval(c) {}

    ostream_iterator &operator=(const T &value) {
        *stream << value;
        if (interval) *stream << interval;
        return *this;
    }

    ostream_iterator &operator*() { return *this; }
    ostream_iterator &operator++() { return *this; }
    ostream_iterator operator++(int) { return *this; }
};

}  // namespace MiniSTL