浅谈C++|STL之list+forward_list篇

一.list基本概念

功能:将数据进行链式存储

链表（list)是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的

链表的组成:链表由—系列结点组成

结点的组成:一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域

STL中的链表是一个双向循环链表

由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器

list的优点:
·采用动态存储分配，不会造成内存浪费和溢出
·链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素

list的缺点:
·链表灵活，但是空间(指针域)和时间(遍历)额外耗费较大
List有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。

总结:STL中List和vector是两个最常被使用的容器，各有优缺点

二.list构造函数

以下是在每个构造函数后添加的示例代码：

1. 默认构造函数：

std::list<int> myList;  // 创建一个空的 int 类型的双向链表容器
1

2. 带有元素个数参数的构造函数：

std::list<int> myList(5, 10);  // 创建一个包含 5 个值为 10 的 int 类型的双向链表容器
1

3. 区间构造函数：

std::vector<int> myVector = {1, 2, 3, 4, 5};
std::list<int> myList(myVector.begin() + 1, myVector.end() - 1);  // 创建一个包含 myVector 中除了第一个和最后一个元素的剩余元素的双向链表容器
1
2

4. 拷贝构造函数：

std::list<int> originalList = {1, 2, 3, 4, 5};
std::list<int> copiedList(originalList);  // 创建一个拷贝 originalList 的新双向链表容器
1
2

5. 移动构造函数：

std::list<int> originalList = {1, 2, 3, 4, 5};
std::list<int> movedList(std::move(originalList));  // 创建一个移动 originalList 元素到新双向链表容器中的新容器
1
2

6. 初始化列表构造函数：

std::list<int> myList = {1, 2, 3, 4, 5};  // 使用初始化列表中的元素初始化一个 int 类型的双向链表容器
1

三.list赋值和交换

当涉及到赋值、交换和 assign 函数时，你可以使用以下方法来操作 std::list 容器：

1. 赋值操作符（operator=）：

   std::list<int> list1 = {1, 2, 3, 4, 5};
   std::list<int> list2;
   
   // 使用赋值操作符将 list1 中的元素赋值给 list2
   list2 = list1;
   1
   2
   3
   4
   5

2. swap 函数：

   std::list<int> list1 = {1, 2, 3, 4, 5};
   std::list<int> list2 = {10, 20, 30};
   
   // 使用 swap 函数交换 list1 和 list2 中的所有元素
   list1.swap(list2);
   
   // 或者使用 std::swap
   std::swap(list1, list2);
   1
   2
   3
   4
   5
   6
   7
   8

3. assign 函数：

   std::list<int> myList;
   
   // 使用 assign 函数将特定值赋给 myList
   myList.assign(5, 10);
   
   // 使用 assign 函数将范围内的元素赋给 myList
   std::vector<int> myVector = {1, 2, 3, 4, 5};
   myList.assign(myVector.begin() + 1, myVector.end() - 1);
   
   // 使用 assign 函数使用初始化列表中的元素进行赋值给 myList
   myList.assign({1, 2, 3, 4, 5});
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11

通过使用这些操作，你可以方便地在 std::list 容器中进行赋值、交换和赋特定值、赋范围以及使用初始化列表进行赋值的操作。请记住，在这些操作之后，原容器中的元素将被替换为新赋值的元素，原容器中的迭代器、引用和指针等将不再有效。

四.list大小操作

当涉及到获取和调整 std::list 的大小时，你可以使用以下函数：

1. 获取大小：

   • size 函数：返回列表中元素的数量。
   • max_size 函数：返回列表所能容纳的最大元素数量。
   • empty 函数：检查列表是否为空。

   示例：

   std::list<int> myList = {1, 2, 3, 4, 5};
   
   size_t length = myList.size();              // 获取列表的大小
   size_t maxSize = myList.max_size();          // 返回列表能够容纳的最大元素数量
   bool isEmpty = myList.empty();               // 检查列表是否为空
   1
   2
   3
   4
   5

2. 调整大小：

   • resize 函数：调整列表的大小。
   • clear 函数：清空列表中的所有元素。

   示例：

   std::list<int> myList = {1, 2, 3, 4, 5};
   
   myList.resize(10);               // 调整列表的大小为 10
   myList.resize(8, 0);             // 调整列表的大小为 8，并插入值为 0 的元素
   myList.clear();                  // 清空列表中的所有元素
   1
   2
   3
   4
   5

