【C++篇】从基础到进阶：全面掌握C++ List容器的使用

熬夜学编程的小王

发布于 2024-11-25 14:27:46

9000

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！ 👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！ 🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++感兴趣的朋友，让我们一起进步！

从基础到进阶：全面掌握C++ List容器的使用

一. C++ `list` 容器简介

list 是 C++ 标准模板库 (STL) 中提供的一种顺序容器。它使用 双向链表 作为底层实现，与 vector 等连续存储的容器不同，list 提供了一种非连续的存储方式，适用于插入和删除操作频繁的场景。

`1.1 list` 容器的特点

双向链表结构：
- 每个节点包含一个数据元素以及前后两个指针，分别指向前一个和后一个节点。
- 节点的非连续存储可以避免频繁的内存移动。
动态大小调整：
- list 不需要预先定义大小，会根据需要动态分配内存。
高效的插入和删除：
- 插入和删除操作时间复杂度为 O(1)，只需要调整指针，而不涉及内存的移动。
- 适用于需要频繁在中间位置进行操作的场景。
低效的随机访问：
- 不支持随机访问（例如 list[3] 不合法），必须通过迭代器逐个访问节点。
支持双向迭代：
- 提供双向迭代器，方便从头到尾或从尾到头遍历。

#include<list>
#include<iostream>
using namespace std;

int main()
{
	list<int> l1 = { 1,2,3,4,5 };
	//使用范围for遍历
	for (auto& s : l1)
	{
		cout << s << " ";
	}
	cout << endl;
	//使用迭代器遍历
	for (auto it = l1.begin(); it != l1.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
	return 0;
}

二. list构造函数

2.1 常见构造函数

2.1.1 默认构造函数

功能：创建一个空的 std::list

#include <list>
#include <iostream>

int main() {
    std::list<int> myList; // 空列表
    std::cout << "Size: " << myList.size() << std::endl; // 输出 0
    return 0;
}

2.1.2 使用初始化列表

方法：可以通过花括号 {} 初始化一个列表。

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {1, 2, 3, 4, 5};
    for (int num : myList) {
        std::cout << num << " "; // 输出 1 2 3 4 5
    }
    return 0;
}

2.1.3 指定大小的构造

功能：创建一个指定大小的列表，元素初始化为默认值（对于基本类型是 0）

#include <list>
#include <iostream>

int main() {
    std::list<int> myList(5); // 创建包含 5 个元素的列表，初始值为 0
    for (int num : myList) {
        std::cout << num << " "; // 输出 0 0 0 0 0
    }
    return 0;
}

2.1.4 指定大小和初始值的构造

功能：可以同时指定列表的大小和每个元素的初始值。

#include <list>
#include <iostream>

int main() {
    std::list<int> myList(5, 42); // 创建包含 5 个元素的列表，初始值均为 42
    for (int num : myList) {
        std::cout << num << " "; // 输出 42 42 42 42 42
    }
    return 0;
}

2.1.5 拷贝构造

功能：用已有的 std::list 初始化另一个列表。

#include <list>
#include <iostream>

int main() {
    std::list<int> originalList = {1, 2, 3};
    std::list<int> copiedList(originalList); // 拷贝 originalList
    for (int num : copiedList) {
        std::cout << num << " "; // 输出 1 2 3
    }
    return 0;
}

2.1.6 区间构造

功能：从另一个容器（如数组、std::vector 等）中指定范围构造。

#include <list>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50};
    std::list<int> myList(vec.begin() + 1, vec.end() - 1); // 使用范围 [20, 30, 40]
    for (int num : myList) {
        std::cout << num << " "; // 输出 20 30 40
    }
    return 0;
}

2.1.7 使用移动构造

功能：C++11 引入的移动语义，可以通过移动已有列表的内容，避免拷贝。

#include <list>
#include <iostream>

int main() {
    std::list<int> originalList = {1, 2, 3};
    std::list<int> movedList(std::move(originalList)); // originalList 内容被转移
    for (int num : movedList) {
        std::cout << num << " "; // 输出 1 2 3
    }
    return 0;
}

这些构造方法结合 std::list 的成员函数（如 push_back, emplace_back, insert 等），可以灵活地处理双向链表数据结构。

2.1.8 相关文档

C++ Reference: list constructor

三. `list` 迭代器的使用

