【C++】stl_list深度剖析
list深度剖析
一、list介绍与使用
1.关于list
list即为链表，而且还是双向带头循环链表，其详细介绍参考C++官网
点我
2.list的使用
这里只介绍一下构造函数，其余函数参考官网
| 构造函数（constructor） | 接口说明 |
|---|---|
| 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 |
3.迭代器相关说明
| 迭代器类型 | ++ | - - | +n | -n | 典型容器 |
|---|---|---|---|---|---|
| 输入(Input) | ✅ | ❌ | ❌ | ❌ | 输入流 |
| 输出(Output) | ✅ | ❌ | ❌ | ❌ | 输出流 |
| 前向(Forward) | ✅ | ❌ | ❌ | ❌ | forward_list |
| 双向(Bidirectional) | ✅ | ✅ | ❌ | ❌ | list, set, map |
| 随机访问(Random) | ✅ | ✅ | ✅ | ✅ | vector, deque, array |
list采用的是双向迭代器，而vector采用的是随机访问迭代器，因此list_iterator不支持 +/-，也不支持[]下标
我们来看看sort
显而易见，算法库的sort要的参数是随机访问迭代器，因此，list不能使用sort，但是list有它自己实现的sort
二、list相关接口简述
l.empty() // 是否为空
l.size() // 元素个数
l.max_size() // 最大容量（一般不用）
l.front() // 第一个元素
l.back() // 最后一个元素
l.push_back(10) //尾插10
l.push_front(20) //头插20
l.pop_back() //尾删
l.pop_front() //头删
- insert:指定位置插入
- erase:指定位置删除
- remove:按值删除
- removeif:条件删除
- unique:去重
- reverse:翻转
- merge:合并链表，需要两链表有序，类似于归并
- splice:剪切链表
简要区分：emplace_back与push_back
list<A> lt;
A aa(1,1);
lt.push_back(aa);
lt.push_back(A(2,1));
//lt.push_back(2,2); 这是错误的
lt.emplace_back(aa);
lt.emplace_back(A(2,1));
lt.emplace_back(2,2); //没有问题
emplace_back和push_back前两种插入效率差不多，但是emplace_back可以进行第三种方式进行插入，且效率更高，因为它只进行了构造，而前两种进行了构造加拷贝
关于splice接口
splice就是把一个list的节点直接移动到另一个list
std::list<int> l1 = {1,2,3};
std::list<int> l2 = {4,5};
auto it = l1.begin();
++it;
l1.splice(it, l2);
结果：
l1: 1 4 5 2 3
l2: 空
vector的insert可能会导致迭代器失效，而splice并不会导致迭代器失效，因为splice只是移动指针，并没有发生扩容导致指针指向位置偏移，并不会导致迭代器失效
简述迭代器失效
链表插入数据后并不会发生迭代器失效，但在删除后可能发生
- 插入数据后，原来迭代器指向的位置不会发生改变，故不会发生迭代器失效
- 删除数据后，若删除的是迭代器指向的数据，那么该迭代器失效，其他的迭代器不会产生任何影响
三、源码剖析：根据源码重构list
1.结构分析
要实现list，必须包含三个类，分别是：节点类、迭代器类、链表类，以下list均用List表示
2.节点类实现
//List节点类
template<class T>
struct ListNode
{
ListNode<T>* _prev;
ListNode<T>* _next;
T _data;
};
list节点类包含指向前驱节点指针_prev、指向后继结点的指针_next、节点数据_data，节点使用struct进行封装，是因为后面的程序会频繁调用节点的成员
ListNode(const T& data = T())
:_prev(nullptr),
_next(nullptr),
_data(data)
{ }
这里需要一个节点的构造函数，我们可以将其全部置空，这里的data=T()，对于内置类型也是兼容的
3.迭代器类实现
3.1 成员变量
//List迭代器类
template<class T>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator self;
Node* _pnode;
};
list的迭代器需要一个封装的指针，因为list的空间不是连续的，原生指针难以实现++,- -,解引用等操作，这些需要我们手动去执行
3.2 构造函数
ListIterator(Node* pnode = nullptr)
:_pnode(pnode)
{ }
迭代器本身就是一个封装的指针，因此浅拷贝足够，不需要我们去实现
3.3 operator*
T& operator*() { return _pnode->_data; }
迭代器就是一个封装的指针，解引用需要返回指针指向的数据
3.4 operator++和operator- -
self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
self operator++(int)
{
auto tmp = *this;
_pnode = _pnode->_next;
return tmp;
}
self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
self& operator--(int)
{
auto tmp = *this;
_pnode = _pnode->_prev;
return tmp;
}
这里是前置++、后置++、前置- -、后置- -
3.5 operator==和operator!=
bool operator==(const self& s) const { return s._pnode == _pnode; }
bool operator!=(const self& s) const { return s._pnode != _pnode; }
直接比较指针是否相等
3.6 operator->
T* operator->() { return &(_pnode->_data); }
既然这个迭代器是指针，那就有指针->的方式去访问节点数据
举一个简单的例子：
class A
{
public:
int _a;
int _b;
};
List<A> lt;
List<A>::iterator it=lt.begin();
//取it指向节点的_b元素
cout<<it->_b<<endl;
取_b元素实际上是
it.operator->()->_b
4.List实现
4.1 成员变量
//List类
template<class T>
class List
{
public:
typedef ListNode<T> Node;
private:
Node* _head;
size_t _size;
};
List需要一个指向头结点的指针_head和一个 _size便于统计长度
4.2 构造函数
接下来，我们需要一个构造函数，因为后面链表各种构造方式都需要一个空链表，所以我们先实现一个空链表的构造：先构造一个哨兵头结点，将头结点的前驱和后继都指向自己，将_size置零即可
//空构造
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
//构造
List(){ empty_init(); }
//拷贝构造
list(const list<T>& lt){
empty_init();
for (auto& e : lt)
push_back(e);
}
4.3赋值重载
复制重载可以使用swap的方式完成，这是一种经典且高效的写法，它避免了一个个拷贝的时间消耗，而是在自己的swap中调用库里的swap
void swap(List<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
List<T>& operator=(List<T> lt)
{
swap(lt);
return *this;
}
4.4 析构函数
先写一个clear函数清除节点，再去实现析构，注意：析构要删除头结点，clear不用
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
_size=0;
}
~List()
{
clear();
delete _head;
_head = nullptr;
}
4.5 插入删除
插入删除注意要保持双向链表的结构
void insert(iterator pos,const T& val)
{
Node* cur = pos._pnode;
Node* prev = cur->_prev;
Node* newnode = new Node(val);
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;
++_size;
}
void erase(iterator pos)
{
Node* node = pos._pnode;
if (node == _head) return;
Node* prev = node->_prev;
Node* next = node->_next;
prev->_next = next;
next->_prev = prev;
delete node;
--_size;
}
void push_back(const T& val) { insert(end(), val); }
void pop_back() { if (!empty()) erase(--end()); }
void push_front(const T& val) { insert(begin(), val); }
void pop_front() { if (!empty()) erase(begin()); }
5.const迭代器的实现
要实现const迭代器可以采用复制一份普通迭代器的方法来实现，但是这样代码长度太长了，接下来，我们看一种stl库里实现的方法
看ListIterator类，我们对它的模板参数进行修改，传三个参数，第一个是类型，第二、三个分别是类型的引用和指针，将ListIterator<T, T&, T*>定义为iterator，而const ListIterator<T, const T&, const T*>定义为const_iterator，接下来把之后T&改成Ref，T*改成Ptr即可，这样编译器就能自动识别你要的是iterator还是const_iterator了
//List迭代器类
template<class T,class Ref,class Ptr>
struct ListIterator
{
typedef ListIterator<T, T&, T*> iterator;
typedef const ListIterator<T, const T&, const T*> const_iterator;
typedef ListNode<T> Node;
typedef ListIterator<T, Ref, Ptr> self;
Node* _pnode;
}
6. 关于initializer_list
stl库支持这样的初始化：
list<int> lt={1,2,3,4,5};
这是C++11新增的初始化方式：初始化列表初始化
看看initializer_list是怎样的
看看它的底层：可见，它的底层是_First和_Last两个指针，_First指向第一个元素，_Last指向最后一个元素的下一个位置
因此，我们可以写一个用initializer_list初始化的构造函数
List(std::initializer_list<T> il)
{
empty_init();
for (auto i : il)
{
push_back(i);
}
}
List<int> lt({1,2,3,4}); //lt: 1->2->3->4更多推荐
9
0- 0
已为社区贡献11条内容
所有评论(0)