通过使用这些函数，你可以方便地获取列表的大小、最大容量以及检查列表是否为空。同时，你也可以调整列表的大小或清空列表中的元素。请根据实际需求选择适合的函数来操作 std::list 容器。
下面是整理成表格的关于获取和调整 std::list 大小的函数接口及示例：

示例：

#include 
#include 

int main() {
    std::list<int> myList = {1, 2, 3, 4, 5};
    
    // 获取大小
    size_t length = myList.size();              // 获取列表的大小
    std::cout << "Size: " << length << std::endl;

    // 获取最大容量
    size_t maxSize = myList.max_size();          // 返回列表能够容纳的最大元素数量
    std::cout << "Max Size: " << maxSize << std::endl;
    
    // 检查是否为空
    bool isEmpty = myList.empty();               // 检查列表是否为空
    std::cout << "Is Empty: " << std::boolalpha << isEmpty << std::endl;
    
    // 调整大小
    myList.resize(10);               // 调整列表的大小为 10
    myList.resize(8, 0);             // 调整列表的大小为 8，并插入值为 0 的元素

    // 清空列表
    myList.clear();                  // 清空列表中的所有元素

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

五.list的插入和删除

在C++中，使用STL的list容器可以实现高效的插入和删除操作。以下是关于list的插入和删除的一些基本操作：

1. 插入元素：
   • 在列表头部插入元素：使用push_front()函数。
   • 在列表尾部插入元素：使用push_back()函数。
   • 在指定位置之前插入元素：使用insert()函数，传递需要插入的位置和要插入的元素的值。

std::list<int> myList;
myList.push_front(10);  // 在头部插入元素
myList.push_back(20);   // 在尾部插入元素
auto it = std::next(myList.begin());  // 获取迭代器指向第一个元素之后的位置
myList.insert(it, 15);  // 在指定位置之前插入元素
myList.insert(it, 150，15);  // 在指定位置之前插入150个元素
myList.insert(myList.begin()，myList.end（）);  // 迭代器插入
1
2
3
4
5
6
7

2. 删除元素：
   • 删除列表头部的元素：使用pop_front()函数。
   • 删除列表尾部的元素：使用pop_back()函数。
   • 删除指定位置的元素：使用erase()函数，传递要删除的元素的位置。

std::list<int> myList;
myList.push_back(10);
myList.push_back(20);
myList.push_back(30);
myList.pop_front();  // 移除头部元素
myList.pop_back();   // 移除尾部元素
auto it = std::next(myList.begin());  // 获取迭代器指向第一个元素之后的位置
myList.erase(it);    // 移除指定位置的元素
myList.erase(myList.begin()，myList.end（）);    // 移除指定区间的元素
1
2
3
4
5
6
7
8
9

3. remove()函数用于删除list容器中所有与指定值相等的元素。它会对容器进行遍历，将符合条件的元素删除。以下是示例代码：

std::list<int> myList { 10, 20, 30, 40, 10, 50 };

myList.remove(10); // 删除所有值为10的元素

// 打印剩余的元素
for (const auto& elem : myList) {
    std::cout << elem << " ";
}
// 输出: 20 30 40 50
1
2
3
4
5
6
7
8
9

4. clear()函数用于清空整个list容器，将其变为空列表。以下是示例代码：

std::list<int> myList { 10, 20, 30 };

myList.clear(); // 清空list

std::cout << "Size of list: " << myList.size() << std::endl; // 输出: 0
1
2
3
4
5

remove()函数删除所有与指定值相等的元素，而非删除指定位置的元素。若要删除指定位置的元素，仍需使用erase()函数。

list容器支持常数时间复杂度的插入和删除操作，但在访问和查找元素方面相对较差。同时，list容器不支持随机访问，只能通过迭代器进行访问。

auto是什么？

在C++11及以后的版本中，可以使用关键字auto来自动推导变量的类型。当使用auto声明变量时，编译器会根据变量的初始化值来推导出变量的类型。

在上述示例代码中，auto被用于声明一个迭代器it，通过调用std::next()函数来获取myList中第一个元素之后的位置。std::next()函数返回一个迭代器，而使用auto让编译器根据返回值来自动推导出it的类型，以保证类型匹配。

使用auto关键字的好处是可以简化代码，减少类型声明的冗余，并且在某些情况下可以更灵活地处理不同类型的变量。然而，需要注意的是，auto并不是完全的类型推导，它只能在编译时确定变量的类型，而不能用于运行时动态类型的情况。

六.数据存取和遍历

在C++的STL中，list容器是一个双向链表，其数据存取方式与使用索引进行访问的容器（例如vector）有所不同。

要访问list容器中的数据，可以使用迭代器。迭代器提供了一种访问容器元素的通用方式，而不需要依赖索引。以下是一些常用的数据存取操作：

1. 访问首尾元素：
   • 使用front()函数可以访问容器的第一个元素。
   • 使用back()函数可以访问容器的最后一个元素。

std::list<int> myList { 10, 20, 30 };
int firstElement = myList.front();   // 访问第一个元素
int lastElement = myList.back();     // 访问最后一个元素
1
2
3

2. 使用迭代器遍历元素：
   • 使用begin()函数获取指向容器第一个元素的迭代器。
   • 使用end()函数获取指向容器最后一个元素之后位置的迭代器。

std::list<int> myList { 10, 20, 30 };
for (auto it = myList.begin(); it != myList.end(); ++it) {
    // 使用迭代器访问元素
    int element = *it;
    // 进行操作
}
1
2
3
4
5
6

3. 使用范围遍历语法：
   • 使用C++11引入的范围遍历语法，可以更简洁地遍历容器元素。

std::list<int> myList { 10, 20, 30 };
for (const auto& element : myList) {
    // 使用范围遍历访问元素
    // 进行操作
}
1
2
3
4
5

需要注意的是，由于list是一个双向链表，它不能像vector那样通过索引直接访问元素，因为链表的元素没有直接的索引位置。因此，在list中按索引进行访问或查找需要通过迭代器和线性搜索来实现。

加强for循环

当使用范围遍历语法时，可以更简洁地遍历容器元素，不需要显式地操作迭代器。以下是对第三种遍历方法的详细介绍：

1. 范围遍历语法：

   std::list<int> myList { 10, 20, 30 };
   for (const auto& element : myList) {
       // 使用范围遍历访问元素
       // 进行操作
   }
   1
   2
   3
   4
   5

   • myList是一个std::list类型的容器，初始化了三个整型元素。
   • for循环遍历myList容器中的每个元素。
   • const auto& element定义了一个循环变量element，用于依次访问容器中的元素。auto关键字用于自动推导element的类型。
   • element是一个常量引用，可以以只读方式访问容器中的元素值。

2. 范围遍历的优点：

   • 简洁：范围遍历语法更加简洁，不需要手动操作迭代器。
   • 安全：范围遍历中的循环变量为常量引用，防止意外修改元素。
   • 自动推导类型：使用auto关键字可以自动推导循环变量的类型，无需显式声明。

范围遍历适用于大多数容器类型，包括vector、list、set、map等。然而，范围遍历仅适用于对容器中元素的只读访问。如果需要对元素进行修改，可以将循环变量声明为非常量引用。

七.反转和排序

1. 反转（Reverse）：
   • 可以使用reverse()函数对std::list容器进行反转操作。
   • 这将会使容器中的元素逆序排列。

示例代码：

std::list<int> myList { 1, 2, 3, 4, 5 };
myList.reverse();  // 反转容器中的元素
1
2

2. 排序（Sort）：
   • 可以使用sort()函数对std::list容器进行排序操作。
   • 默认情况下，sort()函数按升序对容器元素进行排序。
   • 也可以通过提供自定义的比较函数来实现自定义排序。

示例代码：

std::list<int> myList { 5, 3, 1, 4, 2 };
myList.sort();  // 按升序对容器中的元素进行排序
1
2

自定义排序的示例代码：

bool descendingOrder(int a, int b) {
    return a > b;
}

std::list<int> myList { 5, 3, 1, 4, 2 };
myList.sort(descendingOrder);  // 按降序对容器中的元素进行排序
1
2
3
4
5
6

由于std::list是一个双向链表，排序操作可能比较耗时，因为它需要通过链表中的指针进行交换操作。而对于反转操作来说，它可以在常数时间内完成。

八.函数接口

九.forward_list单向链表