std::list 学习笔记

list 是类模板，其声明如下

template <class T, class Allocator = std::allocator<T>>
class list;

std::list 是一个容器，它支持从容器中的任何位置进行常数时间的插入和删除元素。不支持快速随机访问。它通常被实现为一个双向链表。与 std::forward_list 相比，此容器提供双向迭代能力，但空间效率较低。

creator

constructor

• 默认构造函数，使用默认构造的分配器构造一个空容器
• 使用给定的分配器 alloc 构造一个空容器
• 构造一个具有 count 个元素的 list，并使用类型的默认值进行初始化
• 构造一个具有 count 个元素的 list，并初始化每个元素为 value
• 构造一个具有 count 个元素的 list，并使用类型的默认值进行初始化，不进行拷贝，原地创建对象
• 通过 range [first, last) 进行初始化
• 拷贝构造
• 移动构造
• 通过初始化列表进行初始化

#include <iostream>
#include <list>

int main() {
    // 默认初始化，构造一个空的容器
    std::list<int> li;
    // 构造一个具有 5 个元素的 list，并使用类型的默认值进行初始化
    std::list<int> li1(5);
    // 构造一个具有 5 个元素的 list，并初始化每个元素为 3
    std::list<int> li2(5, 3);
    // 通过 range [first, last) 进行初始化
    std::list<int> li3(li2.begin(), li2.end());
    // 拷贝构造
    std::list<int> li4(li2);
    // 移动构造
    std::list<int> li5(std::move(li4));
    // 通过初始化列表进行初始化
    std::list<int> li6 { 0, 1, 2, 3, 4};
}

operator=

• 拷贝赋值
• 移动赋值
• 初始化列表赋值

#include <iostream>
#include <list>

int main() {
  std::list<int> li1{1, 2, 3, 4, 5};
  std::list<int> li2;
  std::list<int> li3;
  std::list<int> li4;

  // 通过拷贝进行赋值
  li2 = li1;
  // 通过移动进行赋值
  li3 = std::move(li1);
  // 通过初始化列表进行赋值
  li4 = {5, 4, 3, 2, 1};
}

assign

• 将容器中内容替换为 count 个 value
• 将容器中的内容替换为 range[first, last)
• 将容器中的内容替换为初始化列表中内容

#include <iostream>
#include <list>

int main() {
  std::list<int> li1{1, 2, 3, 4, 5};
  // 将容器中内容替换为 5 个 6
  li1.assign(5, 6);
  // 将容器中的内容替换为 range[first, last)
  std::list<int> li2{1, 4, 9, 16, 25};
  li1.assign(li2.begin(), li2.end());
  // 将容器中的内容替换为初始化列表
  li1.assign({0, 1, 0, 1});
}

元素获取

front

front 返回容器中第一个元素的引用。对空容器调用 front 是未定义的

#include <iostream>
#include <list>

int main() {
  std::list<int> li1{1, 2, 3, 4, 5};
  std::cout << li1.front() << '\n';
  li1.front() = 10;
  std::cout << li1.front() << '\n';
}

back

back 返回容器中第一个元素的引用。对空容器调用 back 是未定义的

#include <iostream>
#include <list>

int main() {
  std::list<int> li1{1, 2, 3, 4, 5};
  std::cout << li1.back() << '\n';
  li1.back() = 10;
  std::cout << li1.back() << '\n';
}

Iterators

• begin
• cbegin
• end
• cend
• rbegin
• crbegin
• rend
• crend

begin 指向 list 的第一个元素，end 指向最后一个元素的下一个元素，cbegin 和 cend 表示 const 类型的迭代器，不允许其指定的元素被修改，rbegin 和 rend 表示反向迭代器

对于反向迭代器（reverse_iterator），可以通过调用 base 获取到其对应的正向迭代器，且满足 &*r == &*(i - 1)，即如果用一个指针表示一个地址，那么地址左边的元素为反向迭代器指向的元素，地址右边为正向迭代器指向的元素

#include <algorithm>
#include <cassert>
#include <iostream>
#include <list>

int main() {
  std::list<int> li1{1, 2, 3, 4, 5};

  // 1 2 3 4 5
  std::for_each(li1.begin(), li1.end(),
                [](const auto n) { std::cout << n << ' '; });

  std::cout << '\n';
  // 5 4 3 2 1
  std::for_each(li1.rbegin(), li1.rend(),
                [](const auto n) { std::cout << n << ' '; });

  std::list<int>::reverse_iterator r = li1.rbegin();
  std::list<int>::iterator i = r.base();
  assert(&*r == &*prev(i));
}

