C++ list（双向链表）

概念

std::list 是标准模板库（STL）提供的一个容器类，它实现了双向链表的数据结构。

实现原理

内部结构

双向链表由多个节点连接而成。其中每个节点包含三个部分：

• 内容/数据域：用于存储实际的数据元素。
• 前驱：指向前一个节点的指针。
• 后继：指向后一个节点的指针。

节点管理

当创建一个 std::list 对象时，它会维护一个头节点和尾节点，用于标记链表的起始和结束位置。头节点和尾节点通常是虚拟节点，不存储实际的数据，仅用于简化链表的操作。

插入操作

• 在头部插入：创建一个新节点，将新节点的 next 指针指向原来的头节点的下一个节点，将原来头节点的下一个节点的 prev 指针指向新节点，然后更新头节点的 next 指针指向新节点，新节点的 prev 指针指向头节点。
• 在尾部插入：创建一个新节点，将新节点的 prev 指针指向原来的尾节点的前一个节点，将原来尾节点的前一个节点的 next 指针指向新节点，然后更新尾节点的 prev 指针指向新节点，新节点的 next 指针指向尾节点。
• 在中间插入：先找到插入位置的节点，创建一个新节点，调整新节点和相邻节点的 prev 和 next 指针，以将新节点插入到合适的位置。

删除操作

• 删除头部元素：找到头节点的下一个节点，将头节点的 next 指针指向该节点的下一个节点，将该节点下一个节点的 prev 指针指向头节点，然后释放该节点的内存。

• 删除尾部元素：找到尾节点的前一个节点，将尾节点的 prev 指针指向该节点的前一个节点，将该节点前一个节点的 next 指针指向尾节点，然后释放该节点的内存。
• 删除中间元素：找到要删除的节点，调整其相邻节点的 prev 和 next 指针，跳过该节点，然后释放该节点的内存。

查找操作

从头节点开始遍历整个链表，直到找到指定元素或遍历完整个链表。

基本操作与方法接口

定义、初始化和赋值

#include <iostream>
#include <list>

int main() 
{
    // 定义一个空的 list，存储 int 类型的元素
    std::list<int> List1;

    // 定义并初始化一个包含 5 个元素，每个元素都是默认值（0）的 list
    std::list<int> List2(5);

    // 定义并初始化一个包含 5 个元素，每个元素的值都是 10 的 list
    std::list<int> List3(5, 10);

    // 用另一个 list 初始化新的 list
    std::list<int> List4(List3);

    // 用另一个 list 的迭代器范围初始化新的 list
    std::list<int> List5(List4.begin(), List4.end());

    // 使用"拷贝初始化"初始化 list
    std::list<int> List6 = { 1, 2, 3, 4, 5 };
    
    // 使用"直接列表初始化"初始化 list
    std::list<int> List7{ 1, 2, 3, 4, 5 };
}

元素访问

front

访问第一个元素

List.front()
List.front() = 6;   //将第一个元素赋值为6

back

访问最后一个元素

List.back();
List.back() = 6;   //将最后一个元素赋值为6

迭代器

list 的节点在内存中是离散分布的，只能通过节点的指针依次访问相邻的节点。因此，其迭代器只支持双向访问，即可以使用 ++ 和 -- 操作符将迭代器向前或向后移动一个位置，但不支持随机访问操作。以下是 list  迭代器不支持的操作：

算术运算：不能使用 + 和 - 运算符将迭代器直接移动多个位置，因为要访问指定位置的元素，必须从当前位置开始，沿着链表依次遍历，时间复杂度为 (O(n))（较高）。如果非要使用 +- 运算，可以使用 std::advance 泛型算法。

部分比较运算：虽然可以使用 == 和 != 来判断两个迭代器是否相等，但不支持 >、<、<=、>= 等比较运算符，因为链表节点在内存中没有连续的地址顺序，无法直接比较位置关系。

正向迭代器

begin：返回容器中第一个元素的正向迭代器

end：返回容器中最后一个元素的后一个位置的正向迭代器

#include <iostream>
#include <list>

int main() 
{
    std::list<int> List(5);
 
    // 使用正向迭代器为list赋值
    for (std::list<int>::iterator it = List.begin(); it != List.end(); ++it)
    {
        *it = 3;
    }
 
    // 使用正向迭代器遍历list并打印其值
    for (std::list<int>::iterator it = List.begin(); it != List.end(); ++it)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}

