动手实现C++ STL容器。本节介绍std::list的常见用法和实现。
std::list用法
std::list是C++标准库中的一个容器,它有如下特点:
-
双向链表结构:
std::list
使用双向链表实现,每个元素都包含指向前一个和后一个元素的指针,这使得在列表中间快速插入和删除元素的时间复杂度为O(1)
。 -
非连续内存:与数组不同,
std::list
的元素在内存中不是连续存储的,因为每个元素包含指向前后元素的指针。这意味着在插入和删除操作时,不需要移动大量的元素,这有助于提高性能。 -
无随机访问:由于元素不是在连续内存中存储的,因此不能像数组一样通过索引进行
O(1)
的随机访问。在std::list
中,访问元素需要遍历链表,因此时间复杂度为O(n)
。 -
动态大小:
std::list
的大小可以动态地增长或减小,不需要提前指定容器的大小。 -
高效的插入和删除操作:由于
std::list
是双向链表,它对于在列表的任意位置执行插入和删除操作非常高效。这使得它在需要频繁插入和删除操作的场景中比较有优势。 -
相对较大的存储开销:由于每个元素都需要额外的指针来指向前一个和后一个元素,相较于数组,
std::list
在存储上会有一些额外的开销。 -
不支持随机访问迭代器:
std::list
提供双向迭代器,不支持随机访问迭代器。这与支持随机访问的容器(如std::vector
)不同。
std::list
的一些常用用法如下:
#include <iostream>
#include <list>
template <typename T>
void printList(std::list<T> &list) {
// 遍历列表并输出元素
for (T &x : list) {
std::cout << x << " ";
}
std::cout << std::endl;
}
int main()
{
// 创建一个存储整数的列表
std::list<int> myList;
// 在列表末尾插入元素
std::cout << "Add to the back: ";
myList.push_back(1);
myList.push_back(2);
myList.push_back(3);
printList(myList);
// 在列表开头插入元素
std::cout << "Add to the front: ";
myList.push_front(0);
printList(myList);
// 删除列表末尾的元素
std::cout << "Remove the last element: ";
myList.pop_back();
printList(myList);
// 删除列表开头的元素
std::cout << "Remove the first element: ";
myList.pop_front();
printList(myList);
// 在指定位置插入元素
std::cout << "Insert to the 2nd position: ";
auto it = myList.begin();
++it; // 移动到列表的第二个元素位置
myList.insert(it, 4);
printList(myList);
// 在指定位置删除元素
std::cout << "Remove the 2nd element: ";
it = myList.begin();
++it; // 移动到列表的第二个元素位置
myList.erase(it);
printList(myList);
// 获取列表大小
std::cout << "Size of the list: " << myList.size() << std::endl;
// 检查列表是否为空
if (myList.empty()) {
std::cout << "The list is empty." << std::endl;
} else {
std::cout << "The list is not empty." << std::endl;
}
// 清空列表
std::cout << "Clear the list. " ;
myList.clear();
// 再次检查列表是否为空
if (myList.empty()) {
std::cout << "The list is empty." << std::endl;
} else {
std::cout << "The list is not empty." << std::endl;
}
return 0;
}
运行上面的代码可以得到如下结果:
Add to the back: 1 2 3
Add to the front: 0 1 2 3
Remove the last element: 0 1 2
Remove the first element: 1 2
Insert to the 2nd position: 1 4 2
Remove the 2nd element: 1 2
Size of the list: 2
The list is not empty.
Clear the list. The list is empty.
List实现
接下来我们从零开始实现一个类似于标准库中std::list
的双向链表List
。
链表节点
在开始实现List
之前我们需要先实现一下链表的节点,它通过ListBaseNode
模板来实现:
#ifdef NDEBUG
#define DEBUG_INIT_DEADBEAF(T)
#else
#define DEBUG_INIT_DEADBEAF(T) {(T *)0xdeadbeaf}
#endif
template <class T>
struct ListBaseNode {
ListBaseNode *m_next DEBUG_INIT_DEADBEAF(ListBaseNode);
ListBaseNode *m_prev DEBUG_INIT_DEADBEAF(ListBaseNode);
inline T &value();
inline T const &value() const;
};
ListBaseNode
内部包含m_next
以及m_prev
两个指针,分别指向当前节点的前一个和后一个节点。这里引入了一个调试宏DEBUG_INIT_DEADBEAF
:如果NDEBUG
未被定义(即处于调试模式),DEBUG_INIT_DEADBEAF
会把指针成员初始化为一个特殊的值0xdeadbeaf
以便发现和追踪可能出现的问题。
还需要注意的是这里定义的ListBaseNode
本身是不包含任何数据的,我们通过一个继承自ListBaseNode
的新类ListValueNode
来表示一个携带数据的链表节点:
template <class T>
struct ListValueNode : ListBaseNode<T> {
union {
T m_value;
};
};
template <class T>
inline T &ListBaseNode<T>::value() {
return static_cast<ListValueNode<T> &>(*this).m_value;
}
template <class T>
inline T const &ListBaseNode<T>::value() const {
return static_cast<ListValueNode<T> const &>(*this).m_value;
}
当我们需要获取节点的数据时可以通过value()
函数访问实际值所存储的ListValueNode
类。此时函数会先把当前的ListBaseNode<T>
转换为ListValueNode<T>
类型的指针,然后访问m_value
成员变量并返回所需的数据。
模板定义
List
的模板定义类似于Vector,都包含模板参数T
和Alloc
分别用来指定元素类型和管理内存。List
本身则包含三个成员变量:
m_dummy
为链表的虚拟头节点m_size
用来记录链表的大小m_alloc
用来保存内存分配器
同时,这里还引入了两个类型别名ListNode
和AllocNode
。其中AllocNode
将原本T
类型的内存分配器重新绑定为ListValueNode<T>
类型的内存分配器,这可以方便我们处理节点。
template <class T, class Alloc = std::allocator<T>>
struct List {
private:
using ListNode = ListBaseNode<T>;
using AllocNode = std::allocator_traits<Alloc>::template rebind_alloc<ListValueNode<T>>;
ListNode m_dummy;
size_t m_size;
[[no_unique_address]] Alloc m_alloc;
}
同时,我们还需要引入一些类型别名作为List
的元信息:
template <class T, class Alloc = std::allocator<T>>
struct List {
using value_type = T;
using allocator_type = Alloc;
using size_type = size_t;
using difference_type = ptrdiff_t;
using pointer = T *;
using const_pointer = T const *;
using reference = T &;
using const_reference = T const &;
...
}
为了方便添加和删除节点,这里还定义了两个辅助函数newNode()
和deleteNode()
进行处理:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
private:
ListNode *newNode() {
return AllocNode{m_alloc}.allocate(1);
}
void deleteNode(ListNode *node) noexcept {
AllocNode{m_alloc}.deallocate(static_cast<ListValueNode<T> *>(node), 1);
}
}
构造函数
默认构造函数
List
的默认构造函数用来处理无参数构造的情况。此时整个链表为空,我们需要把m_size
设置为0并让虚拟头节点m_dummy
的前后指针都指向自身。
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
List() noexcept {
m_size = 0;
m_dummy.m_prev = m_dummy.m_next = &m_dummy;
}
explicit List(Alloc const &alloc) noexcept : m_alloc(alloc) {
m_size = 0;
m_dummy.m_prev = m_dummy.m_next = &m_dummy;
}
}
参数化构造函数
另一种常见情况是初始化一个大小为n
、每个节点包含数据val
的链表。为此我们先来实现一个辅助函数_uninit_assign()
:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
private:
void _uninit_assign(size_t n) {
m_size = n;
ListNode *prev = &m_dummy;
while (n) {
ListNode *node = newNode();
prev->m_next = node;
node->m_prev = prev;
std::construct_at(&node->value());
prev = node;
--n;
}
m_dummy.m_prev = prev;
prev->m_next = &m_dummy;
}
void _uninit_assign(size_t n, T const &val) {
m_size = n;
ListNode *prev = &m_dummy;
while (n) {
ListNode *node = newNode();
prev->m_next = node;
node->m_prev = prev;
std::construct_at(&node->value(), val);
prev = node;
--n;
}
m_dummy.m_prev = prev;
prev->m_next = &m_dummy;
}
}
此外,我们再实现一个针对迭代器作为输入参数的版本:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
private:
template <std::input_iterator InputIt>
void _uninit_assign(InputIt first, InputIt last) {
m_size = 0;
ListNode *prev = &m_dummy;
while (first != last) {
ListNode *node = newNode();
prev->m_next = node;
node->m_prev = prev;
std::construct_at(&node->value(), *first);
prev = node;
++first;
++m_size;
}
m_dummy.m_prev = prev;
prev->m_next = &m_dummy;
}
}
完成辅助函数_uninit_assign()
后,我们就可以在参数构造函数中把参数转发给_uninit_assign()
进行初始化:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
explicit List(size_t n, Alloc const &alloc = Alloc()) : m_alloc(alloc) {
_uninit_assign(n);
}
List(size_t n, T const &val, Alloc const &alloc = Alloc()) : m_alloc(alloc) {
_uninit_assign(n, val);
}
template <std::input_iterator InputIt>
List(InputIt first, InputIt last, Alloc const &alloc = Alloc()) {
_uninit_assign(first, last);
}
List(std::initializer_list<T> ilist, Alloc const &alloc = Alloc())
: List(ilist.begin(), ilist.end(), alloc) {}
}
移动构造函数
对于移动构造的情况,我们同样需要先实现一个辅助函数_uninit_move_assign()
:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
private:
void _uninit_move_assign(List &&that) {
auto prev = that.m_dummy.m_prev;
auto next = that.m_dummy.m_next;
prev->m_next = &m_dummy;
next->m_prev = &m_dummy;
m_dummy = that.m_dummy;
that.m_dummy.m_prev = that.m_dummy.m_next = &that.m_dummy;
m_size = that.m_size;
that.m_size = 0;
}
}
这样就可以在移动构造中将参数转发给_uninit_move_assign()
完成初始化:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
List(List &&that) : m_alloc(std::move(that.m_alloc)) {
_uninit_move_assign(std::move(that));
}
List(List &&that, Alloc const &alloc) : m_alloc(alloc) {
_uninit_move_assign(std::move(that));
}
List &operator=(List &&that) {
m_alloc = std::move(that.m_alloc);
clear();
_uninit_move_assign(std::move(that));
return *this;
}
}
拷贝构造函数
List
的拷贝构造函数比较简单,我们可以直接调用前面实现的_uninit_assign()
:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
List(List const &that) : m_alloc(that.m_alloc) {
_uninit_assign(that.cbegin(), that.cend());
}
List(List const &that, Alloc const &alloc) : m_alloc(alloc) {
_uninit_assign(that.cbegin(), that.cend());
}
List &operator=(List const &that) {
assign(that.cbegin(), that.cend());
return *this;
}
List &operator=(std::initializer_list<T> ilist) {
assign(ilist);
return *this;
}
}
实际上这里定义的拷贝构造函数是通过迭代器以及assign()函数来实现的。关于迭代器和assign()函数相关的代码我们会稍后再介绍。
访问元素
List
不允许随机访问,我们只能通过对链表进行遍历的方式来访问其中的元素。这里只需要实现访问链表首尾节点的相关函数即可:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
T &front() noexcept {
return m_dummy.m_next->value();
}
T &back() noexcept {
return m_dummy.m_prev->value();
}
T const &front() const noexcept {
return m_dummy.m_next->value();
}
T const &back() const noexcept {
return m_dummy.m_prev->value();
}
}
迭代器
List
需要实现双向迭代器,为此我们在List
内部定义一个iterator
类:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
struct iterator {
using iterator_category = std::bidirectional_iterator_tag;
using value_type = T;
using difference_type = ptrdiff_t;
using pointer = T *;
using reference = T &;
private:
ListNode *m_curr;
friend List;
explicit iterator(ListNode *curr) noexcept
: m_curr(curr) {}
}
}
对于双向迭代器,iterator
需要实现前缀递增++iterator
、后缀递增iterator++
、前缀递减--iterator
、后缀递减iterator--
、解引用*
、以及比较==
!=
等操作:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
struct iterator {
...
public:
iterator() = default;
iterator &operator++() noexcept { // ++iterator
m_curr = m_curr->m_next;
return *this;
}
iterator operator++(int) noexcept { // iterator++
auto tmp = *this;
++*this;
return tmp;
}
iterator &operator--() noexcept { // --iterator
m_curr = m_curr->m_prev;
return *this;
}
iterator operator--(int) noexcept { // iterator--
auto tmp = *this;
++*this;
return tmp;
}
T &operator*() const noexcept {
return m_curr->value();
}
bool operator!=(iterator const &that) const noexcept {
return m_curr != that.m_curr;
}
bool operator==(iterator const &that) const noexcept {
return !(*this != that);
}
};
}
有了iterator
的实现后就可以实现List
的迭代器行为:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
iterator begin() noexcept {
return iterator{m_dummy.m_next};
}
iterator end() noexcept {
return iterator{&m_dummy};
}
using reverse_iterator = std::reverse_iterator<iterator>;
reverse_iterator rbegin() noexcept {
return std::make_reverse_iterator(end());
}
reverse_iterator rend() noexcept {
return std::make_reverse_iterator(begin());
}
}
类似地,我们还可以实现常量迭代器const_iterator
处理常量迭代的情况:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
struct const_iterator {
using iterator_category = std::bidirectional_iterator_tag;
using value_type = T;
using difference_type = ptrdiff_t;
using pointer = T const *;
using reference = T const &;
private:
ListNode const *m_curr;
friend List;
explicit const_iterator(ListNode const *curr) noexcept
: m_curr(curr) {}
public:
const_iterator() = default;
const_iterator(iterator that) noexcept : m_curr(that.m_curr) {
}
explicit operator iterator() noexcept {
return iterator{const_cast<ListNode *>(m_curr)};
}
const_iterator &operator++() noexcept { // ++iterator
m_curr = m_curr->m_next;
return *this;
}
const_iterator operator++(int) noexcept { // iterator++
auto tmp = *this;
++*this;
return tmp;
}
const_iterator &operator--() noexcept { // --iterator
m_curr = m_curr->m_prev;
return *this;
}
const_iterator operator--(int) noexcept { // iterator--
auto tmp = *this;
++*this;
return tmp;
}
T const &operator*() const noexcept {
return m_curr->value();
}
bool operator!=(const_iterator const &that) const noexcept {
return m_curr != that.m_curr;
}
bool operator==(const_iterator const &that) const noexcept {
return !(*this != that);
}
};
const_iterator cbegin() const noexcept {
return const_iterator{m_dummy.m_next};
}
const_iterator cend() const noexcept {
return const_iterator{&m_dummy};
}
const_iterator begin() const noexcept {
return cbegin();
}
const_iterator end() const noexcept {
return cend();
}
using reverse_const_iterator = std::reverse_iterator<const_iterator>;
reverse_const_iterator crbegin() const noexcept {
return std::make_reverse_iterator(cend());
}
reverse_const_iterator crend() const noexcept {
return std::make_reverse_iterator(cbegin());
}
reverse_const_iterator rbegin() const noexcept {
return crbegin();
}
reverse_const_iterator rend() const noexcept {
return crend();
}
}
修改链表
clear()
clear()
函数的作用是清空当前链表。在调用时clear()
函数会依次访问链表的每个节点,然后清除节点数据并释放节点自身的内存:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
void clear() noexcept {
ListNode *curr = m_dummy.m_next;
while (curr != &m_dummy) {
std::destroy_at(&curr->value());
auto next = curr->m_next;
deleteNode(curr);
curr = next;
}
m_dummy.m_prev = m_dummy.m_next = &m_dummy;
m_size = 0;
}
}
List
的析构函数就是基于clear()
函数实现的:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
~List() noexcept {
clear();
}
}
assign()
assign()
函数的作用类似于参数化构造函数中的_uninit_assign()
。实际上assign()
函数也是基于_uninit_assign()
来实现的,不过要在调用_uninit_assign()
前先清空链表:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
template <std::input_iterator InputIt>
void assign(InputIt first, InputIt last) {
clear();
_uninit_assign(first, last);
}
void assign(std::initializer_list<T> ilist) {
clear();
_uninit_assign(ilist.begin(), ilist.end());
}
void assign(size_t n, T const &val) {
clear();
_uninit_assign(n, val);
}
}
emplace_back()和emplace_front()
emplace_back()
函数的作用是构造一个新的链表节点并将它插入到链表的末尾。类似于Vector
中的实现,这里同样使用了变长参数模板:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
template <class ...Args>
T &emplace_back(Args &&...args) {
ListNode *node = newNode();
ListNode *prev = m_dummy.m_prev;
prev->m_next = node;
node->m_prev = prev;
node->m_next = &m_dummy;
std::construct_at(&node->value(), std::forward<Args>(args)...);
m_dummy.m_prev = node;
++m_size;
return node->value();
}
}
emplace_front()
函数的实现与emplace_back()
基本一致,唯一的区别在于它会把新构造的节点插入到链表头:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
template <class ...Args>
T &emplace_front(Args &&...args) {
ListNode *node = newNode();
ListNode *next = m_dummy.m_next;
next->m_prev = node;
node->m_next = next;
node->m_prev = &m_dummy;
std::construct_at(&node->value(), std::forward<Args>(args)...);
m_dummy.m_next = node;
++m_size;
return node->value();
}
}
push_back()和push_front()
在emplace_back()
和emplace_front()
的基础上就可以很容易地实现push_back()
和push_front()
两个函数:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
void push_back(T const &val) {
emplace_back(val);
}
void push_back(T &&val) {
emplace_back(std::move(val));
}
void push_front(T const &val) {
emplace_front(val);
}
void push_front(T &&val) { // don't repeat yourself (DRY)
emplace_front(std::move(val));
}
}
erase()
erase()
函数的作用是根据迭代器pos
的位置清除指定的节点:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
iterator erase(const_iterator pos) noexcept {
ListNode *node = const_cast<ListNode *>(pos.m_curr);
auto next = node->m_next;
auto prev = node->m_prev;
prev->m_next = next;
next->m_prev = prev;
std::destroy_at(&node->value());
deleteNode(node);
--m_size;
return iterator{next};
}
}
除此之外,我们再实现一个针对迭代范围的版本,它会清除指定范围内的所有节点:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
iterator erase(const_iterator first, const_iterator last) noexcept {
while (first != last) {
first = erase(first);
}
return iterator(first);
}
}
pop_front()和pop_back()
在erase()
函数的基础上我们只需要把begin()
和end()
作为输入参数就可以实现pop_front()
和pop_back()
:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
void pop_front() noexcept {
erase(begin());
}
void pop_back() noexcept {
erase(std::prev(end()));
}
}
remove()
remove()
函数的作用类似于erase()
,不过它是根据值val
来判断是否需要删除节点。remove()
函数会删除链表中所有值为val
的节点:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
size_t remove(T const &val) noexcept {
auto first = begin();
auto last = begin();
size_t count = 0;
while (first != last) {
if (*first == val) {
first = erase(first);
++count;
} else {
++first;
}
}
return count;
}
}
与之类似的还有remove_if()
,它接收一个函数对象pred
作为参数。当pred
在某个节点处进行调用并返回true
时,remove_if()
会将该节点删除:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
template <class Pred>
size_t remove_if(Pred &&pred) noexcept {
auto first = begin();
auto last = begin();
size_t count = 0;
while (first != last) {
if (pred(*first)) {
first = erase(first);
++count;
} else {
++first;
}
}
return count;
}
}
emplace()
emplace()
函数有着和erase()
相反的作用,它可以在迭代器pos
位置创建一个新的节点。类似于emplace_back()
和emplace_front()
,emplace()
同样使用了变长参数模板来实现:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
template <class ...Args>
iterator emplace(const_iterator pos, Args &&...args) {
ListNode *curr = newNode();
ListNode *next = const_cast<ListNode *>(pos.m_curr);
ListNode *prev = next->m_prev;
curr->m_prev = prev;
prev->m_next = curr;
curr->m_next = next;
next->m_prev = curr;
std::construct_at(&curr->value(), std::forward<Args>(args)...);
++m_size;
return iterator{curr};
}
}
insert()
在emplace()
函数的基础上我们可以实现insert()
函数,它用来将值val
插入到pos
位置上:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
iterator insert(const_iterator pos, const T &val) {
return emplace(pos, val);
}
iterator insert(const_iterator pos, T &&val) {
return emplace(pos, std::move(val));
}
iterator insert(const_iterator pos, size_t n, T const &val) {
auto orig = pos;
bool had_orig = false;
while (n) {
pos = emplace(pos, val);
if (!had_orig) {
had_orig = true;
orig = pos;
}
++pos;
--n;
}
return iterator(orig);
}
}
除了上面三种标准用法外,我们还可以针对迭代器输入进行单独处理:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
template <std::input_iterator InputIt>
iterator insert(const_iterator pos, InputIt first, InputIt last) {
auto orig = pos;
bool had_orig = false;
while (first != last) {
pos = emplace(pos, *first);
if (!had_orig) {
had_orig = true;
orig = pos;
}
++pos;
++first;
}
return iterator(orig);
}
iterator insert(const_iterator pos, std::initializer_list<T> ilist) {
return insert(pos, ilist.begin(), ilist.end());
}
}
splice()
splice()
函数可以把另一个List
插入到指定位置上:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
void splice(const_iterator pos, List &&that) {
insert(pos, std::make_move_iterator(that.begin()), std::make_move_iterator(that.end()));
}
}
其它函数
List
中有一些获取链表信息的函数,这里简单汇总一下:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
size_t size() const noexcept {
return m_size;
}
static constexpr size_t max_size() noexcept {
return std::numeric_limits<size_t>::max();
}
Alloc get_allocator() const {
return m_alloc;
}
}
不同List
对象之间的比较我们则可以利用标准库的相关函数来实现:
template <class T, class Alloc = std::allocator<T>>
struct List {
...
public:
bool operator==(List const &that) noexcept {
return std::equal(begin(), end(), that.begin(), that.end());
}
auto operator<=>(List const &that) noexcept {
return std::lexicographical_compare_three_way(begin(), end(), that.begin(), that.end());
}
}
完整实现
总结一下,整个List
的代码可以参考如下:
#pragma once
#include <cstddef>
#include <iterator>
#include <memory>
#include <limits>
#include <stdexcept>
#include <utility>
#include <compare>
#include <initializer_list>
#ifdef NDEBUG
#define DEBUG_INIT_DEADBEAF(T)
#else
#define DEBUG_INIT_DEADBEAF(T) {(T *)0xdeadbeaf}
#endif
template <class T>
struct ListBaseNode {
ListBaseNode *m_next DEBUG_INIT_DEADBEAF(ListBaseNode);
ListBaseNode *m_prev DEBUG_INIT_DEADBEAF(ListBaseNode);
inline T &value();
inline T const &value() const;
};
template <class T>
struct ListValueNode : ListBaseNode<T> {
union {
T m_value;
};
};
template <class T>
inline T &ListBaseNode<T>::value() {
return static_cast<ListValueNode<T> &>(*this).m_value;
}
template <class T>
inline T const &ListBaseNode<T>::value() const {
return static_cast<ListValueNode<T> const &>(*this).m_value;
}
template <class T, class Alloc = std::allocator<T>>
struct List {
using value_type = T;
using allocator_type = Alloc;
using size_type = size_t;
using difference_type = ptrdiff_t;
using pointer = T *;
using const_pointer = T const *;
using reference = T &;
using const_reference = T const &;
private:
using ListNode = ListBaseNode<T>;
using AllocNode = std::allocator_traits<Alloc>::template rebind_alloc<ListValueNode<T>>;
ListNode m_dummy;
size_t m_size;
[[no_unique_address]] Alloc m_alloc;
ListNode *newNode() {
return AllocNode{m_alloc}.allocate(1);
}
void deleteNode(ListNode *node) noexcept {
AllocNode{m_alloc}.deallocate(static_cast<ListValueNode<T> *>(node), 1);
}
public:
List() noexcept {
m_size = 0;
m_dummy.m_prev = m_dummy.m_next = &m_dummy;
}
explicit List(Alloc const &alloc) noexcept : m_alloc(alloc) {
m_size = 0;
m_dummy.m_prev = m_dummy.m_next = &m_dummy;
}
List(List &&that) : m_alloc(std::move(that.m_alloc)) {
_uninit_move_assign(std::move(that));
}
List(List &&that, Alloc const &alloc) : m_alloc(alloc) {
_uninit_move_assign(std::move(that));
}
List &operator=(List &&that) {
m_alloc = std::move(that.m_alloc);
clear();
_uninit_move_assign(std::move(that));
return *this;
}
private:
void _uninit_move_assign(List &&that) {
auto prev = that.m_dummy.m_prev;
auto next = that.m_dummy.m_next;
prev->m_next = &m_dummy;
next->m_prev = &m_dummy;
m_dummy = that.m_dummy;
that.m_dummy.m_prev = that.m_dummy.m_next = &that.m_dummy;
m_size = that.m_size;
that.m_size = 0;
}
public:
List(List const &that) : m_alloc(that.m_alloc) {
_uninit_assign(that.cbegin(), that.cend());
}
List(List const &that, Alloc const &alloc) : m_alloc(alloc) {
_uninit_assign(that.cbegin(), that.cend());
}
List &operator=(List const &that) {
assign(that.cbegin(), that.cend());
return *this;
}
bool empty() noexcept {
return m_dummy.m_prev == m_dummy.m_next;
}
T &front() noexcept {
return m_dummy.m_next->value();
}
T &back() noexcept {
return m_dummy.m_prev->value();
}
T const &front() const noexcept {
return m_dummy.m_next->value();
}
T const &back() const noexcept {
return m_dummy.m_prev->value();
}
explicit List(size_t n, Alloc const &alloc = Alloc()) : m_alloc(alloc) {
_uninit_assign(n);
}
List(size_t n, T const &val, Alloc const &alloc = Alloc()) : m_alloc(alloc) {
_uninit_assign(n, val);
}
template <std::input_iterator InputIt>
List(InputIt first, InputIt last, Alloc const &alloc = Alloc()) {
_uninit_assign(first, last);
}
List(std::initializer_list<T> ilist, Alloc const &alloc = Alloc())
: List(ilist.begin(), ilist.end(), alloc) {}
List &operator=(std::initializer_list<T> ilist) {
assign(ilist);
return *this;
}
private:
template <std::input_iterator InputIt>
void _uninit_assign(InputIt first, InputIt last) {
m_size = 0;
ListNode *prev = &m_dummy;
while (first != last) {
ListNode *node = newNode();
prev->m_next = node;
node->m_prev = prev;
std::construct_at(&node->value(), *first);
prev = node;
++first;
++m_size;
}
m_dummy.m_prev = prev;
prev->m_next = &m_dummy;
}
void _uninit_assign(size_t n, T const &val) {
m_size = n;
ListNode *prev = &m_dummy;
while (n) {
ListNode *node = newNode();
prev->m_next = node;
node->m_prev = prev;
std::construct_at(&node->value(), val);
prev = node;
--n;
}
m_dummy.m_prev = prev;
prev->m_next = &m_dummy;
}
void _uninit_assign(size_t n) {
m_size = n;
ListNode *prev = &m_dummy;
while (n) {
ListNode *node = newNode();
prev->m_next = node;
node->m_prev = prev;
std::construct_at(&node->value());
prev = node;
--n;
}
m_dummy.m_prev = prev;
prev->m_next = &m_dummy;
}
public:
size_t size() const noexcept {
return m_size;
}
static constexpr size_t max_size() noexcept {
return std::numeric_limits<size_t>::max();
}
template <std::input_iterator InputIt>
void assign(InputIt first, InputIt last) {
clear();
_uninit_assign(first, last);
}
void assign(std::initializer_list<T> ilist) {
clear();
_uninit_assign(ilist.begin(), ilist.end());
}
void assign(size_t n, T const &val) {
clear();
_uninit_assign(n, val);
}
void push_back(T const &val) {
emplace_back(val);
}
void push_back(T &&val) {
emplace_back(std::move(val));
}
void push_front(T const &val) {
emplace_front(val);
}
void push_front(T &&val) { // don't repeat yourself (DRY)
emplace_front(std::move(val));
}
template <class ...Args>
T &emplace_back(Args &&...args) {
ListNode *node = newNode();
ListNode *prev = m_dummy.m_prev;
prev->m_next = node;
node->m_prev = prev;
node->m_next = &m_dummy;
std::construct_at(&node->value(), std::forward<Args>(args)...);
m_dummy.m_prev = node;
++m_size;
return node->value();
}
template <class ...Args>
T &emplace_front(Args &&...args) {
ListNode *node = newNode();
ListNode *next = m_dummy.m_next;
next->m_prev = node;
node->m_next = next;
node->m_prev = &m_dummy;
std::construct_at(&node->value(), std::forward<Args>(args)...);
m_dummy.m_next = node;
++m_size;
return node->value();
}
~List() noexcept {
clear();
}
void clear() noexcept {
ListNode *curr = m_dummy.m_next;
while (curr != &m_dummy) {
std::destroy_at(&curr->value());
auto next = curr->m_next;
deleteNode(curr);
curr = next;
}
m_dummy.m_prev = m_dummy.m_next = &m_dummy;
m_size = 0;
}
struct iterator {
using iterator_category = std::bidirectional_iterator_tag;
using value_type = T;
using difference_type = ptrdiff_t;
using pointer = T *;
using reference = T &;
private:
ListNode *m_curr;
friend List;
explicit iterator(ListNode *curr) noexcept
: m_curr(curr) {}
public:
iterator() = default;
iterator &operator++() noexcept { // ++iterator
m_curr = m_curr->m_next;
return *this;
}
iterator operator++(int) noexcept { // iterator++
auto tmp = *this;
++*this;
return tmp;
}
iterator &operator--() noexcept { // --iterator
m_curr = m_curr->m_prev;
return *this;
}
iterator operator--(int) noexcept { // iterator--
auto tmp = *this;
++*this;
return tmp;
}
T &operator*() const noexcept {
return m_curr->value();
}
bool operator!=(iterator const &that) const noexcept {
return m_curr != that.m_curr;
}
bool operator==(iterator const &that) const noexcept {
return !(*this != that);
}
};
struct const_iterator {
using iterator_category = std::bidirectional_iterator_tag;
using value_type = T;
using difference_type = ptrdiff_t;
using pointer = T const *;
using reference = T const &;
private:
ListNode const *m_curr;
friend List;
explicit const_iterator(ListNode const *curr) noexcept
: m_curr(curr) {}
public:
const_iterator() = default;
const_iterator(iterator that) noexcept : m_curr(that.m_curr) {
}
explicit operator iterator() noexcept {
return iterator{const_cast<ListNode *>(m_curr)};
}
const_iterator &operator++() noexcept { // ++iterator
m_curr = m_curr->m_next;
return *this;
}
const_iterator operator++(int) noexcept { // iterator++
auto tmp = *this;
++*this;
return tmp;
}
const_iterator &operator--() noexcept { // --iterator
m_curr = m_curr->m_prev;
return *this;
}
const_iterator operator--(int) noexcept { // iterator--
auto tmp = *this;
++*this;
return tmp;
}
T const &operator*() const noexcept {
return m_curr->value();
}
bool operator!=(const_iterator const &that) const noexcept {
return m_curr != that.m_curr;
}
bool operator==(const_iterator const &that) const noexcept {
return !(*this != that);
}
};
iterator begin() noexcept {
return iterator{m_dummy.m_next};
}
iterator end() noexcept {
return iterator{&m_dummy};
}
const_iterator cbegin() const noexcept {
return const_iterator{m_dummy.m_next};
}
const_iterator cend() const noexcept {
return const_iterator{&m_dummy};
}
const_iterator begin() const noexcept {
return cbegin();
}
const_iterator end() const noexcept {
return cend();
}
using reverse_iterator = std::reverse_iterator<iterator>;
using reverse_const_iterator = std::reverse_iterator<const_iterator>;
reverse_iterator rbegin() noexcept {
return std::make_reverse_iterator(end());
}
reverse_iterator rend() noexcept {
return std::make_reverse_iterator(begin());
}
reverse_const_iterator crbegin() const noexcept {
return std::make_reverse_iterator(cend());
}
reverse_const_iterator crend() const noexcept {
return std::make_reverse_iterator(cbegin());
}
reverse_const_iterator rbegin() const noexcept {
return crbegin();
}
reverse_const_iterator rend() const noexcept {
return crend();
}
iterator erase(const_iterator pos) noexcept {
ListNode *node = const_cast<ListNode *>(pos.m_curr);
auto next = node->m_next;
auto prev = node->m_prev;
prev->m_next = next;
next->m_prev = prev;
std::destroy_at(&node->value());
deleteNode(node);
--m_size;
return iterator{next};
}
iterator erase(const_iterator first, const_iterator last) noexcept {
while (first != last) {
first = erase(first);
}
return iterator(first);
}
void pop_front() noexcept {
erase(begin());
}
void pop_back() noexcept {
erase(std::prev(end()));
}
size_t remove(T const &val) noexcept {
auto first = begin();
auto last = begin();
size_t count = 0;
while (first != last) {
if (*first == val) {
first = erase(first);
++count;
} else {
++first;
}
}
return count;
}
template <class Pred>
size_t remove_if(Pred &&pred) noexcept {
auto first = begin();
auto last = begin();
size_t count = 0;
while (first != last) {
if (pred(*first)) {
first = erase(first);
++count;
} else {
++first;
}
}
return count;
}
template <class ...Args>
iterator emplace(const_iterator pos, Args &&...args) {
ListNode *curr = newNode();
ListNode *next = const_cast<ListNode *>(pos.m_curr);
ListNode *prev = next->m_prev;
curr->m_prev = prev;
prev->m_next = curr;
curr->m_next = next;
next->m_prev = curr;
std::construct_at(&curr->value(), std::forward<Args>(args)...);
++m_size;
return iterator{curr};
}
iterator insert(const_iterator pos, const T &val) {
return emplace(pos, val);
}
iterator insert(const_iterator pos, T &&val) {
return emplace(pos, std::move(val));
}
iterator insert(const_iterator pos, size_t n, T const &val) {
auto orig = pos;
bool had_orig = false;
while (n) {
pos = emplace(pos, val);
if (!had_orig) {
had_orig = true;
orig = pos;
}
++pos;
--n;
}
return iterator(orig);
}
template <std::input_iterator InputIt>
iterator insert(const_iterator pos, InputIt first, InputIt last) {
auto orig = pos;
bool had_orig = false;
while (first != last) {
pos = emplace(pos, *first);
if (!had_orig) {
had_orig = true;
orig = pos;
}
++pos;
++first;
}
return iterator(orig);
}
iterator insert(const_iterator pos, std::initializer_list<T> ilist) {
return insert(pos, ilist.begin(), ilist.end());
}
void splice(const_iterator pos, List &&that) {
insert(pos, std::make_move_iterator(that.begin()), std::make_move_iterator(that.end()));
}
Alloc get_allocator() const {
return m_alloc;
}
bool operator==(List const &that) noexcept {
return std::equal(begin(), end(), that.begin(), that.end());
}
auto operator<=>(List const &that) noexcept {
return std::lexicographical_compare_three_way(begin(), end(), that.begin(), that.end());
}
};