Capacity

empty 检查容器是否为空，当 begin() == end() 时则认为是空

#include <iostream>
#include <list>
#include <iomanip>

int main() {
  std::list<int> li1;
  std::cout << std::boolalpha;
  std::cout << li1.empty() << '\n';  // true
  li1.push_back(1);
  std::cout << li1.empty() << '\n';  // false
}

size

size 获取容器中元素的个数，等效于 std::distance(begin(), end())

#include <iostream>
#include <list>

int main() {
  std::list<int> li1{1, 2, 3, 4, 5};
  std::cout << li1.size() << '\n';  // 5
}

max_size

max_size 获取系统能够存放到容器中的元素最大个数

Modifiers

clear

清除容器中的所有元素，当执行 clear 后，容器中 size 变为 0

#include <iostream>
#include <list>

int main()
{
    std::list<int> li1 {1, 2, 3};
    std::cout << li1.size() << '\n'; // 3
    li1.clear();
    std::cout << li1.size()  << '\n'; // 0
}

insert

• 在指定的 pos 前插入指定值 value，并返回指向插入值的 iterator
• 在指定的 pos 前插入 count 个指定值 value，并返回指向插入的第一个元素的 iterator
• 在指定的 pos 前插入 [first, last)，并返回指向插入的第一个元素的 iterator
• 在指定的 pos 前插入初始化列表，并返回指向插入的第一个元素的 iterator

#include <iostream>
#include <list>

template <typename T>
void print(const std::list<T>& li) {
  std::cout << "[";
  char comma[3] = {'\0', ' ', '\0'};
  for (auto item : li) {
    std::cout << comma << item;
    comma[0] = ',';
  }
  std::cout << "]\n";
}

int main() {
  std::list<int> li1{1, 2, 3};
  print(li1);
  // 在 li1.begin() 前插入 4
  li1.insert(li1.begin(), 4);  // 4, 1, 2, 3
  print(li1);
  // 在第 2 个元素前插入 3 个 5
  auto iter = li1.begin();
  std::advance(iter, 2);
  li1.insert(iter, 3, 5);  // 4, 1, 5, 5, 5, 2, 3
  print(li1);
  // 插入 range[first, last)
  std::list<int> tmp{6, 7, 8};
  iter = li1.insert(li1.begin(), tmp.begin(),
                    tmp.end());  // 6, 7, 8, 4, 1, 5, 5, 5, 2, 3
  print(li1);
  // 插入初始化列表
  li1.insert(iter, {9, 0});  // 9, 0, 6, 7, 8, 4, 1, 5, 5, 5, 2, 3
  print(li1);
}

emplace

在 pos 前插入一个元素，通过传入的参数来初始化元素对象。

#include <iostream>
#include <list>

template <typename T>
void print(const std::list<T>& li) {
  std::cout << "[";
  char comma[3] = {'\0', ' ', '\0'};
  for (auto item : li) {
    std::cout << comma << item;
    comma[0] = ',';
  }
  std::cout << "]\n";
}

struct Animal {
  Animal(int a, std::string n) : age(a), name(std::move(n)) {}

  int32_t age;
  std::string name;
};

std::ostream& operator<<(std::ostream& out, const Animal& animal) {
  out << "(" << animal.age << ", " << animal.name << ")";
  return out;
}

int main() {
  std::list<Animal> li1;
  li1.emplace(li1.begin(), 1, "Cat");
  print(li1);  // [(1, Cat)]
  auto iter = li1.emplace(std::next(li1.begin()), 2, "Dog");
  print(li1);  // [(1, Cat), (2, Dog)]
  li1.emplace(iter, 1, "Bird");
  print(li1);  // [(1, Cat), (1, Bird), (2, Dog)]
}

erase

• 删除指定位置 pos 的元素，返回被删除元素的下一个元素位置 iterator
• 删除指定 range[first, last) 元素，返回最后一个被删除的元素的下一个元素位置 iterator

#include <iostream>
#include <list>

template <typename T>
void print(const std::list<T>& li) {
  std::cout << "[";
  char comma[3] = {'\0', ' ', '\0'};
  for (auto item : li) {
    std::cout << comma << item;
    comma[0] = ',';
  }
  std::cout << "]\n";
}

