关注

顺序容器：list双向链表 详解

目录

前言

一、定义及初始化

1.定义 list 对象

2.初始化方式

二、向 list 对象中添加元素

1.在前端添加元素

2.在后端添加元素

3.在中间插入元素

三、list 常用迭代器

四、list 常用运算符

五、list 常用成员函数

1.empty 成员函数

2.size 成员函数

3.front 成员函数

4.push_front 成员函数

5.pop_front 成员函数

6.back 成员函数

7.push_back 成员函数

8.pop_back 成员函数

9.insert 成员函数

10.erase 成员函数

11.swap 成员函数

12.clear 成员函数

六、list 特有成员函数

1.merge 特有成员函数

2.remove 特有成员函数

3.remove_if 特有成员函数

4.reverse 特有成员函数

5.sort 特有成员函数

6.splice 特有成员函数

7.unique 特有成员函数

七、综合练习

练习 1：list 基本操作

练习 2：使用 list 特有成员函数

练习 3：使用 list 实现一个简单的链表

前言

        STL中的list是一个双向循环链表,如下图所示:

        第一个参数是任何数据类型,第二个参数可有可无。

        list对象自带两个指针,一个指向第一个元素,另一个指向最后一个元素。

因此list在如下几个主要方面与array、 vector 或deque不同:

●list不支持随机访问,如果你要访问第5个元素，就得顺着链表逐一遍历前 4个元素。所以，在 list中随机访问任意元素是很缓慢的。然而访问第一个和最后一个元素的速度很快。

●任何位置(不只两端)插入和删除都非常快，在常量时间内完成,因为无须移动其他元素。只需要进行一些指针操作。

list提供的比较好用的函数:

●list提供front,push_front,pop_front和back,push_back,pop_back等函数

●由于不支持随机访问,list即不支持下标操作也不支持at函数。

●list提供不少特殊成员函数,专门用于移动和删除元素,和同名的STL通用算法相比,这些函数执行起来更快速,优先使用list自己提供的算法。

一、定义及初始化

   list 是 C++ 标准库中的一个双向链表容器，定义在 <list> 头文件中，位于 std 命名空间内。它支持在任意位置高效地插入和删除元素，但不支持随机访问。

        使用list时必须先包含头文件<list>：

#include <list>

1.定义 list 对象

#include <list>

// 定义一个存储 int 类型的 list
std::list<int> lst;

// 定义一个存储 std::string 类型的 list
std::list<std::string> strLst;

2.初始化方式

  1. 默认初始化：创建一个空 list

    std::list<int> lst; // 空 list

  2. 列表初始化：

    std::list<int> lst = {1, 2, 3, 4, 5};
std::list<int> lst2{1, 2, 3, 4, 5}; // 与上面等价

  3. 指定元素个数和初始值：

    std::list<int> lst(5, 10); // 包含 5 个元素，每个元素值为 10

  4. 使用另一个 list 初始化：

    std::list<int> lst1 = {1, 2, 3, 4, 5};
std::list<int> lst2 = lst1; // 拷贝初始化
std::list<int> lst3(lst1); // 拷贝构造

  5. 使用迭代器范围初始化：

    std::list<int> lst1 = {1, 2, 3, 4, 5};
std::list<int> lst2(lst1.begin(), lst1.end()); // 包含 lst1 的所有元素

// 从其他容器初始化
std::vector<int> vec = {6, 7, 8, 9, 10};
std::list<int> lst3(vec.begin(), vec.end()); // 包含 vec 的所有元素

二、向 list 对象中添加元素

list 支持在任意位置高效地添加元素，尤其是在两端和已知位置。

1.在前端添加元素

  1. push_front 成员函数：

    • 功能：在 list 前端添加一个元素
    • 参数：要添加的元素值
    • 返回值：无
    std::list<int> lst = {2, 3, 4};
lst.push_front(1); // lst 现在包含 {1, 2, 3, 4}

  2. emplace_front 成员函数（C++11）：

    • 功能：在 list 前端直接构造一个元素
    • 参数：构造元素所需的参数
    • 返回值：无
    • 优点：避免了额外的拷贝或移动操作，比 push_front 更高效
    std::list<std::pair<int, std::string>> lst;
lst.emplace_front(1, "one"); // 直接在前端构造 pair 对象
lst.push_front({2, "two"}); // 先构造临时 pair 对象，再移动到前端

2.在后端添加元素

  1. push_back 成员函数：

    • 功能：在 list 后端添加一个元素
    • 参数：要添加的元素值
    • 返回值：无
    std::list<int> lst = {1, 2, 3};
