[ C++ ] STL_list 使用及其模拟实现
本篇博客学习有关STL库中list的使用及其重要接口的模拟实现。
目录
1.list的介绍及使用
1.1 list的介绍
1.2 list的使用
2.list的迭代器
3.list的构造
4. list capacity
5. list常用接口
5.1 insert
5.2 push_front
5.3 push_back
5.4 erase
5.5 pop_front
5.6 pop_back
5.7 swap
5.8 clear
6.list的迭代器失效
7. list 和 vector 的对比
1.list的介绍及使用
1.1 list的介绍
list官方文档介绍
1. list 是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。2. list 的底层是 双向链表结构 ,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。3. list 与 forward_list 非常相似:最主要的不同在于 forward_list 是单链表,只能朝前迭代,已让其更简单高效。4. 与其他的序列式容器相比 (array , vector , deque) , list 通常在任意位置进行插入、移除元素的执行效率更好。5. 与其他序列式容器相比, list 和 forward_list 最大的缺陷是不支持任意位置的随机访问,比如:要访问 list的第6 个元素,必须从已知的位置 ( 比如头部或者尾部 ) 迭代到该位置,在这段位置上迭代需要线性的时间开销;list 还需要一些额外的空间,以保存每个节点的相关联信息 ( 对于存储类型较小元素的大 list 来说这可能是一个重要的因素)
1.2 list的使用
list中的接口比较多,我们只需要熟悉使用常用的接口以及深入研究其背后的原理即可。
2.list的迭代器
list的迭代器是一个自定义类型的指针,该指针指向list中的某个节点
List 的迭代器迭代器有两种实现方式,具体应根据容器底层数据结构实现:1. 原生态指针,比如: vector2. 将原生态指针进行封装,因迭代器使用形式与指针完全相同,因此在自定义的类中必须实现以下 方法:1. 指针可以解引用,迭代器的类中必须重载 operator*()2. 指针可以通过 -> 访问其所指空间成员,迭代器类中必须重载 oprator->()3. 指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int)至于operator--()/operator--(int)释放需要重载,根据具体的结构来抉择,双向链表可以向前 移动,所以需要重载,如果是 forward_list 就不需要重载 --4. 迭代器需要进行是否相等的比较,因此还需要重载 operator==() 与 operator!=()
我们首先实现一个简单的list的iterator
函数声明 | 接口说明 |
begin+ end |
返回第一个元素的迭代器
+
返回最后一个元素下一个位置的迭代器
|
rbegin+ rend |
返回第一个元素的
reverse_iterator,
即
end
位置
,
返回最后一个元素下一个位置的
reverse_iterator,
即
begin
位置
|
注意:
1、begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动。
2、rebegin(end)与rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动。
// T T& T*
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef list_node<T> Node;
typedef __list_iterator<T, Ref, Ptr> self;
Node* _node;
__list_iterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
//返回的是节点数据的地址 AA*
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& it)
{
return _node != it._node;
}
bool operator==(const self& it)
{
return _node == it._node;
}
};
3.list的构造
构造函数(constructor) | 接口说明 |
list()
|
构造空的
list
|
list (size_type n, const value_type& val = value_type())
|
构造的
list
中包含
n
个值为
val
的元素
|
list (const list& x)
|
拷贝构造函数
|
list (InputIterator first, InputIterator last)
|
用
[first, last)
区间中的元素构造
list
|
构造空的list:
list()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
拷贝构造函数:
list(const list<T>& lt)
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
for (auto e : lt)
{
push_back(e);
}
}
用[first, last)区间中的元素构造list:
template <class InputIterator>
list(InputIterator first, InputIterator last)
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
while (first != last)
{
push_back(*first);
++first;
}
}
4. list capacity
函数声明 | 接口说明 |
empty |
检测
list
是否为空,是返回
true
,否则返回
false
|
size |
返回
list
中有效节点的个数
|
5. list常用接口
函数声明
| 接口说明 |
push_front |
在
list
首元素前插入值为
val
的元素
|
pop_front |
删除
list
中第一个元素
|
push_back |
在
list
尾部插入值为
val
的元素
|
pop_back |
删除
list
中最后一个元素
|
insert |
在
list position
位置中插入值为
val
的元素
|
erase |
删除
list position
位置的元素
|
swap |
交换两个
list
中的元素
|
clear |
清空
list
中的有效元素
|
5.1 insert
方法:
1、首先创建一个新节点newnode,赋值为x。
2、创建两个指针,cur指向pos位置的节点,prev指向pos位置之前的节点
3、prev newnode cur 三个指针依次连接,返回newnode的迭代器。
代码实现:
//插入在pos位置之前
iterator insert(iterator pos, const T& x)
{
Node* newNode = new Node(x);
Node* cur = pos._node;
Node* prev = cur->_prev;
//prev newnode cur
prev->_next = newNode;
newNode->_prev = prev;
newNode->_next = cur;
cur->_prev = newNode;
return iterator(newNode);
}
5.2 push_front
方法:
1、我们复用insert即可,头插就是在第一个元素前插入一个元素,因此我们只需要insert(begin(),x)即可
代码实现:
void push_front(const T& x)
{
insert(begin(), x);
}
5.3 push_back
方法:
1、尾插,就是在最后一个节点后插入新节点,我们依然可以复用insert,由于我们实现的list是双向循环链表,因此我们只需要在end前插即可
void push_back(const T& x)
{
//Node* tail = _head->_prev;
//Node* newnode = new Node(x);
_head tail newnode
//tail->_next = newnode;
//newnode->_prev = tail;
//newnode->_next = _head;
//_head->_prev = newnode;
insert(end(), x);
}
5.4 erase
方法:
1、首先创建3个指针,cur指向pos位置的节点,prev指向pos位置的前一个节点,next指向pos位置的后一个节点。
2、让prev和next相互连接
3、delete掉cur,返回next指针指向节点的迭代器
代码实现:
//删除后指向erase(it)之后的节点
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
//prev next
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
5.5 pop_front
头删,复用erase即可
代码实现:
void pop_front()
{
erase(begin());
}
5.6 pop_back
尾删,复用erase即可
void pop_back()
{
erase(--end());
}
5.7 swap
list的swap交换,只要交换两个链表的head,即可讲两个链表相互交换
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}
5.8 clear
方法:
链表的clear:我们需要将链表的每一个节点释放掉,因此我们使用迭代器时erase即可。
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
6.list的迭代器失效
前面说过,此处大家可将迭代器暂时理解成类似于指针, 迭代器失效即迭代器所指向的节点的无效,即该节 点被删除了 。因为 list 的底层结构为带头结点的双向循环链表 ,因此 在 list 中进行插入时是不会导致 list 的迭代 器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响 。
我们来看这段代码:
void TestListIterator1()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array + sizeof(array) / sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
// erase()函数执行后,it所指向的节点已被删除,因此it无效,在下一次使用it时,必须先给其赋值
l.erase(it);
++it;
}
}
void TestListIterator()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array + sizeof(array) / sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
l.erase(it++); // it = l.erase(it);
}
}
7. list 和 vector 的对比
vector
|
list
| |
底
层
结
构
|
动态顺序表,一段连续空间
|
带头结点的双向循环链表
|
随
机
访
问
|
支持随机访问,访问某个元素效率
O(1)
|
不支持随机访问,访问某个元素
效率
O(N)
|
插
入
和
删
除
|
任意位置插入和删除效率低,需要搬移元素,时间复杂
度为
O(N)
,插入时有可能需要增容,增容:开辟新空
间,拷贝元素,释放旧空间,导致效率更低
|
任意位置插入和删除效率高,不
需要搬移元素,时间复杂度为
O(1)
|
空
间
利
用
率
|
底层为连续空间,不容易造成内存碎片,空间利用率
高,缓存利用率高
| 底层节点动态开辟,小节点容易
造成内存碎片,空间利用率低,缓存利用率低
|
迭
代
器
|
原生态指针
|
对原生态指针
(
节点指针
)
进行封装
|
迭
代
器
失
效
|
在插入元素时,要给所有的迭代器重新赋值,因为插入
元素有可能会导致重新扩容,致使原来迭代器失效,删
除时,当前迭代器需要重新赋值否则会失效
|
插入元素不会导致迭代器失效,
删除元素时,只会导致当前迭代
器失效,其他迭代器不受影响
|
使
用
场
景
|
需要高效存储,支持随机访问,不关心插入删除效率
|
大量插入和删除操作,不关心随
机访问
|