获取 std::list 的迭代器

std::list 提供了三种类型的迭代器：

begin()：指向列表的第一个元素。
end()：指向列表最后一个元素的下一个位置（即尾后迭代器）。
rbegin() 和 rend()：反向迭代器，分别指向最后一个元素和首元素的下一个位置。

3.1 常见迭代器

3.1.1 示例代码：使用正和反迭代器遍历

#include <list>
#include <iostream>

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

    // 使用 begin() 和 end() 正向迭代
    for (std::list<int>::iterator it = myList.begin(); it != myList.end(); ++it) {
        std::cout << *it << " ";  // 输出 10 20 30 40 50
    }
    std::cout << std::endl;

    // 使用 rbegin() 和 rend() 反向迭代
    for (std::list<int>::reverse_iterator rit = myList.rbegin(); rit != myList.rend(); ++rit) {
        std::cout << *rit << " ";  // 输出 50 40 30 20 10
    }
    std::cout << std::endl;

    return 0;
}

std::list 支持双向迭代器，可以通过正向和反向遍历元素。
使用 std::list 的迭代器可以轻松地进行元素的访问、插入、删除和修改。
std::list 提供了灵活的操作方式，适合处理需要频繁插入和删除元素的场景

3.1.2 相关文档

C++ Reference: list iterator

四. list容量管理接口（iterface）

4.1 常见容量接口

4.1.1 `size()`

功能：获取当前列表中元素的个数。

示例代码：

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {10, 20, 30, 40};
    std::cout << "Size: " << myList.size() << std::endl; // 输出 4
    return 0;
}

4.1.2 `empty()`

功能：检查列表是否为空。如果列表为空，则返回 true。

示例代码：

#include <list>
#include <iostream>

int main() {
    std::list<int> myList;

    if (myList.empty()) {
        std::cout << "List is empty" << std::endl;
    } else {
        std::cout << "List is not empty" << std::endl;
    }

    return 0;
}

4.1.3 `max_size()`

获取 std::list 能够容纳的最大元素数量。这通常依赖于系统或编译器的实现

示例代码：

#include <list>
#include <iostream>

int main() {
    std::list<int> myList;
    std::cout << "Max size: " << myList.max_size() << std::endl; // 输出最大可能的元素数量
    return 0;
}

输出：

Max size: 768614336404564650

4.1.4 动态调整大小：resize()

功能：可以调整列表的大小。如果新大小大于当前大小，则在末尾添加默认值的元素；如果新大小小于当前大小，则删除多余的元素。

示例代码：

#include <list>
#include <iostream>
using namespace std;

int main() {
    std::list<int> myList = { 10, 20, 30 };

    // 增大列表大小
    myList.resize(5); // 添加两个默认值（0 或类型默认值）

    for (int val : myList) {
        std::cout << val << " "; // 输出 10 20
    }
    cout << endl;

    // 减小列表大小
    myList.resize(2); // 只保留前两个元素

    for (int val : myList) {
        std::cout << val << " "; // 输出 10 20
    }

    return 0;
}

输出：

10 20 30 0 0 10 20

总结

size() 和 empty() 是检查容量状态的核心函数。
resize() 可以动态调整 std::list 的大小。
std::list 的容量是动态的，由系统内存决定，其极限可以通过 max_size() 查询。

五. list访问元素

在 C++ 中，std::list 是一个双向链表，与 std::vector 不同，它不支持随机访问（如使用索引直接访问元素）。因此，访问 std::list 中的元素主要依赖迭代器或成员函数。

5.1 常见访问元素接口

5.1.1 访问首尾元素

std::list 提供了以下函数直接访问首尾元素：

front()：返回列表中的第一个元素。
back()：返回列表中的最后一个元素。

示例代码：

#include <list>
#include <iostream>

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

    // 访问首尾元素
    std::cout << "Front: " << myList.front() << std::endl; // 输出 10
    std::cout << "Back: " << myList.back() << std::endl;   // 输出 50

    return 0;
}

5.1.2 使用 `std::advance()` 定位特定元素

虽然 std::list 不支持随机访问，但可以使用 std::advance() 函数将迭代器移动到指定位置。

示例代码：