lst.push_back(4); // lst 现在包含 {1, 2, 3, 4}
lst.push_back(5); // lst 现在包含 {1, 2, 3, 4, 5}

  2. emplace_back 成员函数（C++11）：

    • 功能：在 list 后端直接构造一个元素
    • 参数：构造元素所需的参数
    • 返回值：无
    • 优点：避免了额外的拷贝或移动操作，比 push_back 更高效
    std::list<std::pair<int, std::string>> lst;
lst.emplace_back(1, "one"); // 直接在后端构造 pair 对象
lst.push_back({2, "two"}); // 先构造临时 pair 对象，再移动到后端

3.在中间插入元素

  1. insert 成员函数：

    • 功能：在指定位置插入元素
    • 参数：
      • 版本 1：pos, value - 在迭代器 pos 前插入 value
      • 版本 2：pos, count, value - 在迭代器 pos 前插入 count 个 value
      • 版本 3：pos, first, last - 在迭代器 pos 前插入迭代器范围 [first, last) 中的元素
    • 返回值：指向新插入的第一个元素的迭代器
    • 说明：在 list 中插入元素的效率很高，因为只需要修改指针，不需要移动元素
    std::list<int> lst = {1, 2, 4, 5};

// 在位置 2 前插入元素 3
auto it = lst.begin();
std::advance(it, 2); // 将迭代器移动到位置 2
lst.insert(it, 3); // lst 现在包含 {1, 2, 3, 4, 5}

// 在位置 0 前插入 2 个 0
lst.insert(lst.begin(), 2, 0); // lst 现在包含 {0, 0, 1, 2, 3, 4, 5}

// 在末尾插入另一个 list 的元素
std::list<int> lst2 = {6, 7, 8};
lst.insert(lst.end(), lst2.begin(), lst2.end()); // lst 现在包含 {0, 0, 1, 2, 3, 4, 5, 6, 7, 8}

  2. emplace 成员函数（C++11）：

    • 功能：在指定位置直接构造一个元素
    • 参数：
      • pos - 插入位置的迭代器
      • 构造元素所需的参数
    • 返回值：指向新构造元素的迭代器
    • 优点：避免了额外的拷贝或移动操作
    std::list<std::pair<int, std::string>> lst;
auto it = lst.begin();
lst.emplace(it, 1, "one"); // 直接在指定位置构造 pair 对象

三、list 常用迭代器

   list 容器提供了多种迭代器类型，用于遍历容器中的元素。需要注意的是，list 的迭代器是双向迭代器，不支持随机访问（如 it + 5 这样的操作）。

迭代器

含义

l.begin()

第一个元素的迭代器

l.end()

最后一个元素的下一个位置迭代器(尾后迭代器或尾迭代器)

l.cbegin()

第一个元素的常量迭代器(不修改元素内容)

l.cend()

尾后常量迭代器(不修改元素内容)

l.rbegin()

从后往前的第一个迭代器

l.rend()

从后往前的最后一个迭代器

l.crbegin()

从后往前的第一个常量迭代器

l.crend()

从后往前的最后一个常量迭代器

使用示例：

std::list<int> lst = {1, 2, 3, 4, 5};

// 使用正向迭代器遍历
for (auto it = lst.begin(); it != lst.end(); ++it) {
    std::cout << *it << " "; // 输出: 1 2 3 4 5
}
std::cout << std::endl;

// 使用反向迭代器遍历
for (auto it = lst.rbegin(); it != lst.rend(); ++it) {
    std::cout << *it << " "; // 输出: 5 4 3 2 1
}
std::cout << std::endl;

// 使用常量迭代器遍历（不能修改元素）
for (auto it = lst.cbegin(); it != lst.cend(); ++it) {
    std::cout << *it << " "; // 输出: 1 2 3 4 5
    // *it = 10; // 错误：常量迭代器不能修改元素
}
std::cout << std::endl;

// 移动迭代器
auto it = lst.begin();
std::advance(it, 2); // 将迭代器移动 2 个位置
std::cout << "Element at position 2: " << *it << std::endl; // 输出: 3

四、list 常用运算符

list 类重载了多种运算符，方便容器操作：

  1. 赋值运算符：

    • =：将一个 list 赋值给另一个 list
    std::list<int> lst1 = {1, 2, 3};
std::list<int> lst2;
lst2 = lst1; // lst2 现在包含 {1, 2, 3}

  2. 比较运算符：

    • ==：判断两个 list 是否相等
    • !=：判断两个 list 是否不相等
    • <：判断一个 list 是否小于另一个 list（字典序）
    • <=：判断一个 list 是否小于或等于另一个 list
    • >：判断一个 list 是否大于另一个 list
    • >=：判断一个 list 是否大于或等于另一个 list
    std::list<int> lst1 = {1, 2, 3};
