C++学习笔记-list容器

//list节点
template <class T>
struct _list_node{
    _list_node<T>* prev; //指向前一个_list_node
    _list_node<T>* next; //指向后一个_list_node
    T data;
};
//所以很显然_list_node是一个双向链表

//迭代器的设计，必须要正确的递减，递增，取值，成员存取
template<class T, class Ref, class Ptr>  //这是gnu2.9写法，4.9就把这一写法简化成template<class T>
struct _list_iterator{
    typedef _list_iterator<T, T&, T*>    iterator;
    typedef _list_iterator<T, Ref, Ptr>  self;
    //以下五个是大部分容器共有的写法
    typedef bidirectional_iterator_tag iterator_category; //该类提供 iterator_category 表示双向迭代器的函数的返回类型
    typedef T         value_tyep;
    typedef Ptr       pointer;
    typedef Ref       reference;
    typedef ptrdiff_t difference_type;
    
    typedef size_t         size_type;
    typedef _list_node<T>* link_type; //迭代器内部的指向list节点的指针
    
    link_type node;
    
    //构造函数
    _list_iterator(link_type x) : node(x){}
    _list_iterator(){}
    _list_iterator(const _list_iterator& x) : node(x.node){}
    
    //非关键重载
    bool operator == (const _list_iterator& x) const {return x.node == node;}
    bool operator != (const _list_iterator& x) const {return x.node != node;}
    
    //关键重载，取值，成员存取，递增，递减
    
    reference operator* () const { return (*node).data;} //(*node) ==>取list节点对象，然后.data得到data的值
    pointer operator -> () const { return &(operator*());} //operator*() ==> 取list节点对象，然后.data得到data的值; 取地址符得到data的指针
    self& operator ++ () {this->node = (*node).next; return *this;} //表示前++，也就是++node
    self operator ++ (int) {self tmp = *this; ++ *this; return tmp;} //用有无int区别前++还是后++,这是后++
    
    //关于后++: self tmp = *this;关于*为什么没有被重载，因为编译器先遇到的是=因此后面的*this是相当于等于的参数，后面的++ *this也是如此
    //为什么后++返回的不能是self&, 因为tmp是局部变量，这个函数执行完就会直接销毁，销毁后，，你用引用就是变成一个空的引用。
    
    self& operator -- () {this->node = (*node).prev; return *this;} 
    self operator -- (int) {self tmp = *this; -- *this; return tmp;} 
};

template<class T, class Alloc = allocator>
class list{
protected:
    typedef _list_node<T> list_node;
public:
    typedef list_node* link_type;
protected:
    link_type node; //只需要一个指针就可以表示整个双向环状链表
   ... 
};

//begin()
iterator begin() const {return (link_type)(*node).next;}
//end()
iterator end() const {return node;}
//empty()
bool empty() const {return node->next == node;}
//size()
size_type size() const {
    size_type result = 0;
    distance(begin(), end(), result);
    return result;
}

//取链表头的内容front()
reference front() const{
    return *begin();
}
//取表尾的元素back()
reference back() {
    return *(--end());
}

//配置和释放空间要用到分配器，我之前的文章写了，，这里不多说

//插入新元素到尾端push_back()，函数内部调用insert()
void push_back(const T& x) {insert(end(), x);}

//插入新元素到开头push_front()，函数内部调用insert()
void push_front(const T& x){insert(begin(), x);}

//insert()函数
iterator insert(iterator position, const T& x){
    link_type tmp = creator_node(x)  //就是调用分配器和里面的construct函数进行空间的分配和初始化
    //开始插入
    tmp->next = position.node;
    tmp->prev = position.node->prev;
    (link-type)(position.node->prev)->next = tmp;
    position.node->prev = tmp;
    return tmp;
}

//移除迭代器所指的节点
iterator erase(iterator position)
{
    link_type next_node = (link_type)(position.node->next);
    link_type prev_node = (link_type)(position.node->prev);
    prev_node->next = next_node;
    next_node->prev = prev_node;
    return iterator(next_node);
}

//pop_back()
void pop_back(){
    erase(--end());
}

//pop_front()
void pop_front()
{
    erase(begin());
}