C++ list

发布于:2025-03-17 ⋅ 阅读:(21) ⋅ 点赞:(0)

1. ​std::list 基本概念

  • 定义std::list 是 C++ 标准库提供的带头(哨兵位)双向循环链表容器,支持高效的元素插入和删除。
  • 头文件#include <list>

2. ​构造函数

(1) ​默认构造函数
list<int> list1;  // 创建一个空list,size=0
(2) ​指定初始大小和默认值
list<int> list2(5);       // 5个元素,默认初始化(int为0)
list<double> list3(5, 3.14);  // 5个元素,每个值为3.14
(3) ​通过迭代器范围构造
int arr[] = {1, 2, 3};
list<int> list4(arr, arr + 3);  // 复制数组的[arr, arr+3)范围元素
(4) ​拷贝构造函数
list<int> list5(list4);  // 深拷贝list4的内容

3. ​修改元素的成员函数

(1) ​push_back() 和 push_front()

在末尾或头部添加元素:

list<int> lst;
lst.push_back(10);   // 末尾添加10 → {10}
lst.push_front(5);   // 头部添加5 → {5, 10}
(2) ​insert()

插入元素到指定位置,支持以下重载:

  • 插入单个值
    list<int> lst = {1, 3};
    list<int>::iterator it = lst.begin();
    ++it;
    lst.insert(it, 2);  // 在位置1插入2 → {1, 2, 3}
  • 插入多个相同值
    lst.insert(lst.end(), 2, 4);  // 在末尾插入2个4 → {1, 2, 3, 4, 4}
  • 通过迭代器范围插入
    int arr[] = {5, 6};
    lst.insert(lst.end(), arr, arr + 2);  // 插入数组内容 → {1, 2, 3, 4, 4, 5, 6}
(3) ​erase()

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

  • 删除单个元素
    list<int>::iterator it = lst.begin();
    ++it;
    lst.erase(it);  // 删除位置1的元素 → {1, 3, 4, 4, 5, 6}
  • 删除范围元素
    list<int>::iterator first = lst.begin();
    advance(first, 3);  // 移动到位置3
    lst.erase(first, lst.end());  // 删除位置3到末尾 → {1, 3, 4}
(4) ​clear()

清空所有元素:

lst.clear();  // size=0
(5) ​assign()

重新分配元素(覆盖原有内容):

  • 指定数量和值
    lst.assign(3, 10);  // 3个10 → {10, 10, 10}
  • 通过迭代器范围
    int arr[] = {20, 30, 40};
    lst.assign(arr, arr + 2);  // 复制前2个元素 → {20, 30}

4. ​访问元素的成员函数

(1) ​front() 和 back()

访问首尾元素:

int first = lst.front();  // 第一个元素
int last = lst.back();    // 最后一个元素

5. ​容量管理的成员函数

(1) ​size()

获取元素数量:

size_t s = lst.size();  // 当前元素数量
(2) ​resize()

调整元素数量:

lst.resize(5);      // 调整size=5,多出的元素默认初始化(int为0)
lst.resize(3, 100); // 调整size=3,若需要新增元素则初始化为100

6. ​链表特有操作

(1) ​splice()

将另一个链表的元素移动(拼接)到当前链表,支持以下重载:

  • 移动整个链表
    list<int> lst1 = {1, 2};
    list<int> lst2 = {3, 4};
    lst1.splice(lst1.end(), lst2);  // lst1 → {1, 2, 3, 4}, lst2变为空
  • 移动单个元素
    list<int> lst3 = {5, 6};
    list<int>::iterator it = lst3.begin();
    lst1.splice(lst1.begin(), lst3, it);  // lst1 → {5, 1, 2, 3, 4}, lst3 → {6}
  • 移动范围元素
    list<int> lst4 = {7, 8, 9};
    list<int>::iterator first = lst4.begin();
    list<int>::iterator last = lst4.end();
    --last;
    lst1.splice(lst1.end(), lst4, first, last);  // lst1 → {5, 1, 2, 3, 4, 7, 8}, lst4 → {9}
(2) ​remove()

删除特定元素:

  • remove()
    list<int> lst = {1, 2, 3, 2, 4};
    lst.remove(2);  // 删除所有值为2的元素 → {1, 3, 4}
(3) ​sort() 和 merge()

排序和合并链表:

  • sort()
    list<int> lst = {3, 1, 4, 2};
    lst.sort();  // 默认升序 → {1, 2, 3, 4}
  • merge()(要求两个链表已排序):
    list<int> lst1 = {1, 3};
    list<int> lst2 = {2, 4};
    lst1.merge(lst2);  // lst1 → {1, 2, 3, 4}, lst2变为空
(4) ​unique()

删除连续重复元素(需先排序):

list<int> lst = {1, 1, 2, 3, 3};
lst.unique();  // 删除连续重复 → {1, 2, 3}
(5) ​reverse()

反转链表元素顺序:

list<int> lst = {1, 2, 3};
lst.reverse();  // → {3, 2, 1}

7. ​迭代器操作

  • begin() 和 end()
    for (list<int>::iterator it = lst.begin(); it != lst.end(); ++it) {
        cout << *it << " ";
    }
  • rbegin() 和 rend()(反向迭代器)​:
    for (list<int>::reverse_iterator rit = lst.rbegin(); rit != lst.rend(); ++rit) {
        cout << *rit << " ";
    }

8. ​注意事项

  • 迭代器失效:删除操作仅使被删除元素的迭代器失效,其他迭代器仍然有效(后面我会专门整理这个问题)。
  • 性能特点:插入和删除操作高效,但随机访问效率低(需遍历链表)。
  • 排序与合并sort() 和 merge() 是成员函数,不同于 <algorithm> 中的全局函数。

网站公告

今日签到

点亮在社区的每一天
去签到