list是一个双向循环链表,因此它每次插入和删除数据都会配置或者删除空间,不会产生空间的浪费;而且对于任何位置的插入和移除,它的时间复杂度都是常数。下面介绍list的节点,迭代器以及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;}
};
关于list的数据结构,只需要一个指针便可以表示整个双向环状链表:把Node指向刻意置于尾端的空白链表,node便可以符合stl前闭后开的所有要求:
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());
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。