int main() {
  std::list<int> li{1, 2, 3, 4, 5, 6, 7, 8, 9};
  auto iter = li.erase(li.begin());
  print(li);  // [2, 3, 4, 5, 6, 7, 8, 9]
  std::cout << std::distance(li.begin(), iter) << " " << *iter << '\n';  // 0 2
  auto range_begin = li.begin();
  std::advance(range_begin, 2);
  auto range_end = li.begin();
  std::advance(range_end, 4);
  iter = li.erase(range_begin, range_end);
  print(li);  // [2, 3, 6, 7, 8, 9]
  std::cout << std::distance(li.begin(), iter) << " " << *iter << '\n';  // 2 6
}

push_back

在容器最后通过拷贝或移动的方式添加元素

#include <iostream>
#include <list>

int main() {
  std::list<int> li;
  for (size_t i = 0; i < 5; ++i) {
    li.push_back(i);
  }
}

emplace_back

在容器最后通过原地创建元素的方式添加元素，参数为构造元素的参数

#include <iostream>
#include <list>

template <typename T>
void print(const std::list<T> &li) {
  std::cout << "[";
  char comma[3] = {'\0', ' ', '\0'};
  for (auto item : li) {
    std::cout << comma << item;
    comma[0] = ',';
  }
  std::cout << "]\n";
}

struct Animal {
  Animal(int a, std::string n) : age(a), name(std::move(n)) {}

  std::ostream &operator<<(std::ostream &out) {
    out << "(" << age << ", " << name << ")";
    return out;
  }

  int32_t age;
  std::string name;
};

std::ostream &operator<<(std::ostream &out, const Animal &animal) {
  out << "(" << animal.age << ", " << animal.name << ")";
  return out;
}

int main() {
  std::list<Animal> li;
  li.emplace_back(1, "Cat");
  li.emplace_back(2, "Dog");
  print(li);
}

pop_back

删除容器中的最后一个元素

#include <iostream>
#include <list>

int main() {
  std::list<int> li{0, 1, 2, 3, 4};
  li.pop_back();  // 0, 1, 2, 3
  li.pop_back();  // 0, 1, 2
}

push_front

将给定的元素值添加到容器的开头

#include <iostream>
#include <list>

int main() {
  std::list<int> li{0, 1, 2, 3, 4};
  li.push_front(5);  // 5, 0, 1, 2, 3, 4
}

emplace_front

在容器开头通过原地创建元素的方式添加元素，参数为构造元素的参数

#include <iostream>
#include <list>

template <typename T>
void print(const std::list<T> &li) {
  std::cout << "[";
  char comma[3] = {'\0', ' ', '\0'};
  for (auto item : li) {
    std::cout << comma << item;
    comma[0] = ',';
  }
  std::cout << "]\n";
}

struct Animal {
  Animal(int a, std::string n) : age(a), name(std::move(n)) {}

  std::ostream &operator<<(std::ostream &out) {
    out << "(" << age << ", " << name << ")";
    return out;
  }

  int32_t age;
  std::string name;
};

std::ostream &operator<<(std::ostream &out, const Animal &animal) {
  out << "(" << animal.age << ", " << animal.name << ")";
  return out;
}

int main() {
  std::list<Animal> li;
  li.emplace_back(1, "Cat");
  li.emplace_back(2, "Dog");
  li.emplace_front(3, "Duck");
  print(li); // (3, Duck), (1, Cat), (2, Dog)
}

pop_front

删除容器中第一个元素

#include <iostream>
#include <list>

int main() {
  std::list<int> nums {1, 2, 3, 4, 5};
  nums.pop_front();  // 2, 3, 4, 5
}

resize

resize 调整容器大小使得包含 count 个元素，如果当前 size 大于 count，则容器删除多余的元素，如果 size 小于 count，且如果不指定值，则使用类型的默认值，指定值则增加的元素值为该值

#include <iostream>
#include <list>

int main() {
  std::list<int> nums{0, 1, 2, 3, 4};
  nums.resize(8);     // 0, 1, 2, 3, 4, 0, 0, 0
  nums.resize(3);     // 0, 1, 2
  nums.resize(8, 6);  // 0, 1, 2, 6, 6, 6, 6, 6
}

swap

swap 交换两个容器的内容

#include <iostream>
#include <list>

int main() {
  std::list<int> num1{0, 1, 2, 3, 4};
  std::list<int> num2{5, 6, 7, 8, 9};
  num1.swap(num2);
  // num1: 5, 6, 7, 8, 9
  // num2: 0, 1, 2, 3, 4
}