#include <list>
#include <iostream>
#include <iterator> // std::advance

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

    auto it = myList.begin();
    //这里的2是下标
    std::advance(it, 2); // 将迭代器移动到第 3 个元素（从 0 开始计数）

    std::cout << "Third element: " << *it << std::endl; // 输出 30

    return 0;
}

5.1.3 遍历并修改元素

通过迭代器可以直接修改元素的值。

示例代码：

#include <list>
#include <iostream>

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

    // 使用迭代器修改元素
    for (auto it = myList.begin(); it != myList.end(); ++it) {
        *it *= 2; // 每个元素乘以 2
    }

    // 输出修改后的列表
    for (auto val : myList) {
        std::cout << val << " "; // 输出 20 40 60 80 100
    }
    std::cout << std::endl;

    return 0;
}

总结

首尾访问：使用 front() 和 back() 访问第一个和最后一个元素。
顺序遍历：通过正向迭代器（begin() 和 end()）或范围循环进行。
反向遍历：使用反向迭代器（rbegin() 和 rend()）。
特定位置访问：结合 std::advance() 定位特定元素。
元素修改：通过迭代器或引用修改列表内容。

由于 std::list 是链表结构，访问特定位置元素时需要从头或尾顺序遍历，因此不适合需要频繁随机访问的场景。

六. `list` 的插入、删除与修改

6.1 插入操作

6.1.1 使用 push_back

功能：在列表末尾插入元素。

示例代码：

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {10, 20, 30};
    myList.push_back(40); // 在末尾插入 40

    for (int val : myList) {
        std::cout << val << " "; // 输出 10 20 30 40
    }

    return 0;
}

6.1.2 `push_front()`

功能：在列表开头插入元素。

示例代码：

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {20, 30, 40};
    myList.push_front(10); // 在开头插入 10

    for (int val : myList) {
        std::cout << val << " "; // 输出 10 20 30 40
    }

    return 0;
}

6.1.3 使用 `insert()`

功能：在指定位置前插入元素。

单个元素插入：

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {10, 30, 40};
    auto it = myList.begin();
    ++it; // 指向第二个位置

    myList.insert(it, 20); // 在 30 前插入 20

    for (int val : myList) {
        std::cout << val << " "; // 输出 10 20 30 40
    }

    return 0;
}

插入多个元素：

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {10, 40};
    auto it = myList.begin();
    ++it; // 指向第二个位置

    myList.insert(it, {20, 30}); // 在 40 前插入 20 和 30

    for (int val : myList) {
        std::cout << val << " "; // 输出 10 20 30 40
    }

    return 0;
}

6.1.4 使用 `emplace()` 和 `emplace_back()`

emplace() 在指定位置构造元素：

#include <list>
#include <iostream>

int main() {
    std::list<std::pair<int, int>> myList;
    auto it = myList.begin();

    myList.emplace(it, 1, 2); // 在开头插入 pair(1, 2)

    for (const auto& p : myList) {
        std::cout << "(" << p.first << ", " << p.second << ") "; // 输出 (1, 2)
    }

    return 0;
}

emplace_back() 在末尾直接构造元素：

#include <list>
#include <iostream>

int main() {
    std::list<std::pair<int, int>> myList;
    myList.emplace_back(1, 2); // 在末尾插入 pair(1, 2)

    for (const auto& p : myList) {
        std::cout << "(" << p.first << ", " << p.second << ") "; // 输出 (1, 2)
    }

    return 0;
}

6.2 删除操作

6.2.1 使用 `pop_back()`

删除列表中的最后一个元素。

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {10, 20, 30};
    myList.pop_back(); // 删除最后一个元素

    for (int val : myList) {
        std::cout << val << " "; // 输出 10 20
    }

    return 0;
}

6.2.2 使用 `pop_front()`

删除列表中的第一个元素。

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {10, 20, 30};
    myList.pop_front(); // 删除第一个元素

    for (int val : myList) {
        std::cout << val << " "; // 输出 20 30
    }

    return 0;
}

6.2.3 使用 `erase()`

删除指定位置的元素，或删除指定范围的元素。

删除单个元素：

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {10, 20, 30, 40};
    auto it = myList.begin();
    ++it; // 指向第二个元素

    myList.erase(it); // 删除 20

    for (int val : myList) {
        std::cout << val << " "; // 输出 10 30 40
    }

    return 0;
}

