大数据技术建设网站,做网站的基础架构,湖北网站建设公司,成品app直播源码下载代码仓库#xff1a; list模拟实现 list源码 数据结构——双向链表 文章目录 #x1f347;1. 节点结构体#x1f348;2. list成员#x1f349;3. 迭代器模板#x1f34a;4. 迭代器#x1f34b;5. 插入删除操作#x1f34c;5.1 insert erase#x1f34c;5.2 push_… 代码仓库 list模拟实现 list源码 数据结构——双向链表 文章目录 1. 节点结构体2. list成员3. 迭代器模板4. 迭代器5. 插入删除操作5.1 insert erase5.2 push_back push_front pop_back pop_front 6. 构造 析构 拷贝构造7. 赋值重载8. 获取元素个数 1. 节点结构体
源码的list是双向带头循环链表所以我们定义两个节点一个指向下一个一个指向前一个
templateclass T
struct list_node
{list_nodeT* _next; //指向下一个节点list_nodeT* _prev; //指向前一个T _val; //数据list_node(const T val T()):_next(nullptr), _prev(nullptr), _val(val){}
};2. list成员
list类包含一个_head头节点然后为了方便查出当前有多少个节点还能多定义一个_size
templateclass T
class list
{typedef list_nodeT Node;
public:// 各类操作方法//...
private:Node* _head;size_t _size;
}3. 迭代器模板 源码的迭代器设置了三个模板参数
T表示指向list节点的数据类型Ref迭代器的引用类型通常情况为T但也可表示constPtr表示指向节点的指针类型通常情况下为T*但也可表示const迭代器避免代码的冗余
对于string或者是vector的迭代器对其解引用就可以表示当前的数据而list是链表解引用之后表示的一个节点所以相对会麻烦一点
//Ref T / const T
//Ptr T* / const T*
templateclass T, class Ref, class Ptr
struct __list_iterator
{typedef __list_iteratorT, Ref, Ptr self;typedef list_nodeT Node;Node* _node;__list_iterator(Node* node):_node(node){}Ref operator*(){return _node-_val;}Ptr operator-(){return _node-_val;}//前置self operator(){_node _node-_next;return *this;}//后置self operator(int){self tmp(*this);_node _node-_next;return tmp;}//前置--self operator--(){_node _node-_prev;return *this;}//后置--self operator--(int){self tmp(*this);_node _node-_prev;return tmp;}bool operator!(const self lt){return _node ! lt._node;}bool operator(const self lt){return _node lt._node;}};Tips: 迭代器并没有写拷贝构造那么就是默认浅拷贝。这无关影响因为我们就是希望通过这个迭代器找到这个节点 void test1()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);//浅拷贝listint::iterator it lt.begin();while(it!lt.end()){cout *it ;it;}coutendl;
}这里没有奔溃也是因为迭代器没有写析构函数迭代器只是负责访问并不负责管理 4. 迭代器
const const_iterator begin() const
{//单参数构造函数 隐式类型转换return _head-_next;
}
const const_iterator end() const
{return _head;
}iterator begin()
{//单参数构造函数 隐式类型转换return _head-_next;
}
iterator end()
{return _head;
}5. 插入删除操作
5.1 insert erase
这里插入删除操作之后也会存在当前迭代器失效所以传修改完毕之后的迭代器位置 iterator insert(iterator pos, const T x)
{Node* cur pos._node;Node* tmp new Node(x);Node* prev cur-_prev;prev-_next tmp;tmp-_next cur;cur-_prev tmp;tmp-_prev prev;_size;return tmp;
}
iterator erase(iterator pos)
{assert(pos ! end());Node* cur pos._node;Node* next cur-_next;Node* prev cur-_prev;prev-_next next;next-_prev prev;delete cur;--_size;return next;
}5.2 push_back push_front pop_back pop_front
写了指定位置插入删除之后直接复用即可
void push_back(const T x)
{insert(end(), x);
}void push_front(const T x)
{insert(begin(), x);
}void pop_back()
{Node* tail _head-_prev;erase(tail);
}
void pop_front()
{erase(begin());
}6. 构造 析构 拷贝构造
查看源码发现list的构造和析构都采用了复用 清空链表
void clear()
{iterator it begin();while (it ! end()){it erase(it);}//_size 0;
}复用
void empty_init()
{_head new Node;_head-_next _head;_head-_prev _head;_size 0;
}list()
{empty_init();
}list(const listT lt)
{empty_init();for (auto e : lt){push_back(e);}
}
~list()
{clear();delete _head;_head nullptr;
}7. 赋值重载
这里还是采用现代的写法交换完毕之后自动调用析构函数
void swap(listT lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}
listT operator(listT lt)
{swap(lt);return *this;
}8. 获取元素个数
size_t size()
{return _size;
}以上就是list的基本功能实现实质上就是双向带头循环链表迭代器这块有点复杂。
那本期分享就到这里咯我们下期再见如果还有下期的话。