std::list<int> lst2 = {1, 2, 4};
bool b1 = (lst1 == lst2); // false
bool b2 = (lst1 < lst2);  // true（第三个元素 3 < 4）

五、list 常用成员函数

list l的成员函数

含义

l.empty()

判断是否为空

l.size()

返回 l 的数据个数 ,重要函数

l.front()

返回第一个元素的引用 ,重要函数

l.push_front()

头插 ,重要函数

l.pop_front()

头删 ,重要函数

l.back()

返回最后一个元素的引用 ,重要函数

l.push_back()

尾插 ,重要函数

l.pop_back()

尾删 ,重要函数

l.insert()

插入一个或多个元素,这个效率为常数 ,重要函数

l.erase()

删除一个或多个元素 ,重要函数

l.swap()

交换两个list的值 ,重要函数

l.clear()

清空数据

1.empty 成员函数

  • 功能：判断 list 是否为空
  • 参数：无
  • 返回值：如果 list 为空返回 true，否则返回 false
std::list<int> lst1;
std::list<int> lst2 = {1, 2, 3};
std::cout << lst1.empty(); // 输出: 1 (true)
std::cout << lst2.empty(); // 输出: 0 (false)

2.size 成员函数

  • 功能：返回 list 中元素的个数
  • 参数：无
  • 返回值：元素个数，类型为 size_t
std::list<int> lst = {1, 2, 3, 4, 5};
std::cout << lst.size(); // 输出: 5

3.front 成员函数

  • 功能：返回 list 中第一个元素的引用
  • 参数：无
  • 返回值：第一个元素的引用
  • 说明：如果 list 为空，行为未定义
std::list<int> lst = {1, 2, 3};
std::cout << lst.front(); // 输出: 1
lst.front() = 10;         // lst 现在包含 {10, 2, 3}

4.push_front 成员函数

  • 功能：在 list 前端添加一个元素
  • 参数：要添加的元素值
  • 返回值：无
std::list<int> lst = {2, 3, 4};
lst.push_front(1); // lst 现在包含 {1, 2, 3, 4}

5.pop_front 成员函数

  • 功能：删除 list 前端的一个元素
  • 参数：无
  • 返回值：无
  • 说明：如果 list 为空，行为未定义
std::list<int> lst = {1, 2, 3, 4};
lst.pop_front(); // lst 现在包含 {2, 3, 4}
lst.pop_front(); // lst 现在包含 {3, 4}

6.back 成员函数

  • 功能：返回 list 中最后一个元素的引用
  • 参数：无
  • 返回值：最后一个元素的引用
  • 说明：如果 list 为空，行为未定义
std::list<int> lst = {1, 2, 3};
std::cout << lst.back(); // 输出: 3
lst.back() = 30;         // lst 现在包含 {1, 2, 30}

7.push_back 成员函数

  • 功能：在 list 后端添加一个元素
  • 参数：要添加的元素值
  • 返回值：无
std::list<int> lst = {1, 2, 3};
lst.push_back(4); // lst 现在包含 {1, 2, 3, 4}
lst.push_back(5); // lst 现在包含 {1, 2, 3, 4, 5}

8.pop_back 成员函数

  • 功能：删除 list 后端的一个元素
  • 参数：无
  • 返回值：无
  • 说明：如果 list 为空，行为未定义
std::list<int> lst = {1, 2, 3, 4, 5};
lst.pop_back(); // lst 现在包含 {1, 2, 3, 4}
lst.pop_back(); // lst 现在包含 {1, 2, 3}

9.insert 成员函数

  • 功能：在指定位置插入元素
  • 参数：
    • 版本 1：pos, value - 在迭代器 pos 前插入 value
    • 版本 2：pos, count, value - 在迭代器 pos 前插入 count 个 value
    • 版本 3：pos, first, last - 在迭代器 pos 前插入迭代器范围 [first, last) 中的元素
  • 返回值：指向新插入的第一个元素的迭代器
std::list<int> lst = {1, 2, 4, 5};

// 在位置 2 前插入元素 3
auto it = lst.begin();
std::advance(it, 2); // 将迭代器移动到位置 2
lst.insert(it, 3); // lst 现在包含 {1, 2, 3, 4, 5}

10.erase 成员函数

  • 功能：删除 list 中的元素
  • 参数：
    • 版本 1：pos - 删除迭代器 pos 指向的元素
    • 版本 2：first, last - 删除迭代器范围 [first, last) 中的元素
  • 返回值：指向被删除元素之后位置的迭代器
