C++初阶学习第十一弹——list的用法和模拟实现

目录

一、list的使用

二.list的模拟实现

三.总结

---

一、list的使用

list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向 其前一个元素和后一个元素。

常见的list的函数的使用

std::list<int> It = {1, 2, 3, 4, 5};通过迭代器访问元素：
std::list<int>::iterator it = It.begin();
while (it != It.end()) {std::cout << *it << std::endl;++it;
}在链表尾部插入元素：
It.push_back(6);在链表头部插入元素
It.push_front(0);删除元素
It.remove(3); // 删除值为3的元素
It.erase(it); // 删除迭代器指向的元素排序链表：
It.sort();反转链表：
It.reverse();

 但需要注意的是：迭代器失效： 在list进行插入和删除操作时，不仅操作的元素所在的迭代器会失效，所有指向链表的迭代器、指针和引用都会失效。因此，在进行操作后，需要重新获取有效的迭代器。（vector的使用也要注意这个问题）

二.list的模拟实现

list的迭代器和 string与 vector不太一样，，没有vector那么天生条件优越。需要单独实现一个类，来封装迭代器。

指针可以解引用，迭代器的vector类中必须重载operator*()

指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()

指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)

迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()。

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;namespace wyb {template<class T>struct list_node{T _data;list_node<T>* _prve;list_node<T>* _next;list_node(const T& data = T()):_data(data), _prve(nullptr), _next(nullptr){}};template<class T>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T> self;Node* _node;list_iterator(Node* node):_node(node){}T& operator*(){return _node->_data;}self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prve;return *this;}bool operator!=(const self& s) const{return _node != s._node;}bool operator==(const self& s) const{return _node == s._node;}};template <class T>class list{typedef list_node<T> Node;public:typedef  list_iterator<T> iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}list(){_head = new Node;_head->_prve = _head;_head->_next = _head;_size = 0;}void insert(iterator pos, const T& x){Node* cur = pos._node;Node* prve = cur->_prve;Node* newnode = new Node(x);newnode->_next = cur;cur->_prve = newnode;prve->_next = newnode;newnode->_prve = prve;_size++;}void push_back(const T& x){insert(end(), x);}void front_back(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void  pop_front(){erase(begin());}void erase(iterator pos){assert(pos != end());Node* prve = pos->_node->_prve;Node* next = pos->_node->_next;prve->_next = next;next->_prve = prve;free(pos);_size--;}private:Node* _head;size_t _size;};void test_list(){list<int> It;It.push_back(1);It.push_back(2);It.push_back(3);It.push_back(4);It.push_back(5);list<int>::iterator it=It.begin();while (it != It.end()){cout << *it << " ";++it;}cout << endl;}
}

1、任意位置插入删除时：list可以随意插入删除，但是vector任意位置的插入删除效率低，需要挪动元素，尤其是插入时有时候需要异地扩容，就需要开辟新空间，拷贝元素，释放旧空间，效率很低

2、访问元素时：vector支持随机访问，但是list不支持随机访问
3、迭代器的使用上：vector可以使用原生指针，但是list需要对原生指针进行封装
4、空间利用上：vector使用的是一个连续的空间，空间利用率高，而list使用的是零碎的空间，空间利用率低

三.总结

以上关于list的模拟实现有点不全，我后期我会补充一些进来。又不懂的地方可以随时联系。

创作不易希望大佬点赞关注。