cbegin：返回容器中第一个元素的正向常量迭代器

cend：返回容器中最后一个元素的后一个位置的正向常量迭代器

常量迭代器的特点是，它只能用于读取元素，不能通过它来修改所指向的元素，这有助于在需要保证数据不被修改的场景下使用。

#include <iostream>
#include <list>

int main() 
{
    std::list<int> List = {1, 2, 3, 4, 5 };
 
    // 遍历容器并输出元素
    for (std::list<int>::const_iterator it = List.cbegin(); it != List.cend(); ++it)
    {
        // 可以读取元素
        std::cout << *it << " ";
        // 以下代码会编译错误，因为不能通过常量迭代器修改元素
        // *it = 10;
    }
    std::cout << std::endl;
}

反向迭代器

rbegin：返回容器中最后一个元素的反向迭代器

rend：返回容器中第一个元素的前一个位置的反向迭代器

#include <iostream>
#include <list>

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

	std::list<int>::reverse_iterator rit = List.rbegin();
	*rit = 23;
	
	std::cout << *rit;
}

crbegin：返回容器中第一个元素的反向常量迭代器

crend：返回容器中最后一个元素的后一个位置的反向常量迭代器

#include <iostream>
#include <list>

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

	//反向迭代器倒序遍历容器
	std::list<int>::const_reverse_iterator rit1 = List.crbegin();
	while (rit1 != List.crend())
	{
		std::cout << *rit1 << " ";		//先打印再自增
		++rit1;
	}
	std::cout << std::endl;

	/*
	不能使用下面的方法来正序遍历迭代器。 
	因为list 的迭代器是双向迭代器，不是随机访问迭代器，不能使用 rit2 - 1 这样的操作
	std::list<int>::const_reverse_iterator rit2 = List.crend();
	while (rit2 != List.crbegin())
	{
		std::cout << *(rit2 - 1) << " ";
		--rit2;
	}
	std::cout << std::endl;
	*/

	//反向迭代器正序遍历容器
	std::list<int>::const_reverse_iterator rit2 = List.crend();
	while (rit2 != List.crbegin())
	{
		--rit2;		//先自减再打印
		std::cout << *rit2 << " ";
	}
	std::cout << std::endl;
}

对于反向迭代器：rbegin和crbegin到rend和crend为迭代器的正方向。rbegin和crbegin小于rend和crend，rbegin和crbegin通过自加可以到达rend和crend的位置。rend和crend大于rbegin和crbegin，rend和crend通过自减可以到达rbegin和crbegin的位置。

基于范围的for循环

注意向vector写入元素时，for循环中要加引用符&。原因见：C++杂项（更新中）_std::operator==<std::vector<std::vector<int, std::-CSDN博客

#include <iostream>
#include <list>

using namespace std;

int main() 
{
    list<int> List = {1, 2, 3, 4, 5 };
 
    for (int num : List)
    {
        cout << num;
    }
    cout << endl;

    for (int& num : List)
    {
        num = 9;
        cout << num;
    }
    cout << endl;

    for (int num : List)
    {
        cout << num;
    }
    cout << endl;
}

容量

empty

判断容器是否为空，如果为空则返回 true，否则返回 false。

List.empty()

size

返回当前存储的元素个数

List.size()

max_size

返回可容纳的最大元素数量，即一直向list中添加元素直到溢出时的元素个数

List.max_size()

修改器

clear

清除list中的所有内容

List.clear()

insert

在指定位置插入元素

#include <iostream>
#include <list>
#include <array>

// 打印vector中的元素
void printList(const std::list<int>& List)
{
    for (int num : List)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

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

    // 1. 在指定位置插入单个元素
    List.insert(List.begin(), 10);
    std::cout << "在指定位置插入单个元素: ";
    printList(List);

    // 2. 在指定位置插入多个相同值的元素
    List.insert( -- List.end(), 3, 20);
    std::cout << "在指定位置插入多个相同值的元素: ";
    printList(List);

    // 3. 在指定位置插入另一个容器的元素范围
    std::array<int, 2> a = { 30, 40 };
    List.insert(List.begin(), a.begin(), a.end());
    std::cout << "在指定位置插入另一个容器的元素范围: ";
    printList(List);

    // 4. 在指定位置插入初始化列表中的元素
    List.insert(List.end(), { 50, 60 });
    std::cout << "在指定位置插入初始化列表中的元素: ";
    printList(List);
}