std::list<int> lst = {1, 2, 3, 4, 5};

// 删除位置 2 的元素
auto it = lst.begin();
std::advance(it, 2); // 将迭代器移动到位置 2
it = lst.erase(it); // lst 现在包含 {1, 2, 4, 5}，it 指向 4

// 删除从位置 1 到位置 2 的元素
auto start = lst.begin();
std::advance(start, 1); // 移动到位置 1
auto end = start;
std::advance(end, 2); // 移动到位置 3
lst.erase(start, end); // lst 现在包含 {1, 5}

11.swap 成员函数

  • 功能：交换两个 list 的内容
  • 参数：另一个 list 对象
  • 返回值：无
std::list<int> lst1 = {1, 2, 3};
std::list<int> lst2 = {4, 5, 6};
lst1.swap(lst2); // lst1 现在包含 {4, 5, 6}，lst2 现在包含 {1, 2, 3}

12.clear 成员函数

  • 功能：删除 list 中的所有元素
  • 参数：无
  • 返回值：无
std::list<int> lst = {1, 2, 3, 4, 5};
lst.clear();
std::cout << lst.size(); // 输出: 0
std::cout << lst.empty(); // 输出: 1 (true)

六、list 特有成员函数

list l特有成员函数

含义

l.merge()

链表合并

l.remove(val)

删除所有和val相同元素

l.remove_if()

删除符合条件的元素

l.reverse()

反转链表中的元素

l.sort()

排序(默认为升序)

l.splice()

链表连结

l.unique()

删除重复元素

1.merge 特有成员函数

  • 功能：合并两个已排序的 list
  • 参数：
    • other - 另一个已排序的 list
  • 返回值：无
  • 说明：合并后，other 变为空
std::list<int> lst1 = {1, 3, 5};
std::list<int> lst2 = {2, 4, 6};
lst1.merge(lst2); // lst1 现在包含 {1, 2, 3, 4, 5, 6}，lst2 为空

2.remove 特有成员函数

  • 功能：删除所有值等于指定值的元素
  • 参数：要删除的值
  • 返回值：无
std::list<int> lst = {1, 2, 3, 2, 4, 2, 5};
lst.remove(2); // lst 现在包含 {1, 3, 4, 5}

3.remove_if 特有成员函数

  • 功能：删除所有满足指定条件的元素
  • 参数：一个返回 bool 的函数对象或 lambda 表达式
  • 返回值：无
std::list<int> lst = {1, 2, 3, 4, 5, 6};

// 删除所有偶数
lst.remove_if([](int n) { return n % 2 == 0; }); // lst 现在包含 {1, 3, 5}

4.reverse 特有成员函数

  • 功能：反转 list 中元素的顺序
  • 参数：无
  • 返回值：无
std::list<int> lst = {1, 2, 3, 4, 5};
lst.reverse(); // lst 现在包含 {5, 4, 3, 2, 1}

5.sort 特有成员函数

  • 功能：对 list 中的元素进行排序
  • 参数：可选的比较函数
  • 返回值：无
std::list<int> lst = {5, 2, 8, 1, 9};
lst.sort(); // lst 现在包含 {1, 2, 5, 8, 9}

// 使用自定义比较函数（降序）
lst.sort(std::greater<int>()); // lst 现在包含 {9, 8, 5, 2, 1}

6.splice 特有成员函数

  • 功能：将一个 list 中的元素转移到另一个 list 中
  • 参数：
    • 版本 1：pos, other - 将 other 中的所有元素转移到 pos 前
    • 版本 2：pos, other, it - 将 other 中 it 指向的元素转移到 pos 前
    • 版本 3：pos, other, first, last - 将 other 中 [first, last) 范围内的元素转移到 pos 前
  • 返回值：无
  • 说明：转移后，原 list 中的元素被移除
std::list<int> lst1 = {1, 2, 3};
std::list<int> lst2 = {4, 5, 6};

// 将 lst2 中的所有元素转移到 lst1 的末尾
lst1.splice(lst1.end(), lst2); 
// lst1 现在包含 {1, 2, 3, 4, 5, 6}，lst2 为空

// 重新初始化 lst2
lst2 = {7, 8, 9};

// 将 lst2 中的第一个元素转移到 lst1 的开头
auto it = lst2.begin();
lst1.splice(lst1.begin(), lst2, it); 
// lst1 现在包含 {7, 1, 2, 3, 4, 5, 6}，lst2 现在包含 {8, 9}

