加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 百科 > 正文

C++Linklist

发布时间:2020-12-16 07:19:43 所属栏目:百科 来源:网络整理
导读:#if 1 #ifndef _LINKLIST_H_ #define _LINKLIST_H_ #include iterator #pragma warning (disable : 26495) template typename T class linklist{ public : using uint = unsigned int ; struct _iterator; protected : struct _node; uint _size; _node * he
#if 1
#ifndef _LINKLIST_H_
#define _LINKLIST_H_
#include <iterator> 

#pragma warning (disable : 26495)

template<typename T>
class linklist{
public:
    using uint = unsigned int;
    struct _iterator;
    
protected:
    struct _node;
    uint _size;
    _node *head;

    void copy_linklist(const linklist<T> &);
    void init_head();
public:
    //construction and destruction
    linklist();
    linklist(const linklist<T> &ls);
    explicit linklist(const uint);
    linklist(const uint,const T &);
    linklist(_iterator,_iterator);
    ~linklist();

    void push_back(const T &);
    void pop_back();
    void push_front(const T &);
    void pop_front();
    _iterator erase(_iterator);
    _iterator erase(_iterator,_iterator);
    

    const T &back() const{ return head->prior->_value; }
    T &back(){ return head->prior->_value; }               //last element
    const T &front()const{ return head->next->_value; }
    T &front(){ return head->next->_value; }               //first element

    linklist<T> &operator=(const linklist<T> &);
    void reverse();
    bool empty()const{ return _size == 0; }
    uint size()const{ return _size; }

    _iterator begin(){ return _iterator(head->next); }
    _iterator end(){ return _iterator(head); }


    void clear();
};

template<typename T>
struct linklist<T>::_node{
    T _value;
    _node *prior;
    _node *next;

    _node &operator=(const _node &n){
        this->next = n.next;
        this->prior = n.prior;
        this->_value = n._value;
    }

    

    _node() :_value(T()),prior(this),next(this){ }
    _node(const T &value) :_value(value),prior(this),next(this){ }
    _node(const _node &n) :_value(n._value),prior(n.prior),next(n.next){ }
    ~_node(){ }


};

template<typename T>
struct linklist<T>::_iterator : 
    public std::iterator<std::bidirectional_iterator_tag,T>{

protected:
    _node *_real_node;

public:
    _iterator():_real_node(){ }
    _iterator(const _iterator &iter) :_real_node(iter._real_node){ }
    _iterator(_node *n):_real_node(n){ }

    _node *get_ptr(){
        return _real_node;
    }

    T &operator*()const{ return _real_node->_value; }
    T *operator->()const{ return &_real_node->_value; }
    
    _iterator &operator=(const _iterator &iter){
        _real_node = iter._real_node;
        return *this;
    }

    bool operator==(const _iterator &iter) const{
        return _real_node == iter._real_node;
    }

    bool operator!=(const _iterator &iter)const{
        return _real_node != iter._real_node;
    }

    bool operator!()const{
        return !_real_node;
    }

    _iterator &operator++(){
        _real_node = _real_node->next;
        return *this;
    }

    _iterator operator++(int){
        auto old = *this;
        ++ *this;
        return old;
    }

    _iterator &operator--(){
        _real_node = _real_node->prior;
        return *this;
    }

    _iterator operator--(int){
        auto old = *this;
        -- *this;
        return old;
    }


};


template<typename T>
void linklist<T>::copy_linklist(const linklist<T> &ls){ 
    clear();
    init_head();
    auto p = ls.head->next;
    while(p != ls.head){
        this->push_back(p->_value);
        p = p->next;
    }
}

template<typename T>
void linklist<T>::clear(){
    _size = 0;
    if(!empty()){
        auto p = head;
        while(p->next != head){
            auto q = p;
            p = p->next;
            delete q;
        }
        delete p;    //p->next == head
    }
    delete head;
}

template<typename T>
void linklist<T>::init_head(){ 
    head = new _node;
    head->next = head->prior = head;
    head->_value = T();
}

template<typename T>
linklist<T>::linklist() : _size(0){
    init_head();
}

template<typename T>
linklist<T>::linklist(const linklist<T> &ls){ 
    copy_linklist(ls);
}

template<typename T>
linklist<T>::linklist(const uint cnt) :_size(0){
    init_head();
    for(register uint i(0); i < cnt; ++i)
        this->push_back(T());
    
}

template<typename T>
linklist<T>::linklist(const uint cnt,const T &value) :_size(0){
    init_head();
    for(register uint i(0); i < cnt; ++i){
        this->push_back(value);
    }
}

template<typename T>
linklist<T>::~linklist(){ 
    clear();
}

template<typename T>
linklist<T>::linklist(_iterator first,_iterator last) :_size(0){ 
    init_head();
    while(first != last){
        this->push_back(*first);
        ++first;
    }
}

template<typename T>
void linklist<T>::push_back(const T &value){ 
    _node *p = new _node;
    p->_value = value;
    p->next = head;                  //head->next == first elem
    p->prior = head->prior;             //head->prior == last elem
    head->prior->next = p;
    head->prior = p;
    ++_size;
}

template<typename T>
void linklist<T>::push_front(const T &value){
    auto p = new _node;
    p->_value = value;
    p->next = head->next;
    p->prior = head;
    head->next = head->next->prior = p;
    ++_size;
}

template<typename T>
void linklist<T>::pop_back(){
    auto p = head->prior;
    p->prior->next = head;
    head->prior = p->prior;
    p->_value.~T();
    --_size;
    delete p;
}

template<typename T>
void linklist<T>::pop_front(){
    auto p = head->next;
    head->next = p->next;
    p->next->prior = head;
    p->_value.~T();
    --_size;
    delete p;
}

template<typename T>
typename linklist<T>::_iterator linklist<T>::erase(_iterator iter){
    auto ptn = iter.get_ptr();
    auto ptn_next = ptn->next;
    ptn->next->prior = ptn->prior;
    ptn->prior->next = ptn->next;
    delete ptn;
    --_size;
    return _iterator(ptn_next);
}

template<typename T>
typename linklist<T>::_iterator linklist<T>::erase(_iterator first,_iterator last){
    while(first != last){
        first = erase(first);
    }
    return first;
}



template<typename T>
linklist<T> &linklist<T>::operator=(const linklist<T> &ls){
    copy_linklist(ls);
    return *this;
}

template<typename T>
void linklist<T>::reverse(){ 
    auto iter = begin();
    for(register uint i(0); i < _size; ++i){
        push_front(*iter);
        iter = erase(iter);
    }
}



#endif // !_LINKLIST_H_

#endif

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读