版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1338353
list
实现的三个模块节点__list_node
,迭代器__list_iterator
以及list本身
(使用一个__list_node*代表整个链表)的介绍。list
的几个核心函数,理解STL list
的实现原理,核心函数如下:list
的构造函数list
,包括基本类型如int
以及结构体。list
实现的三个模块节点定义如下:
template<typename T>
struct __list_node{
typedef __list_node* list_node_pointer;
list_node_pointer prev;
list_node_pointer next;
T data;
};
迭代器__list_iterator
迭代器的定义如下(下面先省略了iterator_category迭代器类型),迭代器主要是作为 list
内部的iterator
来使用:
template<typename T>
struct __list_iterator{
typedef __list_iterator<T> self;
typedef __list_node<T>* link_type;
link_type ptr; //成员
__list_iterator(link_type p = nullptr):ptr(p){}
.....//先省略成员函数
}
list
的迭代器需要实现的操作有:++、–、*、->、==、!=,定义如下:
T& operator *(){return ptr->data;}
T* operator ->(){return &(operator*());}
self& operator++(){
ptr = ptr->next;
return *this;
}
self operator++(int){
self tmp = *this;
++*this;
return tmp;
}
self& operator--(){
ptr = ptr->prev;
return *this;
}
self operator--(int){
self tmp = *this;
--*this;
return tmp;
}
bool operator==(const __list_iterator& rhs){
return ptr == rhs.ptr;
}
bool operator!=(const __list_iterator& rhs){
return !(*this==rhs);
}
list
的核心实现list节点
的主要类型,以及成员变量list主要的变量别名,以及成员定义如下:
template<typename T>
class SimpleList{
protected:
typedef __list_node<T> list_node;
// nodeAllocator 按照 list_node为单位分配内存
typedef allocator<list_node> nodeAllocator;
public:
typedef T value_type;
typedef T& reference;
typedef value_type* pointer;
typedef list_node* link_type;
typedef const value_type* const_pointer;
typedef size_t size_type;
public:
typedef __list_iterator<value_type> iterator;
private:
link_type node; // 只要一个指针,便可表示整个环状双向链表
.............//为了更清晰的看list的定义,先省略其他的函数
}
list
的构造函数在给出list的构造函数之前,先给出,list内部的向空间配置申请节点的内存分配,以及在节点上面构造对象(调用对象的构造函数),节点返还给空间配置器,以及对象的析构(调用对象的析构函数)。
// 分配一个新结点(分配内存), 注意这里并不进行构造,
link_type alloc_node(){
return nodeAllocator::allocate();
}
// 释放一个结点(节点内存由空间配置回收)
void dealloc_node(link_type p){
nodeAllocator::deallocate(p);
}
// 产生(配置并构造)一个节点, 首先分配内存, 然后进行构造
link_type alloc_ctor_node(const T& val){
link_type p = alloc_node();
// 这里要构造的是节点的data
construct(&p->data, val);
return p;
}
// 析构结点元素, 并释放内存
void dealloc_dtor_node(link_type p){
destroy(&p->data);
dealloc_node(p);
}
基本的构造函数定义如下:
void empty_initialize(){
node = alloc_node(); // 配置一个节点空间,令node指向它
node->prev = node; // 令node头尾都指向自己,不设元素值
node->next = node;
}
SimpleList(){
empty_initialize();
}
注:
explicit SimpleList(size_t n);
构造函数后面在给出
list
迭代器的基本操作iterator begin(){
// link_type可以转化为iterator(构造函数)
// iterator(重载了++ --等)
return (link_type)(node->next);
}
iterator begin()const{
return (link_type)(node->next);
}
iterator end(){
// 链表成环, 当指所以头节点也就是end
return node;
}
iterator end()const{
return node;
}
empty判断:
bool empty()const{return node == node->next;}
list
的插入操作template<typename T>
typename SimpleList<T>::iterator SimpleList<T>::insert(
iterator position, const T& value){
link_type tmp = alloc_ctor_node(value);
// 调整双向指针,使tmp插入进去
tmp->next = position.ptr;
tmp->prev = position.ptr->prev;
position.ptr->prev->next = tmp;
position.ptr->prev = tmp;
return tmp;
}
template<typename T>
void SimpleList<T>::push_back(const T& value){
insert(end(), value);
}
template<typename T>
typename SimpleList<T>::iterator SimpleList<T>::insert(
iterator position, size_t n, const T& value){
while(n--){
// 由于是相同的值,所以顺序无关
insert(position, value);
}
}
接下来我们看 explicit SimpleList(size_t n);
构造函数
template<typename T>
void SimpleList<T>::fill_initialize(size_t n, const T& value){
// 先初始化起始点
empty_initialize();
insert(begin(), n, value);
}
template<typename T>
SimpleList<T>::SimpleList(size_type n, const T& value){
fill_initialize(n, value);
}
如下这个构造函数有点小问题,会创建一个临时对象,然后调用对象的copy构造函数,实际上STL 中的list,只会调用对象的默认构造函数,这里只是为了简化,具体的可以见前面的vector源码实现分析文章。
template<typename T>
SimpleList<T>::SimpleList(size_t n){
fill_initialize(n, T());
}
list
,包括基本类型如int
以及结构体。int
测试首先测试基本的int
SimpleList<int> slInt(5, 10);
std::cout<<slInt<<std::endl;
std::cout<<slInt.size()<<std::endl; // 8
输出如下:
allocator分配的大小是以__list_node为大小单位,初始化的时空间配置器,没有任何内存,由于申请的大小单位<128bytes,因此二级配置器,会给对应的free_list分配20个节点。 构造函数根据大小n每次拿一个
接下来:
SimpleList<int> slInt1;
std::cout<<slInt1.size()<<std::endl; // 0
输出如下:
会默认的为list构造一个头节点。
结构体测试,结构体如下:
struct TestLst{
int a; char c1;
TestLst(int i = 0, char c = 'c'):a(i), c1(c){
std::cout<<"TestLst ctor a: "<<a<<" c1: "<<c1<<std::endl;
}
TestLst(const TestLst& tv):a(tv.a), c1(tv.c1){
std::cout<<"TestLst copy ctor a: "<<a<<" c1: "<<c1<<std::endl;
}
~TestLst(){
std::cout<<"TestLst dtor a: "<<a<<" c1: "<<c1<<std::endl;
}
};
测试代码如下:
SimpleList<TestLst> slStr(5);
std::cout<<"======now clear======"<<std::endl;
slStr.clear();
std::cout<<"======now insert new item======"<<std::endl;
slStr.push_back(TestLst());
输出如下: