STL源码分析list

作者：手机用户2602908893 | 来源：互联网 | 2023-10-13 04:25

相较于vector的连续线性空间，list就显得复杂许多，它的好处是每次插入或删除一个元素，就配置或释放一个元素空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，

相较于vector的连续线性空间，list就显得复杂许多，它的好处是每次插入或删除一个元素，就配置或释放一个元素空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素移除，list永远是常数时间。
list不仅是一个双向链表，而且还是一个环状双向链表。另外，还有一个重要性质，插入操作和接合操作都不会造成原有的list迭代器失效，这在vector是不成立的。因为vector的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效。甚至list的元素删除操作（erase），也只有“指向被删除元素”的那个迭代器失效，其他迭代器不受任何影响。
以下是list的节点、迭代器数据结构设计以及list的源码剖析：

[cpp] view plaincopy

////////////////////////////////////////////////////////////////////////////////
// list结点, 提供双向访问能力
////////////////////////////////////////////////////////////////////////////////
// -------- -------- -------- --------
// | next |---------->| next |---------->| next |---------->| next |
// -------- -------- -------- --------
// | prev |<----------| prev |<----------| prev |<----------| prev |
// -------- -------- -------- --------
// | data | | data | | data | | data |
// -------- -------- -------- --------
////////////////////////////////////////////////////////////////////////////////
template <class T>
struct __list_node
{
typedef void* void_pointer;
void_pointer next;
void_pointer prev;
T data;
};
// 至于为什么不使用默认参数, 这个是因为有一些编译器不能提供推导能力,
// 而作者又不想维护两份代码, 故不使用默认参数
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef __list_iterator iterator; // STL标准强制要求
typedef __list_iterator self;
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef __list_node* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
link_type node; //迭代器内部当然要有一个普通指针，指向list的节点
__list_iterator(link_type x) : node(x) {}
__list_iterator() {}
__list_iterator(const iterator& x) : node(x.node) {}
// 在STL算法中需要迭代器提供支持
bool operator==(const self& x) const { return node == x.node; }
bool operator!=(const self& x) const { return node != x.node; }
// 以下对迭代器取值（dereference）,取的是节点的数据值
reference operator*() const { return (*node).data; }
// 以下是迭代器的成员存取运算子的标准做法
pointer operator->() const { return &(operator*()); }
// 前缀自加，对迭代器累加1，就是前进一个节点
self& operator++()
{
node = (link_type)((*node).next);
return *this;
}
// 后缀自加, 需要先产生自身的一个副本, 然会再对自身操作, 最后返回副本
self operator++(int)
{
self tmp = *this;
++*this;
return tmp;
}
// 前缀自减
self& operator--()
{
node = (link_type)((*node).prev);
return *this;
}
self operator--(int)
{
self tmp = *this;
--*this;
return tmp;
}
};
////////////////////////////////////////////////////////////////////////////////
// list不仅是个双向链表, 而且还是一个环状双向链表
////////////////////////////////////////////////////////////////////////////////
// end() 头结点 begin()
// ↓ ↓ ↓
// -------- -------- -------- --------
// ---->| next |---------->| next |---------->| next |---------->| next |------
// | -------- -------- -------- -------- |
// | --| prev |<----------| prev |<----------| prev |<----------| prev |<--| |
// | | -------- -------- -------- -------- | |
// | | | data | | data | | data | | data | | |
// | | -------- -------- -------- -------- | |
// | | | |
// | | -------- -------- -------- -------- | |
// ---|-| next |<----------| next |<----------| next |<----------| next |<--|--
// | -------- -------- -------- -------- |
// ->| prev |---------->| prev |---------->| prev |---------->| prev |----
// -------- -------- -------- --------
// | data | | data | | data | | data |
// -------- -------- -------- --------
////////////////////////////////////////////////////////////////////////////////
// 默认allocator为alloc, 其具体使用版本请参照
template <class T, class Alloc = alloc>
class list
{
protected:
typedef void* void_pointer;
typedef __list_node list_node;
// 专属之空间配置器，每次配置一个节点大小
typedef simple_alloc list_node_allocator;
public:
typedef T value_type;
typedef value_type* pointer;
typedef value_type& reference;
typedef list_node* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef __list_iterator iterator;
protected:
link_type node ; // 只要一个指针，便可表示整个环状双向链表
// 分配一个新结点, 注意这里并不进行构造,
// 构造交给全局的construct, 见
link_type get_node() { return list_node_allocator::allocate(); }
// 释放指定结点, 不进行析构, 析构交给全局的destroy
void put_node(link_type p) { list_node_allocator::deallocate(p); }
// 产生（配置并构造）一个节点, 首先分配内存, 然后进行构造
// 注: commit or rollback
link_type create_node(const T& x)
{
link_type p = get_node();
construct(&p->data, x);
return p;
}
// 析构结点元素, 并释放内存
void destroy_node(link_type p)
{
destroy(&p->data);
put_node(p);
}
protected:
// 用于空链表的建立
void empty_initialize()
{
node = get_node(); // 配置一个节点空间，令node指向它
node->next = node; // 令node头尾都指向自己，不设元素值
node->prev = node;
}
// 创建值为value共n个结点的链表
// 注: commit or rollback
void fill_initialize(size_type n, const T& value)
{
empty_initialize();
__STL_TRY
{
// 此处插入操作时间复杂度O(1)
insert(begin(), n, value);
}
__STL_UNWIND(clear(); put_node(node));
}
public:
list() { empty_initialize(); }
iterator begin() { return (link_type)((*node).next); }
// 链表成环, 当指所以头节点也就是end
iterator end() { return node; }
// 头结点指向自身说明链表中无元素
bool empty() const { return node->next == node; }
// 使用全局函数distance()进行计算, 时间复杂度O(n)
size_type size() const
{
size_type result = 0;
distance(begin(), end(), result);
return result;
}
size_type max_size() const { return size_type(-1); }
reference front() { return *begin(); }
reference back() { return *(--end()); }
////////////////////////////////////////////////////////////////////////////////
// 在指定位置插入元素
////////////////////////////////////////////////////////////////////////////////
// insert(iterator position, const T& x)
// ↓
// create_node(x)
// p = get_node();-------->list_node_allocator::allocate();
// construct(&p->data, x);
// ↓
// tmp->next = position.node;
// tmp->prev = position.node->prev;
// (link_type(position.node->prev))->next = tmp;
// position.node->prev = tmp;
////////////////////////////////////////////////////////////////////////////////
iterator insert(iterator position, const T& x)
{
link_type tmp = create_node(x); // 产生一个节点
// 调整双向指针，使tmp插入进去
tmp->next = position.node;
tmp->prev = position.node->prev;
(link_type(position.node->prev))->next = tmp;
position.node->prev = tmp;
return tmp;
}
// 指定位置插入n个值为x的元素, 详细解析见实现部分
void insert(iterator pos, size_type n, const T& x);
void insert(iterator pos, int n, const T& x)
{
insert(pos, (size_type)n, x);
}
void insert(iterator pos, long n, const T& x)
{
insert(pos, (size_type)n, x);
}
// 在链表前端插入结点
void push_front(const T& x) { insert(begin(), x); }
// 在链表最后插入结点
void push_back(const T& x) { insert(end(), x); }
// 移除迭代器position所指节点
iterator erase(iterator position)
{
link_type next_node = link_type(position.node->next);
link_type prev_node = link_type(position.node->prev);
prev_node->next = next_node;
next_node->prev = prev_node;
destroy_node(position.node);
return iterator(next_node);
}
// 擦除一个区间的结点, 详细解析见实现部分
iterator erase(iterator first, iterator last);
void resize(size_type new_size, const T& x);
void resize(size_type new_size) { resize(new_size, T()); }
void clear();
// 删除链表第一个结点
void pop_front() { erase(begin()); }
// 删除链表最后一个结点
void pop_back()
{
iterator tmp = end();
erase(--tmp);
}
list(size_type n, const T& value) { fill_initialize(n, value); }
list(int n, const T& value) { fill_initialize(n, value); }
list(long n, const T& value) { fill_initialize(n, value); }
~list()
{
// 释放所有结点 // 使用全局函数distance()进行计算, 时间复杂度O(n)
size_type size() const
{
size_type result = 0;
distance(begin(), end(), result);
return result;
}
clear();
// 释放头结点
put_node(node);
}
list& operator=(const list& x);
protected:
////////////////////////////////////////////////////////////////////////////////
// 将[first, last)内的所有元素移动到position之前
// 如果last == position, 则相当于链表不变化, 不进行操作
////////////////////////////////////////////////////////////////////////////////
// 初始状态
// first last
// ↓ ↓
// -------- -------- -------- -------- -------- --------
// | next |-->| next |-->| next | | next |-->| next |-->| next |
// ... -------- -------- -------- ... -------- -------- -------- ...
// | prev |<--| prev |<--| prev | | prev |<--| prev |<--| prev |
// -------- -------- -------- -------- -------- --------
//
// position
// ↓
// -------- -------- -------- -------- -------- --------
// | next |-->| next |-->| next |-->| next |-->| next |-->| next |
// ... -------- -------- -------- -------- -------- -------- ...
// | prev |<--| prev |<--| prev |<--| prev |<--| prev |<--| prev |
// -------- -------- -------- -------- -------- --------
//
// 操作完成后状态
// first
// |
// --------------|--------------------------------------
// | ------------|------------------------------------ | last
// | | ↓ | | ↓
// -------- | | -------- -------- -------- | | -------- --------
// | next |-- | ----->| next |-->| next | | next |----- | -->| next |-->| next |
// ... -------- | | -------- -------- ... -------- | | -------- -------- ...
// | prev |<--- | ---| prev |<--| prev | | prev |<-- | -----| prev |<--| prev |
// -------- | | -------- -------- -------- | | -------- --------
// | | | |
// | ------ | |
// ------- | ------------------------------ |
// | | | |
// | | | -----------------------------
// | | | |
// | | | | position
// | | | | ↓
// -------- -------- | | | | -------- -------- -------- --------
// | next |-->| next |-- | | -->| next |-->| next |-->| next |-->| next |
// ... -------- -------- | | -------- -------- -------- -------- ...
// | prev |<--| prev |<--- ------| prev |<--| prev |<--| prev |<--| prev |
// -------- -------- -------- -------- -------- --------
////////////////////////////////////////////////////////////////////////////////
void transfer(iterator position, iterator first, iterator last)
{
if (position != last) // 如果last == position, 则相当于链表不变化, 不进行操作
{
(*(link_type((*last.node).prev))).next = position.node;
(*(link_type((*first.node).prev))).next = last.node;
(*(link_type((*position.node).prev))).next = first.node;
link_type tmp = link_type((*position.node).prev);
(*position.node).prev = (*last.node).prev;
(*last.node).prev = (*first.node).prev;
(*first.node).prev = tmp;
}
}
public:
// 将链表x移动到position所指位置之前
void splice(iterator position, list& x)
{
if (!x.empty())
transfer(position, x.begin(), x.end());
}
// 将链表中i指向的内容移动到position之前
void splice(iterator position, list&, iterator i)
{
iterator j = i;
++j;
if (position == i || position == j) return;
transfer(position, i, j);
}
// 将[first, last}元素移动到position之前
void splice(iterator position, list&, iterator first, iterator last)
{
if (first != last)
transfer(position, first, last);
}
void remove(const T& value);
void unique();
void merge(list& x);
void reverse();
void sort();
};
// 销毁所有结点, 将链表置空
template <class T, class Alloc>
void list::clear()
{
link_type cur = (link_type) node->next;
while (cur != node)
{
link_type tmp = cur;
cur = (link_type) cur->next;
destroy_node(tmp);
}
// 恢复node原始状态
node->next = node;
node->prev = node;
}
// 链表赋值操作
// 如果当前容器元素少于x容器, 则析构多余元素,
// 否则将调用insert插入x中剩余的元素
template <class T, class Alloc>
list& list::operator=(const list& x)
{
if (this != &x)
{
iterator first1 = begin();
iterator last1 = end();
const_iterator first2 = x.begin();
const_iterator last2 = x.end();
while (first1 != last1 && first2 != last2) *first1++ = *first2++;
if (first2 == last2)
erase(first1, last1);
else
insert(last1, first2, last2);
}
return *this;
}
// 移除容器内所有的相邻的重复结点
// 时间复杂度O(n)
// 用户自定义数据类型需要提供operator ==()重载
template <class T, class Alloc>
void list::unique()
{
iterator first = begin();
iterator last = end();
if (first == last) return;
iterator next = first;
while (++next != last)
{
if (*first == *next)
erase(next);
else
first = next;
next = first;
}
}
// 假设当前容器和x都已序, 保证两容器合并后仍然有序
template <class T, class Alloc>
void list::merge(list& x)
{
iterator first1 = begin();
iterator last1 = end();
iterator first2 = x.begin();
iterator last2 = x.end();
// 注意：前提是，两个lists都已经递增排序
while (first1 != last1 && first2 != last2)
if (*first2 < *first1)
{
iterator next = first2;
transfer(first1, first2, ++next);
first2 = next;
}
else
++first1;
if (first2 != last2)
transfer(last1, first2, last2);
}

STL源码分析--list

推荐阅读

shell
新浪笔试题

1:有如下一段程序：packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]

蜡笔小新 2024-12-27 19:32:17
tree
次小生成树问题的高效求解

本文探讨了如何通过最小生成树（MST）来计算严格次小生成树。在处理过程中，需特别注意所有边权重相等的情况，以避免错误。我们首先构建最小生成树，然后枚举每条非树边，检查其是否能形成更优的次小生成树。 ... [详细]

蜡笔小新 2024-12-28 13:42:43
io
QUIC协议：快速UDP互联网连接

QUIC（Quick UDP Internet Connections）是谷歌开发的一种旨在提高网络性能和安全性的传输层协议。它基于UDP，并结合了TLS级别的安全性，提供了更高效、更可靠的互联网通信方式。 ... [详细]

蜡笔小新 2024-12-28 12:33:18
go
优化ListView性能

本文深入探讨了如何通过多种技术手段优化ListView的性能，包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]

蜡笔小新 2024-12-28 10:36:30
replace
深入理解 Oracle 存储函数：计算员工年收入

本文介绍如何使用 Oracle 存储函数查询特定员工的年收入。我们将详细解释存储函数的创建过程，并提供完整的代码示例。 ... [详细]

蜡笔小新 2024-12-28 09:49:42
数组
深入理解Cookie与Session会话管理

本文详细介绍了如何通过HTTP响应和请求处理浏览器的Cookie信息，以及如何创建、设置和管理Cookie。同时探讨了会话跟踪技术中的Session机制，解释其原理及应用场景。 ... [详细]

蜡笔小新 2024-12-27 18:20:43
io
深入理解 SQL 视图、存储过程与事务

本文详细介绍了SQL中的视图、存储过程和事务的概念及应用。视图为用户提供了一种灵活的数据查询方式，存储过程则封装了复杂的SQL逻辑，而事务确保了数据库操作的完整性和一致性。 ... [详细]

蜡笔小新 2024-12-27 17:40:42
shell
Linux 自动化安装脚本详解

本文介绍了一款用于自动化部署 Linux 服务的 Bash 脚本。该脚本不仅涵盖了基本的文件复制和目录创建，还处理了系统服务的配置和启动，确保在多种 Linux 发行版上都能顺利运行。 ... [详细]

蜡笔小新 2024-12-27 16:33:32
shell
2023 ARM嵌入式系统全国技术巡讲

2023 ARM嵌入式系统全国技术巡讲旨在分享ARM公司在半导体知识产权(IP)领域的最新进展。作为全球领先的IP提供商，ARM在嵌入式处理器市场占据主导地位，其产品广泛应用于90%以上的嵌入式设备中。此次巡讲将邀请来自ARM、飞思卡尔以及华清远见教育集团的行业专家，共同探讨当前嵌入式系统的前沿技术和应用。 ... [详细]

蜡笔小新 2024-12-28 11:58:48
io
深入解析Android自定义View面试题

本文探讨了Android Launcher开发中自定义View的重要性，并通过一道经典的面试题，帮助开发者更好地理解自定义View的实现细节。文章不仅涵盖了基础知识，还提供了实际操作建议。 ... [详细]

蜡笔小新 2024-12-28 11:15:04
io
Windows服务与数据库交互问题解析

本文探讨了在Windows 10（64位）环境下开发的Windows服务，旨在定期向本地MS SQL Server (v.11)插入记录。尽管服务已成功安装并运行，但记录并未正确插入。我们将详细分析可能的原因及解决方案。 ... [详细]

蜡笔小新 2024-12-28 10:30:14
go
GWT PopupPanel onKeyDownPreview 方法详解与实例

本文详细介绍了 GWT 中 PopupPanel 类的 onKeyDownPreview 方法，提供了多个代码示例及应用场景，帮助开发者更好地理解和使用该方法。 ... [详细]

蜡笔小新 2024-12-28 10:07:27
io
如何通过按钮聚焦ListView的TextCell？ - How to focus ListView's TextCell by button?

IneedtofocusTextCellsonebyoneviaabuttonclick.ItriedlistView.ScrollTo.我需要通过点击按钮逐个关注Tex ... [详细]

蜡笔小新 2024-12-27 17:02:23
io
数据库内核开发入门 | 搭建研发环境的初步指南

本课程将带你从零开始，逐步掌握数据库内核开发的基础知识和实践技能，重点介绍如何搭建OceanBase的开发环境。 ... [详细]

蜡笔小新 2024-12-27 16:38:48
grid
Yii2 GridView 实现列表页数据直接编辑的完整指南

本文详细介绍了如何使用 Yii2 的 GridView 组件在列表页面实现数据的直接编辑功能。通过具体的代码示例和步骤，帮助开发者快速掌握这一实用技巧。 ... [详细]

蜡笔小新 2024-12-27 16:27:52

手机用户2602908893

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章