Operations

merge

将两个排序的列表合并为一个。列表应按升序排序。不复制任何元素。操作后容器 other 变空。第一个版本使用 operator< 来比较元素，第二个版本使用给定的比较函数 comp。

这个操作是稳定的：对于两个列表中的等价元素，来自 *this 的元素总是在来自 other 的元素之前，并且 *this 和 other 的等价元素的顺序不会改变。

comp 的签名如下：

bool cmp(const Type1 &a, const Type2 &b);

也可以不用是 const& 。该函数不得修改传递给它的对象，并且必须能够接受所有类型的值。

对于 li1.merge(li2, comp)，当 comp 返回 true 时，将 li2 中的元素插入到 li1 当前指针的位置，然后 li2 的指针位置后移，为 false 则不插入，直接 li 的指针后移一个位置。也可以这样去理解，当 comp 为 true 时， 先选 li2 中的值，为 false 则先选 li1 中的值，每选完一个值后，对应的指针后移。

#include <iostream>
#include <list>
#include <functional>

template <typename T>
void print(const std::list<T> &li) {
  std::cout << "[";
  char comma[3] = {'\0', ' ', '\0'};
  for (auto item : li) {
    std::cout << comma << item;
    comma[0] = ',';
  }
  std::cout << "]\n";
}

int main() {
  std::list<int> num1{4, 9, 1, 3, 3};
  std::list<int> num2{8, 7, 2, 3, 4, 4};
  num1.sort();  // [1, 3, 3, 4, 9]
  num2.sort();  // [2, 3, 4, 4, 7, 8]
  
  auto num3 {num1};
  auto num4 {num2};

  num1.merge(num2);
  print(num1);  // [1, 2, 3, 3, 3, 4, 4, 4, 7, 8, 9]
  print(num2);  // []

  num3.merge(num4, [](const auto& n1, const auto& n2) { return (n1 + n2) % 2 == 0; });
  print(num3);  // [1, 3, 3, 2, 4, 3, 9, 4, 4, 7, 8]
  print(num4);  // []
}

splice

splice 将一个元素从一个列表转移到另一个列表。没有元素被复制或移动，只有列表节点的内部指针被重新指向。

• 拼接所有元素：将 other 列表中的所有元素转移到 *this 中，放到 pos 之前。转以后 other 边为空
• 拼接单个元素：将 it 指向的元素从 other 转移到 *this。该元素被插入到 pos 所指向的元素之前
• 拼接部分元素：将范围 [first, last) 中的元素从 other 转移到 *this。元素插入在 pos 指向的元素之前

#include <iostream>
#include <list>
#include <functional>

template <typename T>
void print(const std::list<T> &li) {
  std::cout << "[";
  char comma[3] = {'\0', ' ', '\0'};
  for (auto item : li) {
    std::cout << comma << item;
    comma[0] = ',';
  }
  std::cout << "]\n";
}

int main() {
  std::list<int> li1 { 1, 2, 3, 4, 5 };
  std::list<int> li2 { 10, 20, 30, 40, 50 };

  auto it = li1.begin();
  std::advance(it, 2);

  li1.splice(it, li2);
  print(li1);  // [1, 2, 10, 20, 30, 40, 50, 3, 4, 5]
  print(li2);  // []
  // 在拼接后，原来的 it 还是指向之前所指向的元素
  std::cout << std::distance(li1.begin(), it) << '\n';

  // 执行 splice 之后， it 会失效
  li2.splice(li2.begin(), li1, it);
  print(li1);  // [1, 2, 10, 20, 30, 40, 50, 4, 5] 
  print(li2);  // [3]

  it = li1.begin();
  std::advance(it, 2);

  li2.splice(li2.begin(), li1, it, li1.end());
  print(li1);  // [1, 2]
  print(li2);  // [10, 20, 30, 40, 50, 4, 5, 3]
}

remove & remove_if

删除满足特定条件的所有元素。第一个版本删除所有等于 value 的元素，第二个版本删除所有谓词返回 true 的元素。 c++ 20 之后会返回删除元素的个数，c++ 20 之前返回 void

#include <iostream>
#include <list>

template <typename T>
void print(const std::list<T> &li) {
  std::cout << "[";
  char comma[3] = {'\0', ' ', '\0'};
  for (auto item : li) {
    std::cout << comma << item;
    comma[0] = ',';
  }
  std::cout << "]\n";
}