emplace

原位构造元素

未完待续

emplace_back

在容器末尾原位构造元素

未完待续

emplace_front

在容器头部原位构造元素

未完待续

erase

移除单个元素

iterator erase(iterator position);

position：这是一个迭代器，指向要移除的元素。

返回一个迭代器，该迭代器指向被移除元素之后的那个元素。若移除的是列表的最后一个元素，就返回 end() 迭代器。

移除一个范围内的元素

iterator erase(iterator first, iterator last);

first 和 last：这是两个迭代器，它们定义了要移除的元素范围 [first, last)。也就是说，这个范围包含 first 指向的元素，但不包含 last 指向的元素。

返回一个迭代器，该迭代器指向被移除范围之后的第一个元素。若移除的是列表末尾的元素，就返回 end() 迭代器。

#include <iostream>
#include <list>
#include <iterator>

// 打印List中的元素
void printList(const std::list<int>& List)
{
    for (int num : List)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main()
{
    std::list<int> List = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    printList(List);

    List.erase(List.begin());
    printList(List);

    // 保存开始迭代器向前移动2个位置的迭代器
    auto it1 = List.begin();
    std::advance(it1, 2);
    // 保存结束迭代器向前移动3个位置的迭代器
    auto it2 = List.end();
    std::advance(it2, -3);

    List.erase(it1, it2);
    printList(List);
}

push_front

将元素添加到容器开头

List.push_back("abc")    //将“abc”插入List开头

push_back

将元素添加到容器末尾

List.push_back("abc")    //将“abc”插入List末尾

pop_front

移除开头元素

List.pop_front()

pop_back

移除末尾元素

List.pop_back()

resize

改变存储元素的个数

#include <iostream>
#include <list>
#include <iterator>

// 打印List中的元素
void printList(const std::list<int>& List)
{
    for (int num : List)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main()
{
    std::list<int> List = { 1, 2, 3 };
    std::cout << "原始List： ";
    printList(List);

    List.resize(5);
    std::cout << "增加大小到 5 后： ";
    printList(List);

    List.resize(2);
    std::cout << "减少大小到 2 后： ";
    printList(List);

    List.resize(6, 4);
    std::cout << "增加大小到 6 并将新增的元素赋予默认值 4 后： ";
    printList(List);

    List.resize(3, 3);
    std::cout << "减少大小到 3 并将新增的元素（实际没有）赋予默认值 3 后： ";
    printList(List);
}

swap

交换两个list中的内容

#include <iostream>
#include <list>
#include <iterator>

// 打印List中的元素
void printList(const std::list<int>& List)
{
    for (int num : List)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

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

    List1.swap(List2);

    std::cout << "List1: ";
    printList(List1);
    std::cout << "List2: ";
    printList(List2);
}

assign

将值赋给容器

#include <iostream>
#include <list>
#include <string>

int main()
{
    std::list<char> List;

    // 使用Lambda表达式打印list中的元素
    auto print_list = [&]()
    {
        for (char c : List)
        {
            std::cout << c << ' ';
        }
        std::cout << '\n';
    };

    List.assign(5, 'a');
    print_list();

    const std::string extra = "hello world";
    List.assign(extra.begin(), extra.end());
    print_list();

    List.assign({ 'C', '+', '+', '1', '1' });
    print_list();
}

操作

sort

对元素进行排序

有两种重载形式。第一种是升序排序，第2种是按照自定义的比较规则排序。

void sort();

template< class Compare >
void sort( Compare comp );

#include <functional>   //std::greater<int>()
#include <iostream>
#include <list>

// 打印List中的元素
void printList(const std::list<int>& List)
{
    for (int num : List)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main()
{
    std::list<int> List{ 8, 7, 5, 9, 0, 1, 3, 2, 6, 4 };
    std::cout << "初始：";
    printList(List);

    List.sort();
    std::cout << "升序：";
    printList(List);

    List.sort(std::greater<int>());
    std::cout << "降序：";
    printList(List);
}

merge

合并两个有序列表，准确来说是按照一定比较规则将指定列表中的元素剪切至原列表中。

默认比较方式

void merge( list& other );
void merge( list&& other );

other：要合并到当前列表的另一个 std::list 对象，可以是左值引用或右值引用。

功能：将 other 列表中的所有元素合并到当前列表中，合并后 other 列表会变为空。两个列表都必须按照默认的比较规则（通常是 operator<）进行排序。

示例代码：

#include <iostream>
#include <list>

// 打印List中的元素
void printList(const std::list<int>& List)
{
    for (int num : List)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main()
{
    std::list<int> List1 = { 5, 9, 1, 3, 3 };
    std::list<int> List2 = { 8, 7, 2, 3, 4, 4 };

    List1.sort();
    List2.sort();

    std::cout << "list1："; printList(List1);
    std::cout << "list2："; printList(List2);

    List1.merge(List2);

    std::cout << "合并后的list1："; printList(List1);
    std::cout << "合并后的list2："; printList(List2);
}

自定义比较方式

template< class Compare >
void merge( list& other, Compare comp );
template< class Compare >
void merge( list&& other, Compare comp );

other：要合并到当前列表的另一个 std::list 对象，可以是左值引用或右值引用。

comp：一个二元比较函数，用于定义元素的排序规则。该函数接受两个参数，返回一个布尔值，表示第一个参数是否应该排在第二个参数之前（如果返回的值为true，那么第一个参数要在第二个参数前）。

功能描述：将 other 列表中的所有元素合并到当前列表中，合并后 other 列表会变为空。两个列表都必须按照 comp 指定的比较规则进行排序。

示例代码：

#include <iostream>
#include <list>

// 打印List中的元素
void printList(const std::list<int>& List)
{
    for (int num : List)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

// 自定义比较函数，按降序排序
bool greater(int a, int b) 
{
    return a > b;
}

int main()
{
    std::list<int> List1 = { 5, 9, 1, 3, 3 };
    std::list<int> List2 = { 8, 7, 2, 3, 4, 4 };

    List1.sort(greater);
    List2.sort(greater);

    std::cout << "list1："; printList(List1);
    std::cout << "list2："; printList(List2);

    List1.merge(List2, greater);

    std::cout << "合并后的list1："; printList(List1);
    std::cout << "合并后的list2："; printList(List2);
}

splice

从另一个 list 中移动元素

转移整个列表

void splice(const_iterator position, list& other);
void splice(const_iterator position, list&& other);

position：这是一个常量迭代器，它指定了在目标列表中插入元素的位置。

other：这是要转移元素的源列表，可以是左值引用或者右值引用。

功能：把 other 列表中的所有元素转移到目标列表的 position 位置之前，转移完成后，other 列表会变为空。

转移单个元素

void splice(const_iterator position, list& other, const_iterator it);
void splice(const_iterator position, list&& other, const_iterator it);

参数说明：

position：常量迭代器，指定在目标列表中插入元素的位置。

other：源列表，可以是左值引用或者右值引用。

it：常量迭代器，指向 other 列表中要转移的单个元素。

功能描述：把 other 列表中 it 所指向的元素转移到目标列表的 position 位置之前，转移后，该元素会从 other 列表中移除。

转移元素范围

void splice(const_iterator position, list& other, const_iterator first, const_iterator last);
void splice(const_iterator position, list&& other, const_iterator first, const_iterator last);

参数说明：

position：常量迭代器，指定在目标列表中插入元素的位置。

other：源列表，可以是左值引用或者右值引用。

first 和 last：常量迭代器，定义了要转移的元素范围 [first, last)，也就是包含 first 指向的元素，但不包含 last 指向的元素。

功能描述：把 other 列表中 [first, last) 范围内的元素转移到目标列表的 position 位置之前，转移后，这些元素会从 other 列表中移除。

代码示例

#include <iostream>
#include <list>

// 打印List中的元素
void printList(const std::list<int>& List)
{
    for (int num : List)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main()
{
    std::list<int> List1 = { 1, 2, 3 };
    std::list<int> List2 = { 4, 5, 6 };
    // 把 List2 的所有元素转移到 List1 的开头
    List1.splice(List1.begin(), List2);
    std::cout << "List1: ";   printList(List1);
    std::cout << "List2: ";   printList(List2);



    std::list<int> List3 = { 1, 2, 3 };
    std::list<int> List4 = { 4, 5, 6 };
    // 把 List4 的第二个元素转移到 list1 的开头
    List3.splice(List3.begin(), List4, ++List4.begin());
    std::cout << "List3: ";     printList(List3);
    std::cout << "List4: ";     printList(List4);



    std::list<int> List5 = { 1, 2, 3, 4, 5, 6 };
    std::list<int> List6 = { 7, 8, 9 };
    // 把 List5 的第二个到倒数第二个之间的元素转移到 list6 的开头
    List6.splice(List6.begin(), List5, ++List5.begin(), --List5.end());
    std::cout << "List5: ";     printList(List5);
    std::cout << "List6: ";     printList(List6);
}

remove

移除列表中所有值等于指定值的元素

C++20前，该方法没有返回值； C++20及C++20后，该方法返回移除的数量。

#include <list>
#include <iostream>

// 打印List中的元素
void printList(const std::list<int>& List)
{
    for (int num : List)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main()
{
    std::list<int> List = { 1, 100, 2, 3, 10, 1, 11, -1, 12 };

    auto count = List.remove(1);
    std::cout << "移除了 " << count << " 个等于 1 的元素\n";

    printList(List);
}

remove_if

移除满足特定标准的元素

C++20前，该方法没有返回值； C++20及C++20后，该方法返回移除的数量。

void remove_if( UnaryPredicate p );
size_type remove_if( UnaryPredicate p );

p：一个一元谓词函数（关于谓词函数的相关知识可以查看：C++杂项（更新中）_std::operator==<std::vector<std::vector<int, std::-CSDN博客），接受列表元素类型的参数，返回一个布尔值。如果返回 true，则表示该元素需要被移除。

#include <list>
#include <iostream>

// 打印List中的元素
void printList(const std::list<int>& List)
{
    for (int num : List)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

// 定义一个一元谓词函数，判断元素是否为奇数
bool isOdd(int num) 
{
    return num % 2 != 0;
}

int main() 
{
    std::list<int> List = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    // 移除所有奇数元素
    List.remove_if(isOdd);

    // 输出移除元素后的列表
    printList(List);
}

reverse

逆转容器中的元素顺序

List.reverse()

unique

从列表中移除连续重复的元素，仅保留每个连续重复元素序列中的第一个元素

默认比较方式

void unique();    (C++20 前)
size_type unique();    (C++20 起)

返回值：移除的元素数量。

功能：使用 operator== 来比较相邻的元素，移除所有连续重复的元素，只保留每个连续重复元素序列中的第一个元素。

#include <iostream>
#include <list>

// 打印List中的元素
void printList(const std::list<int>& List)
{
    for (int num : List)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main()
{
    std::list<int> List = { 1, 1, 2, 2, 2, 3, 3, 1, 1 };
    List.unique();
    printList(List);
}

自定义比较方式

template< class BinaryPredicate >
void unique( BinaryPredicate p );    (C++20 前)

template< class BinaryPredicate >
size_type unique( BinaryPredicate p );    (C++20 起)

p：一个二元谓词函数 （关于谓词函数的相关知识可以查看：C++杂项（更新中）_std::operator==<std::vector<std::vector<int, std::-CSDN博客），用于比较相邻的元素。该函数接受两个参数，返回一个布尔值，表示这两个参数是否被视为相等。

返回值：移除的元素数量。

功能：使用用户提供的二元谓词 p 来比较相邻的元素，移除所有被 p 判断为相等的连续元素，只保留每个连续重复元素序列中的第一个元素。

#include <iostream>
#include <list>

// 自定义二元谓词，判断两个元素的绝对值是否相等
bool absEqual(int a, int b) 
{
    return std::abs(a) == std::abs(b);
}

// 打印List中的元素
void printList(const std::list<int>& List)
{
    for (int num : List)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() 
{
    std::list<int> List = { 1, -1, 2, 2, -2, 3, 3, -1, 1 };
    List.unique(absEqual);
    printList(List);
}

参考与引用

C++ STL list 容器详解-CSDN博客

C++——list的简介及使用_c++ list-CSDN博客

std::list - cppreference.com

百度安全验证

未完待续

写出容器方法的底层实现原理和复杂度。

未完待续