删除范围内的元素

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {10, 20, 30, 40, 50};
    auto it1 = myList.begin();
    auto it2 = myList.begin();
    std::advance(it2, 3); // 指向第四个元素

    myList.erase(it1, it2); // 删除第一个到第三个元素（不包括第四个）

    for (int val : myList) {
        std::cout << val << " "; // 输出 40 50
    }

    return 0;
}

6.2.4 使用 remove() 和 remove_if()

remove() 删除与指定值匹配的所有元素

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {10, 20, 30, 20, 40};
    myList.remove(20); // 删除所有值为 20 的元素

    for (int val : myList) {
        std::cout << val << " "; // 输出 10 30 40
    }

    return 0;
}

remove_if() 按条件删除元素：

#include <list>
#include <iostream>

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

    // 删除所有大于 30 的元素
    myList.remove_if([](int x) { return x > 30; });

    for (int val : myList) {
        std::cout << val << " "; // 输出 10 20 30
    }

    return 0;
}

6.3 修改元素

6.3.1 使用迭代器修改元素

通过迭代器可以访问并修改元素。

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {10, 20, 30};

    for (auto it = myList.begin(); it != myList.end(); ++it) {
        *it *= 2; // 每个元素乘以 2
    }

    for (int val : myList) {
        std::cout << val << " "; // 输出 20 40 60
    }

    return 0;
}

6.3.2 使用范围循环修改元素（C++11 起）

通过引用可以直接修改元素。

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {10, 20, 30};

    for (int& val : myList) {
        val += 5; // 每个元素加 5
    }

    for (int val : myList) {
        std::cout << val << " "; // 输出 15 25 35
    }

    return 0;
}

总结：

插入元素：push_back()、push_front()、insert()、emplace()。
删除元素：pop_back()、pop_front()、erase()、remove()、remove_if()。
修改元素：通过迭代器或范围循环进行修改。
std::list 的灵活性在于其对插入和删除的高效支持，适合需要频繁调整内容的场景。

七. list迭代器失效问题

在 C++ 中，std::list 是一种双向链表，插入或删除操作通常不会导致迭代器失效。然而，在某些情况下，迭代器仍可能变得无效，导致未定义行为。以下是详细介绍 std::list 迭代器失效的场景、原因及解决方法：

7.1 常见导致迭代器失效的操作

7.1.1 删除操作（`erase` 和 `remove`）

当从列表中删除元素时，与被删除元素关联的迭代器将失效。指向其他元素的迭代器不会受到影响。

示例：

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {10, 20, 30, 40};
    auto it = myList.begin();
    ++it; // 指向第二个元素 (20)

    myList.erase(it); // 删除 20
    // 此时，it 已失效，不能再访问

    // 正确做法：更新迭代器
    it = myList.begin();
    ++it; // 指向新的第二个元素 (30)
    std::cout << *it << std::endl; // 输出 30

    return 0;
}

解决方法：

在调用 erase 后，更新迭代器。
使用 erase 的返回值（新有效迭代器）。

auto it = myList.erase(myList.begin()); // 删除第一个元素，并获取新迭代器
注：erase（）返回删除下一个元素的位置

7.1.2 批量删除操作（`remove` 和 `remove_if`）

使用 remove 或 remove_if 删除多个元素时，所有指向被删除元素的迭代器都会失效。

示例：

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {10, 20, 30, 40, 20};
    auto it = myList.begin();
    ++it; // 指向第二个元素 (20)

    myList.remove(20); // 删除所有值为 20 的元素
    // it 已失效，不能再使用

    // 正确做法：重新获取有效迭代器
    it = myList.begin();
    std::cout << *it << std::endl; // 输出 10

    return 0;
}

7.1.3 插入操作（`insert` 和 `emplace`）

普通插入：在 std::list 中插入新元素时，不会影响现有迭代器的有效性。
错误访问：插入新元素后，如果误用插入位置周围的迭代器访问未初始化的范围，会导致逻辑错误。

示例：

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {10, 30, 40};
    auto it = myList.begin();
    ++it; // 指向 30

    myList.insert(it, 20); // 在 30 前插入 20
    std::cout << *it << std::endl; // 输出 30（有效）

    return 0;
}

7.1.4 清空操作（`clear`）

调用 clear 后，列表中的所有迭代器都将失效。

示例：

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {10, 20, 30};
    auto it = myList.begin();

    myList.clear(); // 清空列表
    // it 已失效，不能再使用

    return 0;
}

