Clist类的使用及模拟实现
C++—list类的使用及模拟实现
1、list的介绍
list在底层是双向链表，能够进行动态内存分配，与其他容器相比，list的插入删除要更高效。
list的特性
1、list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2、list的底层是带头双向循环链表结构，在节点中通过指针指向其前一个元素和后一个元素。
3、与其他的序列式容器相比(array，vector，deque等)，list通常在任意位置进行插入、移除元素的效率更高。
list的缺陷
list最大的缺陷是不支持任意位置的随机访问
list和vector一样也是类模板。
2、list常用接口函数
2.1 几个构造函数
| 函数声明 | 函数说明 |
|---|---|
| list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
| list() | 构造空的list |
| list (const list& x) | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造list 注意：这里的区间是左闭右开 |
//无参构造
list<int> l1;
//用10个6初始化链表
list<int> l2(10, 6);
//拷贝构造
list<int> ll2(l2);
vector<int> v{ 1,2,3,4 };
//用迭代器区间初始化链表
list<int> l3(v.begin(), v.end());2.1.1 构造函数的模拟实现
无参构造
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
list()
{
empty_init();
}拷贝构造
list(const list<T>& lt)
{
empty_init();
for (const auto& e : lt)
{
push_back(e);
}
}赋值构造
void swap(const list<T>& tmp)
{
std::swap(_head, tmp._head);
}
list<T>& operator=(const list<T> lt)
{
swap(lt);
return *this;
}析构
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}2.2 迭代器
可以暂时将迭代器理解成指针，这个指针指向list中的某个节点。
| 函数声明 | 接口说明 |
|---|---|
| begin + end | 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
| rbegin + rend | 返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置 |
vector<int> v1{ 5,3,10,26,9,22,12,24 };
list<int> l(v1.begin(), v1.end());
auto it = l.begin();
while (it != l.end())
{
cout << *it << " ";
it++;
}
反向迭代
2.2.1 迭代器的模拟实现
与vector不同，list的迭代器不是一个原生指针，而是封装节点指针的类，因为用户只需要得到节点中的数据而不是整个节点。
vector随机访问可以支持像it+5，it[6]这样的形式，而list不能随机访问也就不能使用operator []来访问节点，仅支持++和–操作，这个++和–也不是指针的++和–，所以要把迭代器也封装成一个类，通过重载++、–和解引用等运算符来满足需求。
//先要封装一个结点类
template<class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
ListNode(const T& x = T())
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
};
//封装一个迭代器类
template<class T>
struct __list_iterator
{
typedef ListNode<T> Node;
typedef __list_iterator<T> self;
Node* _node;
__list_iterator(Node* x)
:_node(x)
{}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
//相当于__list_iterator<T> tmp(*this);
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int);
//解引用重载
T& operator*()
{
return _node->_data;
}
//
T operator->()
{
return &_node->_data;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
bool operator==(const self& s);
};迭代器的实现
const_iterator begin()const
{
//这里是单参数类型支持隐式类型转换
//return const_iterator(_head->_next);
return _head->_next;
}
const_iterator end()const
{
return _head;
}
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}2.3 容量相关的函数
| 函数 | 接口说明 |
|---|---|
| empty | 检测list是否为空，是返回true，否则返回false |
| size | 返回list中有效节点的个数 |
这里个函数我们学会使用即可。
3、list的增删查改
访问头部和尾部数据
| 函数 | 功能 |
|---|---|
| front() | 取到头节点数据的引用 |
| back() | 返回尾节点数据的引用 |
3.1 插入insert
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;//这里是为了管理_size
return newnode;
}3.2 删除erase
将待删除的节点的前后节点先保存起来，再删除pos出节点，将前后节点连接起来。
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
--_size;
return next;
}3.3 头插、头删、尾插、尾删
//尾插
void push_back(const T& x)
{
insert(end(), x);
}
//头插
void push_front(const T& x)
{
insert(begin(), x);
}
//尾删
void pop_back()
{
erase(--end());
}
//头删
void pop_front()
{
erase(begin());
}4、list需要注意的点及功能完善
4.1 list迭代器失效问题
list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，pos指向的节点的，改变的只是连接关系，位置始终都是一个位置。
只有在删除时才会失效，这个位置的数据被删除后，连接关系被改变，此位置就不在原链表中了，此时失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
4.2 list的sort排序
由于list是带头结点的双向循环链表，而算法库中的sort底层是快排，需要传入随机访问迭代器，所以list并不能使用算法库的sort。那么list的sort是怎么一回事呢？
list中给了一个适合自己的sort，这个sort实质上是归并排序，但是 直接使用这个sort 比list的数据先push_back到vector中，再使用算法库的sort，排完序后再导入list中的三步 还要慢。
所以我们通常不使用list自己的sort。