deque.h

Go to the documentation of this file.

 
//
// Created by emon100 on 2019/12/9 0009.
#ifndef DEQUE_DEQUE_H
#define DEQUE_DEQUE_H
 
#include <utility>
#include <exception>
 
 
namespace my {
 
    const long MAXSIZE=128;//<对队列最大长度的宏定义
 
    template<typename T>
    class deque {
    private:
        typedef long size_type;
 
        struct Node;
        class const_iterator;//<队列常迭代器
        class iterator;//<队列迭代器
 
        size_type const m_max_size=my::MAXSIZE;//<队列最大长度
        size_type m_size;//<队列当前长度
 
        Node *m_front_ptr;//<队列头指针
        Node *m_tail_ptr;//<队列尾指针
    protected:
    public:
        [[nodiscard]] size_type size() const noexcept{ return m_size;}
 
 
        [[nodiscard]] size_type max_size() const noexcept{ return m_max_size;}
 
        [[nodiscard]] bool empty() const noexcept{ return m_size==0;};
 
        void push_front(const T &x){
            if(size()>=max_size()){
                return;
            } else if (empty()) {
                m_front_ptr= m_tail_ptr=new Node(x);
                ++m_size;
            } else {
                m_front_ptr = m_front_ptr->next =new Node(x,m_front_ptr);
                ++m_size;
            }
        }
        void push_front(T &&x){/*TODO*/
            if(size()>=max_size()){
                return;
            } else if (empty()) {
                m_front_ptr= m_tail_ptr=new Node(x);
                ++m_size;
            } else {
                m_front_ptr = m_front_ptr->next =new Node(std::move(x),m_front_ptr);
                ++m_size;
            }
        }
        void push_back(const T &x) {
            if (size() >= max_size()) {
                return;
            } else if (empty()) {
                m_front_ptr = m_tail_ptr = new Node(x);
                ++m_size;
            } else {
                m_tail_ptr = m_tail_ptr->prev = new Node(x, nullptr ,m_tail_ptr);
                ++m_size;
            }
        }
        void push_back(T &&x){
            if (size() >= max_size()) {
                return;
            } else if (empty()) {
                m_front_ptr = m_tail_ptr = new Node(x);
                ++m_size;
            } else {
                m_tail_ptr = m_tail_ptr->prev = new Node(x, nullptr ,m_tail_ptr);
                ++m_size;
            }
        }
        void pop_front(){
            if(m_size==0)
                return;
            else if (m_size==1){
                delete m_front_ptr;
                m_front_ptr=m_tail_ptr=nullptr;
            }else {
                m_front_ptr = m_front_ptr->prev;
                delete m_front_ptr->next;
            }
            m_size--;
        }
        void pop_back(){
            if(m_size==0)
                return;
            else if(m_size==1){
                delete m_tail_ptr;
                m_front_ptr=m_tail_ptr=nullptr;
            } else{
                m_tail_ptr=m_tail_ptr->next;
                delete m_tail_ptr->prev;
            }
            m_size--;
        }
 
        T &front(){ return m_front_ptr->data;}
        const T &front() const{ return m_front_ptr->data;}
 
        T &back(){ return m_tail_ptr->data;}
        const T &back() const { return m_tail_ptr->data;}
 
        const_iterator begin()const noexcept {
            return const_iterator(m_tail_ptr);
        }
        const_iterator end()const noexcept {
            return const_iterator();
        }
 
        iterator begin() noexcept {
            return iterator(m_tail_ptr);
        }
        iterator end() noexcept {
            return iterator();
        }
 
        T &at(size_type pos){
            if(pos >= m_size){
                throw std::out_of_range("Out of range");
            }else{
                return (*this)[pos];
            }
        }
 
        const T &at(size_type pos) const{
            if(pos >= m_size){
                throw std::out_of_range("Out of range");
            }else{
                return (*this)[pos];
            }
        }
 
        T &operator[](size_type pos)noexcept {
            iterator a=this->begin();
            for (int i = 0; i < pos ; ++i,++a);
            return *a;
        }
 
       const T &operator[](size_type pos) const noexcept{
           const iterator a=this->begin();
           for (int i = 0; i < pos ; ++i,++a);
           return *a;
       }
 
 
        deque():
                m_size(0),
                m_front_ptr(nullptr),
                m_tail_ptr(nullptr) {}
 
        deque(const deque &x) :
                m_size(0),
                m_tail_ptr(nullptr),
                m_front_ptr(nullptr){
            for(auto a:x){
                push_front(a);
            }
        }
 
        deque &operator=(const deque &x){
            if(this!=&x) {
                deque copy = x;
                std::swap(*this, copy);
            }
            return *this;
        }
 
        deque(deque &&x) noexcept:
                m_tail_ptr(x.m_tail_ptr),
                m_front_ptr(x.m_front_ptr),
                m_size(x.m_size),
                m_max_size(x.m_max_size)
        {
            x.m_size=0;
            x.m_tail_ptr=x.m_front_ptr=nullptr;
        }
 
        deque &operator=(deque &&x)noexcept {
            if(this != &x) {
                std::swap(m_size, x.m_size);
                std::swap(m_front_ptr, x.m_front_ptr);
                std::swap(m_tail_ptr, x.m_tail_ptr);
            }
            return *this;
        }
 
        deque(std::initializer_list<T> x) :
                m_size(0),
                m_max_size(128),
                m_tail_ptr(nullptr),
                m_front_ptr(nullptr){
            for (auto a:x) {
                push_front(a);
            }
        }
 
        deque &operator=(std::initializer_list<T> x){
            *this = deque<T>(x);
            return *this;
        }
 
        ~deque(){
            while(m_size) {
                pop_back();
            }
        }
    };
 
    template <typename T>
    struct deque<T>::Node {
        T data;
        Node *prev;
        Node *next;
 
        explicit Node(const T &d=T{},Node *p= nullptr,Node *n= nullptr):
                data(d),
                prev(p),
                next(n){}
 
        explicit Node(T &&d,Node *p = nullptr, Node *n = nullptr):
                data(std::move(d)),
                prev(p),
                next(n){}
    };
 
    template <typename T>
    class deque<T>::const_iterator {
    public:
        const_iterator():current(nullptr){}
        const T &operator*()const{ return retrieve();}
        const_iterator &operator++(){
            current = current->next;
            return *this;
        }
 
        const_iterator operator++(int) {
            const_iterator old =*this;
            ++(*this);
            return old;
        }
 
        bool operator==(const const_iterator &rhs)const{ return  current == rhs.current;}
        bool operator!=(const const_iterator &rhs)const{ return  !(current == rhs.current);}
 
    protected:
        T & retrieve() const{ return current->data; }
        Node *current;
        const_iterator(Node *p):current(p){}
        friend class deque<T>;
    };
 
    template <typename T>
    class deque<T>::iterator : public deque<T>::const_iterator{
    public:
        iterator(){}
        T &operator*(){
            return const_iterator::retrieve();
        }
        iterator &operator++(){
            this->current=this->current->next;
            return *this;
        }
        iterator operator++(int){
            iterator old=*this;
            ++(*this);
            return old;
        }
 
    protected:
        iterator(Node *p) : const_iterator(p){}
 
        friend class deque<T>;
    };
 
}
#endif //DEQUE_DEQUE_H