解决方法：

在调用 clear 后，不应再访问任何迭代器。
重新初始化迭代器，例如指向 begin() 或 end()。

7.1.5 为什么 `std::list` 的迭代器通常不失效？

std::list 是双向链表，其底层实现是动态分配的节点，每个节点独立存储数据，并通过指针连接。因此：

插入新元素时，现有节点的地址保持不变，现有迭代器不会失效。
删除单个节点时，其他节点的地址保持不变，其迭代器不会失效。

总结

重新获取迭代器：是将迭代器从新指向初始位置

八. `list` 常见的其他修改操作(splice 、merge)

在 C++ 中，std::list 提供了两个强大的成员函数 splice 和 merge，专门用于操作链表的内容，特别适合链表的高效数据操作。以下是它们的介绍及使用方法：

8.1 `splice()` 操作

功能

splice 函数用于将一个 std::list 的元素或整个内容移动到另一个 std::list 中，而无需拷贝数据。
它的时间复杂度是常数级别 O(1)，因为仅需调整指针。

函数重载形式

splice 有三种重载形式：

void splice(iterator pos, list& other) 将 other 的所有元素移动到当前列表 pos 位置之前。
void splice(iterator pos, list& other, iterator it) 将 other 中的单个元素 it 移动到当前列表 pos 位置之前。
void splice(iterator pos, list& other, iterator first, iterator last) 将 other 中从 first 到 last 范围的元素移动到当前列表 pos 位置之前。

8.1.1 使用示例

(1) 移动整个列表

#include <list>
#include <iostream>

int main() {
    std::list<int> list1 = {10, 20, 30};
    std::list<int> list2 = {40, 50, 60};

    auto it = list1.begin();
    ++it; // 指向 20

    list1.splice(it, list2); // 将 list2 的所有元素插入到 list1 的 20 之前

    for (int val : list1) {
        std::cout << val << " "; // 输出 10 40 50 60 20 30
    }

    return 0;
}

（2）移动单个元素

#include <list>
#include <iostream>

int main() {
    std::list<int> list1 = {10, 20, 30};
    std::list<int> list2 = {40, 50, 60};

    auto it1 = list1.begin();
    ++it1; // 指向 20
    auto it2 = list2.begin();
    ++it2; // 指向 50

    list1.splice(it1, list2, it2); // 将 list2 的 50 插入到 list1 的 20 之前

    for (int val : list1) {
        std::cout << val << " "; // 输出 10 50 20 30
    }

    for (int val : list2) {
        std::cout << val << " "; // 输出 40 60
    }

    return 0;
}

（3）移动范围元素

#include <list>
#include <iostream>

int main() {
    std::list<int> list1 = {10, 20, 30};
    std::list<int> list2 = {40, 50, 60, 70};

    auto it1 = list1.begin();
    ++it1; // 指向 20
    auto it2 = list2.begin();
    auto it3 = list2.end();
    --it3; // 指向 70

    list1.splice(it1, list2, it2, it3); // 将 list2 中 40 50 60 插入到 list1 的 20 之前

    for (int val : list1) {
        std::cout << val << " "; // 输出 10 40 50 60 20 30
    }

    for (int val : list2) {
        std::cout << val << " "; // 输出 70
    }

    return 0;
}

8.2 `merge` 函数

功能

merge 函数用于将两个有序 std::list 合并为一个有序列表。
原列表中的元素必须是 升序排序 或根据指定比较函数排序，否则结果未定义。
合并后，other 列表被清空。

函数形式

void merge(list& other) 使用默认的 < 运算符合并两个列表。
void merge(list& other, Compare comp) 使用自定义比较函数 comp 合并两个列表。

8.2.1 使用示例

（1）默认比较

#include <list>
#include <iostream>

int main() {
    std::list<int> list1 = {10, 30, 50};
    std::list<int> list2 = {20, 40, 60};

    list1.merge(list2); // 合并 list2 到 list1，要求两者升序排列

    for (int val : list1) {
        std::cout << val << " "; // 输出 10 20 30 40 50 60
    }

    std::cout << "List2 size: " << list2.size() << std::endl; // 输出 List2 size: 0

    return 0;
}

（2）自定义比较

#include <list>
#include <iostream>

