做类似于彩票的网站犯法吗,个人网站是什么意思,郑州市主城区,网络营销渠道的功能从零开始手写STL库–List部分
Github链接#xff1a;miniSTL 文章目录 从零开始手写STL库–List部分List是什么#xff1f;List需要包含什么函数1#xff09;基础成员函数2#xff09;核心功能3)其他功能 基础成员函数的编写核心功能的编写其他功能编写总结 List是什么miniSTL 文章目录 从零开始手写STL库–List部分List是什么List需要包含什么函数1基础成员函数2核心功能3)其他功能 基础成员函数的编写核心功能的编写其他功能编写总结 List是什么
std::list是基于双向链表的的数据结构与std::vector基于数组不同list在频繁插入和删除的场景中更适合应用。
List需要包含什么函数
应当具有
1基础成员函数
构造函数初始化List头节点 析构函数释放内存当运行结束后要摧毁这个List防止内存泄漏 不同于VectorList这种以链表为基础的容器一般不需要去拷贝新的List也就不用手动构建拷贝构造函数和拷贝赋值操作符
2核心功能
push_back/push_front在List的末尾/头部加入新元素 pop_back/pop_front移除List末尾/头部元素 size获取List长度 clear清空List get获取List中某个元素的值 remove删除某个节点 find查找某个值对应的节点 empty检查List是否为空
3)其他功能
迭代器、重载输出符等等
基础成员函数的编写
List的成员 List本身是链表那么每个节点应该包括本节点的数据、指向上/下一个节点的指针而List是描述这一系列节点构成的双向链表那么只需要记录头节点、尾节点以及List长度即可
templatetypename T
class myList
{
private:struct Node{T data;Node * next;Node * prev;Node(const T data_, Node * next_ nullptr, Node * prev_ nullptr): data(data_), next(next_), prev(prev_) {} };Node * head;Node * tail;size_t current_size;
public:};构造函数和析构函数就是
public:myList() : head(nullptr), tail(nullptr), current_size(0) {}~myList() {clear(); }再次提示这里的构造函数用current_size(0) 初始化才是合规的放在中括号内会浪费掉这个初始化进程
析构函数调用一下清空函数即可
核心功能的编写
1、push_back/push_front函数在List的末尾/头部加入新元素 链表不像动态数组需要考虑分配问题所以直接加就行了
但是也需要判断List为空的清空如果为空head/tail是没法取出next指针的此时就会报错
所以在push的时候检查一下
在力扣算法题中避免这种复杂操作的方法是构建一个虚拟头节点就可以统一处理 void push_back(const T value){Node * temp new Node(value, nullptr, tail);if(tail) tail-next temp;else head temp;tail temp;current_size ;}void push_front(const T value){Node * temp new Node(value, head, nullptr);if(head) head-prev temp;else tail temp;head temp;current_size ;}2、pop_back/pop_front函数移除List末尾/头部元素 头尾节点的删除较为简单注意一下空列表的情况特殊处理即可 void pop_back(){if(current_size 0){Node * temp tail-prev;delete tail;tail temp;if(tail) tail-next nullptr;else head nullptr;current_size --;}}void pop_front(){if(current_size 0){Node * temp head-next;delete head;head temp;if(head) head-prev nullptr;else tail nullptr;current_size --;}}这里如果删除之后发现头/尾节点是空了说明这个List已经空了但是另一端还没处理所以要让另一端也为nullptr否则有可能发生指针越界问题。
3、size函数获取List长度 int size(){return current_size;}4、clear函数清空List 不同于vector那样直接将size归零List需要考虑节点占用的内存所以实际上是需要循环释放的
void clear()
{ while (head) { Node * temp head;head head-next; delete temp; } tail nullptr; current_size 0;
}5、get函数获取List中某个元素的值 这里的实现方法不是给定一个get函数而是重载符号“[]”这样就能更加方便地访问了 T operator[](size_t index){Node * curr head;for(size_t i 0; i index; i ){if(!curr) throw std::out_of_range(Index out of range!);curr curr-next;}return curr-data;}const T operator[](size_t index) const{Node * curr head;for(size_t i 0; i index; i ){if(!curr) throw std::out_of_range(Index out of range!);curr curr-next;}return curr-data;}这里返回值设置为引用是考虑到一下情况
myList testList;
testList[2] 4;如果返回的不是引用那么这样的赋值就会失效并不能真的修改掉List的节点元素
6、remove函数删除某个节点 那么这里需要查找到该节点再进行删除而且需要注意它是头尾节点时的情况 void remove(const T val){Node * temp head;while (temp temp-data ! val){temp temp-next;}if(!temp) return;if(temp ! head temp ! tail){temp-prev-next temp-next;temp-next-prev temp-prev;}else if(temp head temp tail){head nullptr;tail nullptr;}else if(temp head){head temp-next;head-prev nullptr;}else{tail temp-prev;tail-next nullptr;}current_size --;delete temp;temp nullptr;}7、find函数查找某个值对应的节点 循环遍历对比就行 Node * getNode(const T val){Node * node head;while (node node-data ! val){node node-next;}return node;}T *find(const T val){Node * node getNode(val);if(!node) return nullptr;return node-data;}8、empty函数检查List是否为空 bool empty(){return current_size 0;}其他功能编写
迭代器 Node * begin() { return head; }Node * end() { return nullptr; }const Node * begin() const { return head; }const Node * end() const { return nullptr; }重载符号
template typename T
std::ostream operator(std::ostream os, myListT pt)
{for (auto current pt.begin(); current; current current-next){os current-data;}os std::endl;return os;
}总结
List的编写中难点在于考虑链表为空的情况很多个函数都需要去考虑并且处理头尾节点实际上是个细致的工作并不在于思路上有多难。
在经常增删的情况下用List会比Vector更为合适代价是内存用得比较多空间换时间。