7.unique 特有成员函数

  • 功能：删除连续的重复元素，只保留一个
  • 参数：可选的比较函数
  • 返回值：无
std::list<int> lst = {1, 1, 2, 2, 2, 3, 4, 4, 5};
lst.unique(); // lst 现在包含 {1, 2, 3, 4, 5}

七、综合练习

练习 1：list 基本操作

#include <iostream>
#include <list>

int main() {
    // 创建并初始化 list
    std::list<int> lst = {3, 4, 5};
    
    // 在前端添加元素
    lst.push_front(2);
    lst.push_front(1);
    
    // 在后端添加元素
    lst.push_back(6);
    lst.push_back(7);
    
    // 输出当前 list
    std::cout << "Current list: ";
    for (int x : lst) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    // 访问元素
    std::cout << "Front: " << lst.front() << std::endl;
    std::cout << "Back: " << lst.back() << std::endl;
    
    // 删除前端和后端元素
    lst.pop_front();
    lst.pop_back();
    
    // 输出修改后的 list
    std::cout << "After pop_front and pop_back: ";
    for (int x : lst) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    // 在中间插入元素
    auto it = lst.begin();
    std::advance(it, 2);
    lst.insert(it, 10);
    
    // 输出插入后的 list
    std::cout << "After insert: ";
    for (int x : lst) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    // 删除中间元素
    it = lst.begin();
    std::advance(it, 1);
    lst.erase(it);
    
    // 输出删除后的 list
    std::cout << "After erase: ";
    for (int x : lst) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    // 检查 list 状态
    std::cout << "Size: " << lst.size() << std::endl;
    std::cout << "Empty: " << (lst.empty() ? "Yes" : "No") << std::endl;
    
    return 0;
}

练习 2：使用 list 特有成员函数

#include <iostream>
#include <list>

int main() {
    // 创建并初始化 list
    std::list<int> lst = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // 排序
    lst.sort();
    std::cout << "After sort: ";
    for (int x : lst) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    // 反转
    lst.reverse();
    std::cout << "After reverse: ";
    for (int x : lst) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    // 创建另一个 list 并合并
    std::list<int> lst2 = {10, 11, 12};
    lst.merge(lst2);
    std::cout << "After merge: ";
    for (int x : lst) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    std::cout << "lst2 size: " << lst2.size() << std::endl; // 应该为 0
    
    // 添加重复元素并去重
    lst.push_back(5);
    lst.push_back(5);
    lst.push_back(7);
    std::cout << "Before unique: ";
    for (int x : lst) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    lst.unique();
    std::cout << "After unique: ";
    for (int x : lst) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    // 删除特定元素
    lst.remove(5);
    std::cout << "After remove 5: ";
    for (int x : lst) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    // 删除满足条件的元素
    lst.remove_if([](int n) { return n > 8; });
    std::cout << "After remove_if (>8): ";
    for (int x : lst) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

练习 3：使用 list 实现一个简单的链表

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

class Student {
public:
    std::string name;
    int age;
    double score;
    
    Student(std::string n, int a, double s) : name(n), age(a), score(s) {}
    
    void display() const {
        std::cout << "Name: " << name << ", Age: " << age << ", Score: " << score << std::endl;
    }
};

// 自定义比较函数，按分数降序排序
bool compareByScore(const Student& s1, const Student& s2) {
    return s1.score > s2.score;
}

int main() {
    // 创建存储 Student 对象的 list
    std::list<Student> students;
    
    // 添加学生
    students.emplace_back("Alice", 18, 95.5);
    students.emplace_back("Bob", 19, 88.0);
    students.emplace_back("Charlie", 17, 92.5);
    students.emplace_back("David", 18, 85.0);
    
    // 显示所有学生
    std::cout << "All students: " << std::endl;
    for (const auto& student : students) {
        student.display();
    }
    
    // 按分数排序
    students.sort(compareByScore);
    std::cout << "\nStudents sorted by score: " << std::endl;
    for (const auto& student : students) {
        student.display();
    }
    
    // 删除年龄小于 18 的学生
    students.remove_if([](const Student& s) { return s.age < 18; });
    std::cout << "\nStudents after removing under 18: " << std::endl;
    for (const auto& student : students) {
        student.display();
    }
    
    // 反转顺序
    students.reverse();
    std::cout << "\nStudents in reverse order: " << std::endl;
    for (const auto& student : students) {
        student.display();
    }
    
    return 0;
}

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2402_82668550/article/details/159514288

评论

赞0

评论列表

微信小程序
QQ小程序

关于作者

点赞数：0
关注数：0
粉丝：0
文章：0
关注标签：0
加入于：--