bool compareDescending(int a, int b) {
    return a > b; // 降序比较
}

int main() {
    std::list<int> list1 = {50, 30, 10};
    std::list<int> list2 = {60, 40, 20};

    list1.merge(list2, compareDescending); // 使用降序规则合并

    for (int val : list1) {
        std::cout << val << " "; // 输出 60 50 40 30 20 10
    }

    std::cout << "List2 size: " << list2.size() << std::endl; // 输出 List2 size: 0

    return 0;
}

8.3 splice和merge比较

总结

splice 是链表特有的高效数据操作，适合在多个列表之间移动元素而不进行复制。
merge 适用于有序数据的合并，同时保持排序状态。
两者结合使用，可以灵活、高效地处理链表数据结构中的复杂操作。

九. list的排序与去重

在 C++ 中，std::list 提供了排序和去重的成员函数，使得对链表的排序和去重操作变得非常简便。以下是 std::list 中排序（sort）和去重（unique）功能的详细介绍与使用方法：

9.1 `sort` 函数

功能

sort 用于对 std::list 中的元素进行排序，默认是升序排序。可以自定义比较函数实现降序或其他排序规则。

函数重载形式

void sort() 使用默认的 < 运算符进行升序排序。
void sort(Compare comp) 使用自定义的比较函数 comp 对列表进行排序。

9.1.1 使用实例

（1）使用默认比较排序排升序

#include <list>
#include <iostream>

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

    myList.sort(); // 默认升序排序

    for (int val : myList) {
        std::cout << val << " "; // 输出 10 20 30 40 50
    }

    return 0;
}

（2）使用自定义比较进行降序排序

#include <list>
#include <iostream>

bool compareDescending(int a, int b) {
    return a > b; // 降序比较
}

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

    myList.sort(compareDescending); // 使用自定义降序比较函数

    for (int val : myList) {
        std::cout << val << " "; // 输出 50 40 30 20 10
    }

    return 0;
}

注意事项

std::list::sort 会直接修改原始列表，元素顺序会改变。
默认排序使用 < 运算符，适用于大多数数据类型。如果需要自定义排序，可以通过比较函数传递给 sort。

9.2 `unique` 函数

功能

unique 用于删除 std::list 中相邻的重复元素。该函数仅比较相邻的元素，因此在使用之前，通常需要先对列表进行排序，以确保所有重复元素相邻。
调用 unique 后，链表中的重复元素会被移除，返回一个指向新“末尾”元素的迭代器。

函数重载形式

void unique() 删除相邻的重复元素，使用 operator== 进行比较。
void unique(BinaryPredicate pred) 使用自定义的比较函数 pred，根据指定的规则删除相邻的重复元素。

9.2.1 使用示例

(1) 使用默认比较删除相邻重复元素

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {10, 10, 20, 20, 30, 30, 40};

    myList.unique(); // 删除相邻重复元素

    for (int val : myList) {
        std::cout << val << " "; // 输出 10 20 30 40
    }

    return 0;
}

(2) 使用自定义比较删除相邻重复元素

#include <list>
#include <iostream>

bool compare(int a, int b) {
    return a % 10 == b % 10; // 比较两个元素的个位数是否相等
}

int main() {
    std::list<int> myList = {10, 20, 30, 40, 50, 60};

    myList.unique(compare); // 根据个位数相等删除相邻元素

    for (int val : myList) {
        std::cout << val << " "; // 输出 10 20
    }

    return 0;
}

注意事项

std::list::unique 只会删除相邻的重复元素，如果需要去除所有重复元素，通常先对列表进行排序再调用 unique。
unique 会修改列表的结构，移除的元素将不再存在。

`9.3 sort` 和 `unique` 结合使用

由于 unique 只会删除相邻的重复元素，因此通常我们会在调用 unique 之前先对列表进行排序，以确保重复的元素是相邻的。

示例：排序后去重

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {10, 30, 20, 10, 40, 20, 30};

    myList.sort();    // 排序
    myList.unique();  // 删除相邻的重复元素

    for (int val : myList) {
        std::cout << val << " "; // 输出 10 20 30 40
    }

    return 0;
}

总结

sort：

用于排序列表中的元素，可以使用默认比较（升序）或自定义比较函数。
排序是原地进行的，修改原始列表的顺序。

unique：

