c++|list使用及深度剖析模拟实现
目录
一、list介绍与使用
1.1 list介绍
①list底层是带头双向循环链表，在任意位置可进行插入和删除的序列式容器。
②list与其他序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。
③与其他序列式容器相比，list的缺陷是不支持任意位置的随机访问，要访问某个元素，必须从已知位置迭代到访问位置，这段迭代则需要额外的线性时间开销，途中，还需要开辟额外空间，来保存每个节点的相关联信息。
1.2 list的使用
list同样也是一个模板类，有了前面的string、vector基础，这里也不在对list的接口做过多解释，而是简单的进行介绍使用一些常见的重要接口，然后再来对其底层进行一个分析与模拟实现。
1.2.1list的构造
| 构造函数 | 接口说明 |
| list(size_type n,const value_type& val = value_type()) | n个val值构造list |
| list() | 构造空list |
| list(const list& x) | 拷贝构造 |
| list(InputIterator first,InputIterator last) | 用[first,last)区间中的元素构造list |
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> lt1;//构造空list
list<double> lt2(3, 2.1);//用3个2.1值构造lt2
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
list<double> lt3(lt2);//拷贝构造，用lt2构造lt3
for (auto e : lt3)
{
cout << e << " ";
}
cout << endl;
list<double> lt4(lt3.begin(), lt3.end());//用迭代器区间中的元素构造lt4
for (auto e : lt4)
{
cout << e << " ";
}
cout << endl;
return 0;
} 
1.2.2iterator
| 函数声明 | 接口说明 |
| begin+end | 返回第一个元素的迭代器+返回最后一个元素的下一个位置的迭代器 |
| rbegin+rend | 返回第一个元素的reverse_iterator，即最后一个元素的下一个位置+返回最后一个元素的reverse_iterator,即第一个元素的位置 |
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<char> ch(5,'a');
list<char>::iterator cit = ch.begin();
list<char>::reverse_iterator rcit = ch.rbegin();
while (cit != ch.end())
{
cout << *cit;
cit++;
}
cout << endl;
while (rcit != ch.rend())
{
cout << *rcit;
rcit++;
}
return 0;
}
1.2.3容量
| 函数声明 | 接口说明 |
| empty | 检测list是否为空，是返回true，否返回false |
| size | 返回list中有效节点的个数 |
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<char> ch(5, 'a');
cout << boolalpha<< ch.empty() << endl;//以bool类型的方式打印，而不是以数字方式
cout << ch.size() << endl;
return 0;
} 
1.2.4元素访问
| 函数声明 | 接口说明 |
| front | 返回list的第一个节点值的引用 |
| back | 返回list的最后一个节点值的引用 |
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<string> ch(5,"a");
cout << ch.front() << endl;
cout << ch.back() << endl;
return 0;
}
1.2.5 元素修改
| 函数声明 | 接口说明 |
| push_front | 头插，在list首元素插入一个值 |
| pop_front | 头删，删除list首元素 |
| push_back | 尾插，在尾部插入一个值 |
| pop_back | 尾删，删除尾部元素 |
| insert | 在迭代器POS位置插入元素，或者一段区间的值 |
| erase | 删除迭代器POS位置的值，或者一段区间的值 |
| swap | 交换两个list中的元素 |
| clear | 清空list中的有效元素 |
int main()
{
list<string> ch(5,"a");
ch.push_front("b");//头插
ch.push_back("c");//尾插
for (auto e : ch)
{
cout << e;
}
cout << endl;
ch.pop_front();//头删
ch.pop_back();//尾删
for (auto e : ch)
{
cout << e;
}
cout << endl;
ch.insert(ch.begin(), "d");//迭代器指向开始位置，头插
ch.insert(ch.end(), ch.begin(), ch.end());//迭代器指向末尾，尾插一段区间的值
for (auto e : ch)
{
cout << e;
}
cout << endl;
ch.erase(ch.begin());//迭代器指向开始位置，头删
for (auto e : ch)
{
cout << e;
}
cout << endl;
list<string> s(3,"s");
s.swap(ch);//交换
for (auto e : ch)
{
cout << e;
}
cout << endl;
for (auto e : s)
{
cout << e;
}
cout << endl;
s.clear();//清空元素
ch.clear();
cout << s.empty() << endl;
cout << ch.empty() << endl;
return 0;
}
二、list的深度剖析及模拟实现
相较于string、vector，list的模拟实现对于迭代器的实现进行了另一层封装，为什么要这样做？
首先，对于，string、vector而言，他们的底层都是连续的，那么，他们对于迭代器的实现，本质上就是对于指针的封装，正因为底层是连续的，所以指针就可以进行加加到下一个连续的地址，然而对于list而言，底层并不是连续的，如果再对迭代器的实现是对指针的封装，想想是不合适的，因为对于链表而言，底层不连续，指针加加，一定会到下一个节点吗？不一定
那么对于list的迭代器可以怎么实现呢？
我们知道，链表访问下一个节点，是用当前节点的next到下一个节点,那么，迭代器的加加，就可以通过重载函数对链表访问下一个节点的方式进行封装，所以，对于list的迭代器的实现，就是对链表的实现玩法进行一个封装。光看这里还是不能理解，那么接下来就对其如何实现进行一个模拟实现。
①在实现list前，我们先得要有一个节点类，用来存放指针，数据
template<class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
ListNode(const T& x = T())
:_next(nullptr)
,_prev(nullptr)
,_data(x)
{}
};
② 接下来就可以实现list的底层，首先对于迭代器的实现就可以单独进行一个封装，我们学习过string、vector、list的迭代器玩法，知道迭代器是属于这些容器的类域，对于list容器而言，迭代器实现成了一个类，要使迭代器属于list的类域，只需在list类中使用迭代器类即可，那么对于自定义类型，编译器会去自动调用其成员函数。
template<class T>
class _list_iterator
{
typedef ListNode<T>* pNode;
typedef _list_iterator<T> Self;
public:
pNode _node;
public:
_list_iterator(pNode node = nullptr)
{
_node = node;
}
_list_iterator(const Self& x)
{
_node = x._node;
}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &(_node->_data);
}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& x)
{
return _node != x._node;
}
bool operator==(const Self& x)
{
return _node == x._node;
}
};
template<class T>
class list
{
typedef ListNode<T> Node;
typedef Node* pNode;
public:
typedef _list_iterator<T> iterator;
public:
//迭代器
iterator begin()//自定义类型成员，编译器会去调用它的成员函数
{
return _head->_next;//即在返回值时，会构造迭代器对象，去调用迭代器的构造函数
}
iterator end()
{
return _head;
}
//构造
list()
{
_head = new Node;
_head->_next = _head->_prev = _head;
}
list(int n, const T& val = T())
{
_head = new Node;
_head->_next = _head->_prev = _head;
pNode cur = _head;
while (n--)
{
pNode node = new Node(val);
cur->_next = node;
_head->_prev = node;
node->_next = _head;
node->_prev = cur;
cur = node;
}
}
template<class T>
list(iterator first, iterator last)
{
pNode cur = _head;
while (first != last)
{
pNode node = new Node;
node->_data = *first;
cur->_next = node;
_head->_prev = node;
node->_next = _head;
node->_prev = cur;
cur = node;
first++;
}
}
list(const list<T>& x)
{
pNode cur = x._head->_next;
_head = new Node;
pNode _cur = _head;
while (cur != x._head)
{
pNode node = new Node;
node->_data = cur->_data;
_cur->_next = node;
_head->_prev = node;
node->_next = _head;
node->_prev = _cur;
_cur = node;
cur = cur->_next;
}
}
list<T>& operator=(const list<T> l)
{
if(*this != &l)
swap(l);
return *this;
}
~list()
{
pNode cur = _head->_next;
pNode next = cur;
while (cur != _head)
{
next = next->_next;
delete cur;
cur = next;
}
_head->_next = _head->_prev = _head;
}
private:
Node* _head;
}上述代码迭代器的实现就是对于链表的玩法进行封装，通过重载函数进行一个包装。其实透过代码还是比较难以理解，接下来再结合图进行解释。
对于list对象，其成员_head属于自定义类型，类型是节点类，编译器会去调用自定义类型的成员函数，在构造list对象时调用list对应的构造函数，此时就会创建节点，如下图：
构造迭代器对象时，本质上就是其成员_node指向了list对象的成员_head所指向的结点_head->_next，那么是如何指向的，如下图：
那么结合以上两点，迭代器对象的成员_node 指向和list对象的_head成员指向就可以用一张图来解释
③返向迭代器+list剩余函数实现
其实反向迭代器的实现跟正向迭代器的形式是一样的，不同的就是指向问题，反向迭代器可以通过
正向迭代器来实现,改变其指向即可如下：
template<class Iterator>
struct _list_reverse_iterator
{
Iterator _it;
typedef _list_reverse_iterator<Iterator> Self;
_list_reverse_iterator(Iterator it)
:_it(it)
{}
Iterator& operator*()
{
Iterator tmp(_it);
return *(--tmp);
}
Iterator* operator->()
{
return &(operator*());
}
Self& operator++()
{
_it--;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_it--;
return tmp;
}
Self& operator--()
{
_it++;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_it++;
return tmp;
}
bool operator!=(const Self& x)
{
return _it != x._it;
}
bool operator==(const Self& x)
{
return _it == x._it;
}
};
template<class T>
class list
{
typedef ListNode<T> Node;
typedef Node* pNode;
public:
typedef _list_iterator<T> iterator;
typedef _list_reverse_iterator<iterator> reverse_iterator;
public:
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
...
private:
Node* _head;
}对于迭代器的const成员，修饰的主要是不能对重载函数的修改，那么又要加上模板参数，为了达到一个巧妙，对于迭代器的实现可以挂几个模板参数，那么对于迭代器的实例化，就可以实例成自己想要的类型。
#include <iostream>
#include <assert.h>
using namespace std;
namespace bite
{
//节点类
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, class ref, class ptr>
//class _list_reverse_iterator
//{
//typedef ListNode<T>* pNode;
//typedef _list_reverse_iterator<T, ref, ptr> Self;
//public:
//pNode _node;
//public:
//_list_reverse_iterator(pNode node = nullptr)
//{
//_node = node;
//}
//_list_reverse_iterator(const Self& x)
//{
//_node = x._node;
//}
//ref operator*()
//{
//return _node->_prev->_data;
//}
//ptr operator->()
//{
//return &(_node->_prev->_data);
//}
//Self& operator++()
//{
//_node = _node->_prev;
//return *this;
//}
//Self operator++(int)
//{
//Self tmp(*this);
//_node = _node->_prev;
//return tmp;
//}
//Self& operator--()
//{
//_node = _node->_next;
//return *this;
//}
//Self operator--(int)
//{
//Self tmp(*this);
//_node = _node->_next;
//return tmp;
//}
//bool operator!=(const Self& x)
//{
//return _node != x._node;
//}
//bool operator==(const Self& x)
//{
//return _node == x._node;
//}
//};
template<class T,class ref,class ptr>
class _list_iterator
{
typedef ListNode<T>* pNode;
typedef _list_iterator<T,ref,ptr> Self;
public:
pNode _node;
public:
_list_iterator(pNode node = nullptr)
{
_node = node;
}
_list_iterator(const Self& x)
{
_node = x._node;
}
ref operator*()
{
return _node->_data;
}
ptr operator->()
{
return &(_node->_data);
}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& x)
{
return _node != x._node;
}
bool operator==(const Self& x)
{
return _node == x._node;
}
};
template<class Iterator, class Ref, class Ptr>
struct _list_reverse_iterator
{
Iterator _it;
typedef _list_reverse_iterator<Iterator, Ref, Ptr> Self;
_list_reverse_iterator(Iterator it)
:_it(it)
{}
Ref operator*()
{
Iterator tmp(_it);
return *(--tmp);
}
Ptr operator->()
{
return &(operator*());
}
Self& operator++()
{
_it--;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_it--;
return tmp;
}
Self& operator--()
{
_it++;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_it++;
return tmp;
}
bool operator!=(const Self& x)
{
return _it != x._it;
}
bool operator==(const Self& x)
{
return _it == x._it;
}
};
template<class T>
class list
{
typedef ListNode<T> Node;
typedef Node* pNode;
public:
typedef _list_iterator<T,T&,T*> iterator;
typedef _list_iterator<T, const T&,const T*> const_iterator;
typedef _list_reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef _list_reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
public:
//构造
list()
{
_head = new Node;
_head->_next = _head->_prev = _head;
}
list(int n, const T& val = T())
{
_head = new Node;
_head->_next = _head->_prev = _head;
pNode cur = _head;
while (n--)
{
pNode node = new Node(val);
cur->_next = node;
_head->_prev = node;
node->_next = _head;
node->_prev = cur;
cur = node;
}
}
template<class T>
list(iterator first, iterator last)
{
pNode cur = _head;
while (first != last)
{
pNode node = new Node;
node->_data = *first;
cur->_next = node;
_head->_prev = node;
node->_next = _head;
node->_prev = cur;
cur = node;
first++;
}
}
list(const list<T>& x)
{
pNode cur = x._head->_next;
_head = new Node;
pNode _cur = _head;
while (cur != x._head)
{
pNode node = new Node;
node->_data = cur->_data;
_cur->_next = node;
_head->_prev = node;
node->_next = _head;
node->_prev = _cur;
_cur = node;
cur = cur->_next;
}
}
list<T>& operator=(const list<T> l)
{
if(*this != &l)
swap(l);
return *this;
}
~list()
{
pNode cur = _head->_next;
pNode next = cur;
while (cur != _head)
{
next = next->_next;
delete cur;
cur = next;
}
_head->_next = _head->_prev = _head;
}
//迭代器
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
const_reverse_iterator rend() const
{
returnconst_reverse_iterator(begin());
}
//容量
size_t size() const
{
size_t count = 0;
pNode cur = _head->_next;
while (cur != _head)
{
cur = cur->_next;
count++;
}
return count;
}
bool empty() const
{
return _head == _head->_next && _head == _head->_prev;
}
//元素获取
T& front()
{
return _head->_next->_data;
}
const T& front() const
{
return _head->_next->_data;
}
T& back()
{
return _head->_prev->_data;
}
const T& back() const
{
return _head->_prev->_data;
}
//元素修改
void push_back(const T& val)
{
insert(end(), val);
}
void pop_back()
{
/*assert(_head->_next != _head && _head->_prev != _head);
pNode node = _head->_prev;
_head->_prev = node->_prev;
node->_prev->_next = _head;
delete node;*/
erase(--end());
}
void push_front(const T& val)
{
insert(begin(), val);
}
void pop_front()
{
/*assert(_head->_next != _head && _head->_prev != _head);
pNode node = _head->_next;
_head->_next = node->_next;
node->_next->_prev = _head;
delete node;*/
erase(begin());
}
iterator insert(iterator pos, const T& val)
{
pNode cur = pos._node;
pNode prev = cur->_prev;
pNode node = new Node(val);
node->_next = prev->_next;
prev->_next = node;
cur->_prev = node;
node->_prev = prev;
return node;
}
iterator erase(iterator pos)
{
assert(pos != end());
pNode cur = pos._node;
pNode next = cur->_next;
cur->_prev->_next = next;
next->_prev = cur->_prev;
delete cur;
return next;
}
void clear()
{
pNode cur = _head->_next;
pNode next = cur;
while (cur != _head)
{
next = next->_next;
delete cur;
cur = next;
}
_head->_next = _head->_prev = _head;
}
void swap(list<T> l)
{
std::swap(_head, l._head);
}
private:
Node* _head;
};
void listtest()
{
list<int> i(3, 2);
for (auto e : i)
{
cout << e;
}
cout << endl;
list<int>::iterator it = i.begin();
while (it != i.end())
{
cout << *it;
it++;
}
cout << endl;
cout << i.size() << endl;
cout << i.empty() << endl;
list<int> j = i;
for (auto e : i)
{
cout << e;
}
cout << endl;
}
void listtest1()
{
list<string> s(1, "a");
s.push_back("c");
s.push_back("d");
s.push_back("c");
s.push_back("c");
list<string>::reverse_iterator it = s.rbegin();
while (it != s.rend())
{
cout << *it;
it++;
}
cout << endl;
}
}
int main()
{
bite::listtest();
bite::listtest1();
return 0;
}
三、list与vector的对比
vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：
| vector | list | |
| 底层结构 | 动态顺序表，一段连续空间 | 带头节点双向循环链表 |
| 随机访问 | 支持随机访问，时间复杂度为O(1) | 不支持随机访问，时间复杂度为O(N) |
| 插入和删除 | 任意位置插入和删除效率低，需要移动元素，时间复杂度为O(N),插入时可能需要增容，则需开辟新空间，将元素拷贝过去，效率低 | 任意位置插入和删除效率高，不需要移动元素，时间复杂度为O(1) |
| 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点为动态开辟的空间，不连续，容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭代器 | 原生态指针（例如，char*,int*,string*等） | 对原生态指针(节点指针)进行封装 |
| 迭代器失效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，导致原来迭代器失效，删除元素时，当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
| 使用场景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量插入和删除操作，不关系随机访问 |
原文地址：https://blog.csdn.net/weixin_68201503/article/details/137396354
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！