int main() {
  std::list<int> li1 { 1, 2, 3, 100, 4, 5, 100, -1, 10 };

  auto count = li1.remove(100);
  print(li1);  // [1, 2, 3, 4, 5, -1, 10]
  std::cout << count << '\n';  // 2

  li1.remove_if([](int n) { return n > 4; });
  print(li1);  // [1, 2, 3, 4, -1]  

}

reverse

颠倒容器中元素的顺序

#include <iostream>
#include <list>

template <typename T>
void print(const std::list<T> &li) {
  std::cout << "[";
  char comma[3] = {'\0', ' ', '\0'};
  for (auto item : li) {
    std::cout << comma << item;
    comma[0] = ',';
  }
  std::cout << "]\n";
}

int main() {
  std::list<int> li1 { 1, 2, 3, 4, 5 };
  print(li1);  // [1, 2, 3, 4, 5]
  li1.reverse();
  print(li1);  // [5, 4, 3, 2, 1]
}

unique

从容器中删除所有连续的重复元素。只剩下每组相等元素中的第一个元素。

unique 可以参数 comp，comp 的原型为 bool pred(const Type1 &a, const Type2 &b);，参数类型也可以不是 const&。其中 a 表示连续元素中的第一个，b 表示连续元素中的第二个，当 pred 为 true 时，删除 b，为 false 时，保留 a，然后指针往后移

#include <iostream>
#include <list>

template <typename T>
void print(const std::list<T> &li) {
  std::cout << "[";
  char comma[3] = {'\0', ' ', '\0'};
  for (auto item : li) {
    std::cout << comma << item;
    comma[0] = ',';
  }
  std::cout << "]\n";
}

int main() {
  std::list<int> li1 { 1, 1, 2, 2, 3, 3, 3, 4, 5 };
  li1.unique();
  print(li1);  // [1, 2, 3, 4, 5]

  li1.assign({ 1, 2, 4, 6, 3, 5, 7, 2, 4, 8 });
  li1.unique([](int a, int b) { return (a + b) % 2 == 0; });
  print(li1);  // [1, 2, 3, 2]  
}

sort

按升序对元素进行排序。相等元素的顺序被保留。第一个版本使用 operator< 来比较元素，第二个版本使用给定的比较函数 comp。sort 内部使用的 merge sort 排序方法。当使用 comp 时，对于需要将满足条件的元素放在前面，不满足条件的元素放在后面，可以在条件中只对一个元素进行判断。如果设置 a 的条件，满足条件的在前，不满足条件的在后，对 b 设置则相反。并且满足条件的元素顺序是原始顺序的倒序，不满足条件的元素顺序是原始顺序的正序，

#include <iostream>
#include <list>
#include <functional>

template <typename T>
void print(const std::list<T> &li) {
  std::cout << "[";
  char comma[3] = {'\0', ' ', '\0'};
  for (auto item : li) {
    std::cout << comma << item;
    comma[0] = ',';
  }
  std::cout << "]\n";
}

int main() {
  std::list<int> li1 { 8,7,5,9,0,1,3,2,6,4 };
  li1.sort();
  print(li1);  // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

  li1.sort(std::greater<int>());
  print(li1);  // [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

  li1.assign({ 15, 1, 2, 3, 4, 5, 6, 7, 8, 9, 6 });
  li1.sort([&li1](const int a, const int b) { 
    return a % 3 == 0;});
  print(li1);  // [6, 9, 6, 3, 15, 1, 2, 4, 5, 7, 8]
}

Non-member functions

std::swap

std::swap 对于 list 的偏特化实现

#include <iostream>
#include <list>

int main() {
  std::list<int> li1 { 0, 1, 2, 3, 4};
  std::list<int> li2{5, 6, 7, 8, 9};
  std::swap(li1, li2);
  // li1: 5, 6, 7, 8, 9
  // li2: 0, 1, 2, 3, 4
}

erase & erase_if

从容器中删除所有与 value 相同的元素或满足条件的元素，返回删除的元素个数

#include <iostream>
#include <list>

int main() {
  std::list<int> li1{0, 1, 2, 3, 4, 5, 4, 3, 2, 1};
  auto count = std::erase(li1, 3); // 0, 1, 2, 4, 5, 4, 2, 1
  std::cout << count << '\n'; // 2

  count = std::erase_if(li1, [](int x){ return x % 2 == 0; }); // 1, 5, 1
  std::cout << count << '\n'; // 5
}