|
目录
一.list使用
1.list构造
2.list迭代器
3.容量操作
4.增删查改
二.list迭代器失效问题
四.list模拟实现总代码
三.list分部模拟实现
1.节点类
2.迭代器封装
3.list本身私有成员与typedef
4.反向迭代器类实现
5.迭代器
6.节点初始化
7.构造
8.拷贝构造
9.赋值操作符重载
10.析构函数
11.clear函数
12.尾插、尾删、头插、头删
13.插入
14.删除
五.list与vector的对比
1. list
2. vector?
前言：list类的学习，可以仿照之前的string类和vector类。（这里的反向迭代器是一个适配器，适配正向迭代器）
一.list使用
在使用之前我们先介绍一下vector：
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，而list更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的list来说这可能是一个重要的因素)
介绍ok，现在开始使用list。
1.list构造
① vector()? ? ? ? 构造空的list
② vector(size_t n, const value_type& val = value_type()) ? ? ? ?构造并初始化n个值为val的元素
③ vector(const vector& x) ? ? ? ?拷贝构造函数
④ vector(InputIterator first, InputIterator last) ? ? ? ?使用迭代器区间中的元素构造list
2.list迭代器
① begin + end ? ? ? ?正向
② rbegin + rend ? ? ? ?反向
③ iterator ? ? ? ?正向迭代器
④ reverse_iterator ? ? ? ?反向迭代器
⑤ const_iterator ? ? ? ?常量迭代器
⑥ const_reverse_iterator ? ? ? ?常量反向迭代器
3.容量操作
① size() ? ? ? ?获取数据个数
③ empty() ? ? ? ?判断是否为空
④ resize() ? ? ? ?改变list的size
4.增删查改
① push_back() ? ? ? ?尾插
② pop_back() ? ? ? ?尾删
③ push_front? ? ? ? 头插
④ pop_front? ? ? ? 头删
⑤ insert ? ? ? ?在pos之前插入
⑥ erase ? ? ? ?删除pos位置的元素
⑦ swap ? ? ? ?交换
⑧ clear? ? ? 清空list中的有效元素
二.list迭代器失效问题
? ? ? ? 因为list的底层结构是带头结点的双向循环链表，因此在list中插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删结点的迭代器，其它迭代器不会受到影响。
正常删除所有的偶数用迭代器实现：
?
void test_list5()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.push_back(6);
// 删除所有的偶数
auto it1 = lt.begin();
while (it1 != lt.end())
{
if (*it1 % 2 == 0)
{
lt.erase(it1);
}
++it1;
}
}
????????如果按照正常的方式去写，那么就会发生迭代器失效问题，当删除该节点后，会自动到下一个节点的位置，这时候再++，就会遗漏掉上一个节点。
修改方式：
void test_list5()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.push_back(6);
// 删除所有的偶数
auto it1 = lt.begin();
while (it1 != lt.end())
{
if (*it1 % 2 == 0)
{
it1 = lt.erase(it1);
}
else
{
++it1;
}
}
}
四.list模拟实现总代码
????????这里实现list要分3个类，一个类是创建链表的节点，一个类是封装迭代器，最后一个类就是list本体实现。
反向迭代器：
#pragma once
namespace hb
{
template <class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
Iterator _it;
typedef Reverse_iterator<Itertor, Ref, Ptr> Self;
Reverse_iterator(Iterator it)
: _it(it)
{}
Ref operator*()
{
Iterator tmp = _it;
return *(--tmp);
}
Ptr operator->()
{
return &(operator*());
}
Self& operator++()
{
--_it;
return *this;
}
Self& operator--()
{
++_it;
return *this;
}
bool operator!=(const Self& s)
{
return _it != s._it;
}
};
}
list：
#pragma once
#include <assert.h>
#include "ReverseIterator.h"
namespace hb
{
template <class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _data;
list_node(const T& val = T())
: _next(nullptr)
, _prev(nullptr)
, _data(val)
{}
};
// typedef __list_iterator<T, T&, T*> iterator;
// typedef __list_iterator<T, const T&, const T*> const_iterator;
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->()
{
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;
}
};
template <class T>
class list
{
typedef list_node<T> Node;
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
// 反向迭代器适配支持
typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin());
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
list()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
void empty_init()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
template <class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
++first;
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}
list(const list<T>& lt)
{
empty_init();
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
void push_back(const T& x)
{
/*Node* tail = _head->_prev;
Node* newnode = new Node(x);
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;*/
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
// 插在pos位置之前
iterator insert(iterator pos, const T& x)
{
Node* newNode = new Node(x);
Node* cur = pos._node;
Node* prev = cur->_prev;
prev->_next = newNode;
newNode->_prev = prev;
newNode->_next = cur;
cur->_prev = newNode;
return iterator(newNode);
}
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;
return iterator(next);
}
private:
Node* _head;
};
}
三.list分部模拟实现
1.节点类
template <class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _data;
list_node(const T& val = T())
: _next(nullptr)
, _prev(nullptr)
, _data(val)
{}
};
2.迭代器封装
? ? ? ? 因为list的迭代器并不是原生指针，因此需要我们自己去封装一个迭代器。
? ? ? ? 首先这里的模板参数中Ref是T&，Ptr是T*，然后将节点类typedef为Node，将自己typedef为self。
? ? ? ? 然后实现构造函数。这里不需要实现拷贝构造和赋值重载函数，默认的浅拷贝就足够了，而析构函数也不需要，因为节点并不属于迭代器这个类，不需要它去释放。
? ? ? ? 再就是依次实现对迭代器操作的各种运算符重载（*? ->? 前置++? 后置++? 前置--? 后置--? !=? ==）。
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->()
{
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本身私有成员与typedef
? ? ? ? 反向迭代器是一个适配器，通过适配iterator。
typedef list_node<T> Node;
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
// 反向迭代器适配支持
typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
private:
Node* _head;
4.反向迭代器类实现
? ? ? ? 反向迭代器的实现是适配正向迭代器的，因为反向迭代器的与正向迭代器几乎一样，因此不需要自己重新实现，只需要适配一下正向迭代器就可以了。
? ? ? ? 这里的operator*的实现是因为_it是哨兵位的头节点，因此创建一个临时变量tmp，让tmp--就是尾节点了。
? ? ? ? ++和--的实现正好是相反的。
template <class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
Iterator _it;
typedef Reverse_iterator<Itertor, Ref, Ptr> Self;
Reverse_iterator(Iterator it)
: _it(it)
{}
Ref operator*()
{
Iterator tmp = _it;
return *(--tmp);
}
Ptr operator->()
{
return &(operator*());
}
Self& operator++()
{
--_it;
return *this;
}
Self& operator--()
{
++_it;
return *this;
}
bool operator!=(const Self& s)
{
return _it != s._it;
}
};
5.迭代器
? ? ? ? 迭代器的begin+end，rbegin+rend接口。
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin());
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
6.节点初始化
? ? ? ? 按照双向循环链表进行初始化。?
void empty_init()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
7.构造
（1）无参构造
list()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
?（2）迭代器区间构造
template <class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
++first;
}
}
8.拷贝构造
? ? ? ? 采用现代写法进行拷贝构造。
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}
list(const list<T>& lt)
{
empty_init();
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}
9.赋值操作符重载
? ? ? ? 现代写法
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
10.析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}
11.clear函数
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
12.尾插、尾删、头插、头删
? ? ? ? 直接通过调用insert和erase实现。
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());
}
13.插入
? ? ? ? 与之前学过的双向链表插入方法相同，最后要返回该节点。
iterator insert(iterator pos, const T& x)
{
Node* newNode = new Node(x);
Node* cur = pos._node;
Node* prev = cur->_prev;
prev->_next = newNode;
newNode->_prev = prev;
newNode->_next = cur;
cur->_prev = newNode;
return iterator(newNode);
}
14.删除
? ? ? ? 与之前相同，最后返回删除掉的节点的下一个节点。
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;
return iterator(next);
}
五.list与vector的对比
1. list
（1）底层结构：带哨兵位头节点的双向循环链表
（2） 随机访问：不支持随机访问，访问某个元素的效率是O（N）
（3）插入和删除：任意位置插入和删除效率高，不需要挪到元素，时间复杂度为O（N）
（4）空间利用率：底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
（5）迭代器：对原生态指针（节点指针）进行封装
（6）迭代器失效：插入元素不会导致迭代器失效；删除元素时，只会导致当前迭代器失效，其它迭代器不受影响
（7）使用场景：大量插入和删除操作，不关心随机访问
2. vector?
（1）底层结构：动态顺序表，是一段连续的空间
（2） 随机访问：支持随机访问，访问某个元素效率是O（1）
（3）插入和删除：任意位置插入和删除效率低，需要挪到元素，随机复杂度为O（N），插入时有可能需要增容（开辟新空间，拷贝元素，释放就空间，导致效率更低）
（4）空间利用率：底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高
（5）迭代器：原生态指针
（6）迭代器失效：在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值，否则会失效
（7）使用场景：需要高效存储，支持随机访问，不关心插入删除效率
|