当前位置：首页 > news >正文

list容器介绍及模拟实现和与vector比较

news 来源：原创 2025/8/18 14:35:16

list容器介绍

lisy接口

list迭代器的注意事项

迭代器失效

list的模拟实现

list的节点

list的迭代器实现

list的接口实现

vector和list的优缺点

vector优点：

vector缺点：

list优点：

list缺点：

总结：

vector和list都是互补的，它们相辅相成，而这些优点和缺点都是由于它们的底层空间的分布不同造成的，vector是动态开辟的连续空间，而list是不连续的空间，通过节点来相互连接，这些底层特性的不同早就了vector和list的差别，我们应正确理解和应用它们。

list容器介绍

lisy接口

STL库中提供了许多list的接口，它的底层是不连续的空间，和我们学习过的数据结构中的双向链表相似。和其它容器一样，它提供许多接口。例如size函数，头删头插，尾插尾删等函数。

下面我们给出list一些重要接口的说明。

list迭代器的注意事项

list的迭代器是只支持++或者--，不支持连续跳跃例如it+5这些操作，它不是随机迭代器，这是由于它的底层决定的，因为list底层的空间不连续。同样的像vector这些容器的迭代器是随机迭代器，是因为它的底层动态开辟的空间是连续的。

前面说过，此处大家可将迭代器暂时理解成类似于指针， 迭代器失效即迭代器所指向的节点的无

效，即该节点被删除了 。因为 list 的底层结构为带头结点的双向循环链表 ，因此在 list 中进行插入

时是不会导致 list 的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭

代器，其他迭代器不会受到影响 。

迭代器失效

迭代器失效的问题在vector和list两个容器我们来对比一下，首先由于list容器的底层空间不连续，它erase之后仅仅是删除节点的迭代器失效，并不影响其它迭代器，insert之后也不影响其它迭代器，本质是因为底层空间不连续导致的特性，但是vector不同，由于它底层是连续空间，当我们insert之后，如果容器满了，它会进行扩容，而扩容一般都是异地扩容，这时会导致所以指向原来地址的迭代器失效，当空间足够大时，会使插入位置及之后的迭代器失效，这是因为比如原来有一个迭代器指向5这个位置，但是插入之后所以元素向后移动一位，原来指向5的迭代器可能就不再指向5了。因此迭代器失效。

如下图所示，假如有一个it指向4但是,insert一个5之后it会指向5我们称这为迭代器失效。

list的模拟实现

要模拟实现 list ，必须要熟悉 list 的底层结构以及其接口的含义，通过上面的学习，这些内容已基本

掌握，现在我们来模拟实现 list 。

list的节点

template<class T>
struct node
{node(const T&val=T()):_next(nullptr),_prev(nullptr),_data(val){}node<T>* _next;node<T>* _prev;T _data;
};

list的迭代器实现

由于list的一个元素是一个节点，其中包括_next,_prev,_data，所以简单的指针不也实现迭代器的功能了，我们需要自己定义迭代器来满足我们的需求。这本质也是因为list底层的空间不连续导致的。

那么在实现迭代器之前，我们先了解一下迭代器的基本功能有哪些，分别是解引用*it，it++,

it--,++it,--it,!= ,==

下面的迭代器实现还需要注意诸多细节，例如为什么写成node<T>*而不是node*这时因为在类外部（如全局函数、其他类或非成员代码中），node 只是一个 模板名称，不是完整的类型，必须显式指定模板参数，为什么前置++返回引用，后置++为什么不返回引用，这是因为tmp是一个临时变量，它出栈就会被销毁，如果返回引用会返回悬浮引用导致报错。


mplate<class T>struct iterator{node<T>* _node;//指针itreator()
:_node(nullptr){}T& operator*(){
return _node->data;}iterator<T>& operator ++()//括号内无参数是前置++{
_node = _node->_next;
return *this;//这里不能返回_node，原因是_node是一个指针而不是迭代器，这里迭代器是一个结构体需要注意}iterator<T> operator ++(int){
auto tmp = *this;
_node = _node->_next;
return tmp;//tmp出栈销毁，返回引用会出现错误。}iterator<T>& operator--(){
_node = _node->_prev;
return *this;}iterator<T>  operator--(int){
Self tmp(*this);
_node = _node->_prev;return tmp;}bool operator!=(const iterator<T>& s)//比较的是节点的地址是否相同而非值{
if (_node == s._node)return false;
elsereturn true;}bool operator==(const iterator<T>& s){
if (_node == s._node)return true;
elsereturn false;}
};

list的接口实现

实现了list的节点和迭代器之后，我们最后来模拟实现list的一些重要接口来切实体会一下list的实现方式。

	template <class T>class list{public:/*list():_head(nullptr),_size(0)这样写不对的原因是没有创建头节点，直接把头节点为空了{}*/iterator<T> begin(){return iterator<T>(_head->_next);//如果直接返回_head->_next就要发生饮食类型转换}iterator<T> end(){return iterator<T>(_head);//如果直接返回_head就要发生饮食类型转换}void empty_init(){_head = new node<T>;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}~list(){clear();delete _head;_head = nullptr;_size = 0;}void clear(){auto it = begin();while (it != end()){it=erase(it);}}size_t size(){return _size;}void insert(iterator pos, const T& x){//12 <-5->  34auto newnode = new node<T>(x);//返回的是一个地址newnode->_next = pos._node;//pos._node是地址newnode->_prev = pos._node->_prev;pos._node->_prev = newnode;newnode->_prev->_next = newnode;++_size;}iterator<T> erase(iterator pos){//1234auto next = pos._node->_next;auto prev = pos._node->_prev;next->_prev = prev;prev->_next = next;delete pos._ndoe;--_size;return next;//这里就发生隐式类型转换}void pop_front()//头删{erase(begin());}void pop_back()//尾删{erase(--end());}void push_back(const T& val)//尾插{insert(end(), val);}void push_front(const T& x)//头插{insert(begin(), x);}list(initializer_list<T> il){empty_init();for (auto& e : il){push_back(e);}}// lt2(lt1)//list(const list<T>& lt)list(list<T>& lt)//拷贝构造{empty_init();for (auto& e : lt){push_back(e);}}void swap(list<T>& it){std::swap(_head, it._head);std::swap(_size, it._size);}// lt1 = lt3list<T>& operator=(list<T> lt){swap(lt);return *this;}private:node<T>* _head;size_t _size;};

现在我们实现了整个list的模拟实现。下面我们来比较一下vector和list的区别。

vector和list的优缺点

vector优点：

它支持了下标的访问，访问速度比较快，其次CPU的缓存命中率比较高。

vector缺点：

由于底层是连续的数组，当它在中间删除或者中间插入时，需要移动整个空间，时间复杂度高，效率低下。

list优点：

list由于底层空间不是连续的，所以它的头插头删尾插尾删的时间复杂度都比较低，效率高。

list缺点：

list不支持下标访问，且CPU的缓存命中率低。

list容器介绍

lisy接口

list迭代器的注意事项

迭代器失效

list的模拟实现

list的节点

list的迭代器实现

list的接口实现

vector和list的优缺点

vector优点：

vector缺点：

list优点：

list缺点：

总结：

相关文章：