【C++】list容器
目录
学习途径
在学习list之前，我们可以查询一些相关文档来学习！
文档详情：list文档学习
list的使用
list的一些构造
图：
构造使用示范：
迭代器说明
list中的迭代器和咋们印象中的迭代器一样：
begin指向第一个元素，end指向最后一个元素的后面一个位置！rbegin指向最后一个元素，rbegin指向第一个元素的前一个位置！
使用的时候要注意：
接口使用
常用接口
这里不做代码示范！比较简单！
迭代器失效问题
迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。
因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入 时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
list和vector对比
模拟实现list
迭代器的模拟（重点）
list的迭代器模拟和vector不一样！
因为list底层是带头的双向链表，而链表底层是节点连接而成的，不是连续的空间！
而vector底层是动态数组，是一块连续的空间！
所以我们如何将这一块一块的空间来遍历它！！！
我们可以用一个类包装它，这个类就叫迭代器，上图理解：
理解了这里，其他就水到渠成了！！！
List.h文件
#include<iostream>
#include<assert.h>
namespace ywc
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _next;
list_node<T>* _prev;
list_node(const T& data=T())
:_data(data)
,_next(nullptr)
,_prev(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)
{}
bool operator!=(const Self& s)
{
return _node != s._node;
}
const T& operator*()
{
return _node->_data;
}
Self& operator++()
{
_node = _node->_next;
return *this;
}
};
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->_next = _head;
_head->_prev = _head;
_size = 0;
}
size_t size()
{
return _size;
}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = pos._node->_prev;
Node* newnode = new Node(x);
//prev newnode cur
newnode->_next = cur;
cur->_prev = newnode;
prev->_next = newnode;
newnode->_prev = prev;
++_size;
}
void erase(iterator pos)
{
assert(pos != end());
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
--_size;
}
void pop_back()
{
erase(_head->_prev);
}
void pop_front()
{
erase(begin());
}
bool empty()
{
return _size==0;
}
private:
Node* _head;
size_t _size;
};
}我们下期见！！！
原文地址：https://blog.csdn.net/Qiwaw/article/details/145226454
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！