用于删除相邻的重复元素。
必须先排序（如果需要删除所有重复元素），然后调用 unique 来删除重复项。
可以使用自定义比较函数来判断元素是否重复。

通过结合使用 sort 和 unique，你可以高效地对链表进行去重和排序操作。

十. list中的swap与reverse函数

10.1 swap函数

功能

swap 用于交换两个 std::list 对象的内容。该操作不需要进行元素的复制或移动，只需要交换内部的数据结构指针，具有常数时间复杂度 O(1)。
交换后的两个列表将互换它们的内容，原列表为空，目标列表变成了原来列表的内容。

函数原型

void swap(list& other);

other：另一个要与当前列表交换内容的 std::list 对象。

10.1.1 使用示例

示例：交换两个列表的内容

#include <list>
#include <iostream>

int main() {
    std::list<int> list1 = {10, 20, 30};
    std::list<int> list2 = {40, 50, 60};

    // 交换 list1 和 list2 的内容
    list1.swap(list2);

    // 输出 list1
    std::cout << "list1: ";
    for (int val : list1) {
        std::cout << val << " "; // 输出 40 50 60
    }

    // 输出 list2
    std::cout << "\nlist2: ";
    for (int val : list2) {
        std::cout << val << " "; // 输出 10 20 30
    }

    return 0;
}

注意事项

swap 是一种非常高效的操作，因为它只交换底层数据的指针，不会涉及到元素的逐一复制或移动。
交换后的列表会变为空，原列表的内容会被完全替换。

10.2 reverse函数

功能

reverse 用于反转 std::list 中元素的顺序，使得列表中的元素顺序完全颠倒。reverse 是原地操作，不会创建新的列表。

函数原型：

void reverse();

10.2.1 使用示例

示例：反转列表

#include <list>
#include <iostream>

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

    // 反转列表
    myList.reverse();

    // 输出反转后的列表
    for (int val : myList) {
        std::cout << val << " "; // 输出 50 40 30 20 10
    }

    return 0;
}

注意事项

reverse 会修改原始列表，使得列表元素的顺序发生变化。
该操作的时间复杂度是 O(n)，其中 n 是列表中元素的数量。

10.3 swap与reverse对比

总结

swap：用于交换两个 std::list 对象的内容，效率极高。适用于需要交换列表内容而不需要拷贝数据的场景。
reverse：用于反转 std::list 中元素的顺序，操作简单且直接。适用于需要颠倒列表元素顺序的场景。

这两个函数都是 std::list 中的非常实用的操作，能够帮助你高效地处理链表中的数据。

十一. list内存管理

11.1 `shrink_to_fit函数`

std::list 是一个基于双向链表的数据结构，其内存管理方式不同于动态数组。每个节点独立分配内存，因此没有额外的“容量”概念，所有的节点内存都是即时分配和释放的。因此，std::list 没有实现 shrink_to_fit 的必要性。

list没有增容概念。

end

在这篇关于 C++ 中 std::list 的详细介绍和使用指南 中，我们系统地学习了 std::list 的基本特性、常见操作及其实际应用。通过本文的学习，你应该已经掌握了以下内容：

std::list 的基本构造和容量管理方法：如何创建列表、访问元素以及判断列表是否为空等。
迭代器的使用：熟悉如何遍历和操作列表元素，并理解迭代器失效问题及其规避方法。
插入、删除和修改操作：灵活管理列表中的元素，快速进行动态调整。
高级功能：如排序（sort）、去重（unique）、合并（merge）、反转（reverse）、交换（swap）等。
性能优化：通过合适的操作，如交换空列表或重新构造，释放不必要的内存。

std::list 是 C++ 标准库中功能强大且灵活的容器之一，尤其在需要频繁插入和删除操作的场景中表现优异。虽然它的随机访问性能不如动态数组（如 std::vector），但在需要高效的动态调整和稳定迭代器的场景中，std::list 是一个不可替代的选择。

通过本文的学习，你不仅可以熟练地操作 std::list，还能够根据项目需求选择合适的数据结构，编写出更高效、更健壮的代码。希望本文能为你未来的开发提供帮助！

如果你还有任何问题，欢迎随时提出，我们一起探讨与学习！ 🚀

下一篇文章再会！！！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-11-25，如有侵权请联系 cloudcommunity@tencent.com 删除

list

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！