网站建设合同书样本,手机百度经验首页登录官网,wordpress点击文章跳转外站,拿回家组装的零件加工活C:list增删查改模拟实现 前言一、list底层双链表验证、节点构造1.1 list底层数据结构1. 2 节点构造 二、迭代器封装实现#xff08;重点、难点#xff09;2.1 前置说明2.2 迭代器实现 三、list实现3.1 基本框架3.2 迭代器和const迭代器3.2 构造函数、析构函数、拷贝构造、赋值… C:list增删查改模拟实现 前言一、list底层双链表验证、节点构造1.1 list底层数据结构1. 2 节点构造 二、迭代器封装实现重点、难点2.1 前置说明2.2 迭代器实现 三、list实现3.1 基本框架3.2 迭代器和const迭代器3.2 构造函数、析构函数、拷贝构造、赋值重载3.2.1 构造函数3.2.2 析构函数3.2.3 拷贝构造3.2.4 赋值重载 3.3 任意位置插入、任意位置删除、尾插、尾删、头插、头删3.3.1任意位置插入3.3.2任意位置插入删除3.3.3 尾插、尾删、头插、头删 四、list功能完善4.1 迭代器operator-()4.2 打印数据 五·、所有代码以及测试用例 前言
本篇博客采用SGI版本同时考虑到看到此篇博客大部分为初学者为此博主仅仅给出有用片段。C:list增删查改模拟实现就是用C复写双链表非常简单。难点主要在迭代器实现
一、list底层双链表验证、节点构造
1.1 list底层数据结构
list底层使用什么数据结构来实现的呢我们先来看看SGI库中list的成员函数和初始化吧。 我们发现list实现中只有node一个成员变量。构造函数构造出一个头尾相连的哨兵位。同时验证了list底层是一个带哨兵位的双链表。 1. 2 节点构造 节点和双链表一样有三个成员节点数据、指向前一个节点(prev)、指向后一个节点(next)。 //节点
templateclass T
struct List_node
{T _data;List_nodeT* _prev;List_nodeT* _next;List_node(const T x T()):_data(x),_prev(nullptr),_next(nullptr){}
};小tips:
我们这里类名和库中一样(List_node)后续在其他类中使用时在typedef。这里类名使用struct而不是class原因在于struct默认访问权限为公有后续其他类只都需要大量使用。如果使用class需要使用大量友元类过于繁琐。
二、迭代器封装实现重点、难点
2.1 前置说明
我们知道迭代器的最大用途便是遍历数据。但何时停在迭代器指向空间存储数据时是什么…导致我们需要使用!、、*等操作。但自定义类型是无法支持使用这些操作符的。为此给出的解决办法是封装加运算符重载。迭代器使用上分为普通迭代器和const迭代器还分为单向迭代器、双向迭代器和随机访问迭代器。其中一种最简单的实现方式就是实现两个类。但。。。我们知道两个迭代器的不同之处在于const迭代器无法修改数据只是j相关借口这里有*、-不同而已便实现两个类未免过于“小题大做”。 所以接下来我们来看看库中是如何巧妙的解决这个问题吧
2.2 迭代器实现
前置说明中以及解决了如何实现一个类达到目的。接下来的实现过于简单就不单独说明了。
//迭代器封装
templateclass T, class Ref, class Ptr
struct __list_iterator
{typedef List_nodeT Node;//节点类名重命名//由于迭代器实现中,如、--等重载函数返回值类型为__list_iterator名字过长,这里我们重命名self意味自身typedef __list_iteratorT,Ref, Ptr self;Node* _node;//成员变量__list_iterator(Node* node)//构造出一个节点:_node(node){}//前置self operator(){_node _node-_next;return *this;}//前置--self operator--(){_node _node-_prev;return *this;}//后置self operator(int){self tmp(*this);_node _node-_next;return tmp;}//后置--self operator--(int){self tmp(*this);_node _node-_prev;return tmp;}//解引用操作符重载Ref operator*(){return _node-_data;}//用于访问迭代器指向对象中存储的是自定义类型Ptr operator-(){return _node-_data;}bool operator!(const self s){return _node ! s._node;}bool operator(const self s){return _node s._node;}
};三、list实现
3.1 基本框架
list模拟中我们和库中一样给出一个头节点_head、_size两个成员变量。同时我们将节点、迭代器进行重命名。迭代器重命名不是单纯图方便更重要的是提供统一接口(例如sting、vector、set等接口都一样)屏蔽底层的变量和成员函数属性实现过程和差异。
//list模拟实现
templateclass T
class List
{typedef List_nodeT Node;
public://迭代器重命名提供统一的接口屏蔽底层实现细节和差异typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;
private:Node* _head;//头节点int _size;
};3.2 迭代器和const迭代器
下面是begin()、end()指向一个有效双线表的位置。
实现
const_iterator begin()const
{//return const_iterator(_head-_next);或return _head-_next;//单参数类型支持隐式类型转换
}const_iterator end()const
{return _head;
}iterator begin()
{return _head-_next;
}iterator end()
{return _head;
}3.2 构造函数、析构函数、拷贝构造、赋值重载
3.2.1 构造函数
构造函数的实现和开头中看到的一样构造函数中调用一个函数empty_Init来是实现。empty_Init()用来完成初始化。empty_Init()函数后续其他接口也要调用
//初始化
void empty_Init()
{_head new Node;_head-_next _head;_head-_prev _head;_size 0;
}//无参构造
List()
{empty_Init();
}3.2.2 析构函数
析构函数我们调用一个clear函数来将数据全部清空在将_head变量释放。
//析构函数
~List()
{clear();delete _head;_head nullptr;
}void clear()
{iterator it begin();while (it ! end()){it erase(it);}
}3.2.3 拷贝构造
拷贝构造时首先要初始化出一个节点然后将需要拷贝的数据依次尾插即可尾插接口后续给出实现
//拷贝构造
List(const ListT It)
{empty_Init();for (auto e : It){push_back(e);}
}3.2.4 赋值重载
赋值重载有很多方式。比较简单的参数我们直接传值然后将待赋值的变量和传值传参省生成的临时变量的数据进行交换即可。
void swap(const ListT It)
{std::swap(_head, It._head);
}//赋值重载
ListT operator(const ListT It)
{swap(It);return *this;
}3.3 任意位置插入、任意位置删除、尾插、尾删、头插、头删
3.3.1任意位置插入
首先new出待插入节点newnode然后将pos前一个节点prev、newnode、pos相连。最后_size即可。
iterator insert(iterator pos, const T x)
{Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;return newnode;
}3.3.2任意位置插入删除
将待删除数据的前后节点先保存起来然后将删除pos处节点再将前后节点连接起来。最后–_size即可。
iterator erase(iterator pos)
{Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;delete cur;prev-_next next;next-_prev prev;_size--;return next;
}3.3.3 尾插、尾删、头插、头删
尾插、尾删、头插、头删都是复用任意位置插入、任意位置删除接口。
void push_back(const T x)
{insert(end(), x);
}void push_front(const T x)
{insert(begin(), x);
}void pop_back()
{erase(--end());
}void pop_front()
{erase(begin());
}四、list功能完善
4.1 迭代器operator-()
我们先来看看下面这段代码对吗
struct AA
{AA(int a1 0, int a2 0):_a1(a1),_a2(a2){}int _a1;int _a2;
};void test_list3()
{listAA lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));listAA::iterator it lt.begin();while (it ! lt.end()){cout*it ;it;}cout endl;
}由于list没有重载所以对存储的是自定义类型之间访问会编译报错。 那我们重载下运算符不就行了吗很不幸的是C库在list中不支持很大原因也在于编译器不知到我们如何取数据 所以对于自定义类型我们可以先解引用在去访问成员也可以在迭代器中重载operator-()函数。但需要注意的是编译器隐藏了一个-具体原生行为如下
struct AA
{AA(int a1 0, int a2 0):_a1(a1),_a2(a2){}int _a1;int _a2;
};void test_list3()
{listAA lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));listAA::iterator it lt.begin();while (it ! lt.end()){//cout (*it)._a1 (*it)._a2 endl;cout it-_a1 it-_a2 endl;//上面编译器访问成员变量的真正行为如下//cout it.operator-()-_a1 it.operator-()-_a1 endl;it;}cout endl;
}4.2 打印数据
//大多数情况模板是class还是typename是一样的但当有未实例化模板时必须使用typename
//templatetypename T
void print_list(const listT lt)
{// listT未实例化的类模板编译器不能去他里面去找// 编译器就无法listT::const_iterator是内嵌类型还是静态成员变量// 前面加一个typename就是告诉编译器这里是一个类型等listT实例化// 再去类里面去取typename listT::const_iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;
}优化上面打印数据是针对list下面是针对容器的。
// 模板(泛型编程)本质本来应该由我们干的活交给编译器
templatetypename Container
void print_container(const Container con)
{typename Container::const_iterator it con.begin();while (it ! con.end()){cout *it ;it;}cout endl;
}五·、所有代码以及测试用例
giteeC:list增删查改模拟实现代码以及测试用例 推荐giteeC:list增删查改模拟实现代码最终版本、感觉版本
