c++ std::list使用笔记

1. 包含头文件

使用 std::list 需要包含头文件 <list>。

#include <list>
#include <iostream>

2. 创建和初始化 std::list

• 默认构造函数：创建一个空的 list。
• 初始化列表：用花括号 {} 初始化。
• 拷贝构造函数：从另一个 list 拷贝。

std::list<int> list1;                // 空列表
std::list<int> list2 = {1, 2, 3};    // 初始化列表: [1, 2, 3]
std::list<int> list3(list2);         // 拷贝构造: list3 = [1, 2, 3]

3. 添加元素

• push_back(value)：在链表末尾添加元素。
• push_front(value)：在链表开头添加元素。
• insert(iterator pos, value)：在指定位置插入元素。

std::list<int> myList = {1, 2, 3};
myList.push_back(4);       // myList: [1, 2, 3, 4]
myList.push_front(0);      // myList: [0, 1, 2, 3, 4]
myList.insert(++myList.begin(), 10);  // myList: [0, 10, 1, 2, 3, 4]

4. 删除元素

• pop_back()：删除链表末尾的元素。
• pop_front()：删除链表开头的元素。
• erase(iterator pos)：删除指定位置的元素。
• erase(iterator first, iterator last)：删除范围 [first, last) 内的元素。
• clear()：清空链表。

std::list<int> myList = {1, 2, 3, 4, 5};
myList.pop_back();         // myList: [1, 2, 3, 4]
myList.pop_front();        // myList: [2, 3, 4]
myList.erase(++myList.begin());  // myList: [2, 4]
myList.clear();            // myList: []

5. 访问元素

• front()：返回链表第一个元素。
• back()：返回链表最后一个元素。

注意：std::list 不支持随机访问（如 operator[] 或 at()），因为它是链表结构。

std::list<int> myList = {1, 2, 3};
std::cout << "Front: " << myList.front() << std::endl;  // 输出: Front: 1
std::cout << "Back: " << myList.back() << std::endl;    // 输出: Back: 3

6. 遍历 std::list

• 范围 for 循环：

  std::list<int> myList = {1, 2, 3};
  for (int val : myList) {
      std::cout << val << " ";  // 输出: 1 2 3
  }
  

• 迭代器：

  std::list<int> myList = {1, 2, 3};
  for (auto it = myList.begin(); it != myList.end(); ++it) {
      std::cout << *it << " ";  // 输出: 1 2 3
  }
  

7. 容量相关操作

• size()：返回链表中元素的数量。
• empty()：判断链表是否为空。
• max_size()：返回链表可以容纳的最大元素数量。

std::list<int> myList = {1, 2, 3};
std::cout << "Size: " << myList.size() << std::endl;  // 输出: Size: 3
std::cout << "Empty: " << myList.empty() << std::endl;  // 输出: Empty: 0 (false)
std::cout << "Max size: " << myList.max_size() << std::endl;

8. 其他常用操作

• sort()：对链表进行排序。
• reverse()：反转链表。
• merge(list& other)：合并两个有序链表。
• unique()：删除连续重复的元素。

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

list1.sort();           // list1: [1, 2, 3]
list2.sort();           // list2: [4, 5]
list1.merge(list2);     // list1: [1, 2, 3, 4, 5], list2: []
list1.reverse();        // list1: [5, 4, 3, 2, 1]
list1.unique();         // 如果链表中有连续重复元素，会删除重复项

9. 示例代码

#include <iostream>
#include <list>

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

    // 添加元素
    myList.push_back(4);
    myList.push_front(0);

    // 遍历
    std::cout << "List: ";
    for (int val : myList) {
        std::cout << val << " ";  // 输出: 0 1 2 3 4
    }
    std::cout << std::endl;

    // 删除元素
    myList.pop_back();
    myList.pop_front();

    // 访问元素
    std::cout << "Front: " << myList.front() << std::endl;  // 输出: Front: 1
    std::cout << "Back: " << myList.back() << std::endl;    // 输出: Back: 3

    // 排序和反转
    myList.sort();
    myList.reverse();

    std::cout << "After sort and reverse: ";
    for (int val : myList) {
        std::cout << val << " ";  // 输出: 3 2 1
    }
    std::cout << std::endl;

    return 0;
}

总结

std::list 是一个双向链表，适合频繁在任意位置插入和删除元素的场景。它的主要特点是：

• 插入和删除操作的时间复杂度为 O(1)。
• 不支持随机访问，只能通过迭代器遍历。
• 提供了排序、反转、合并等操作。

根据需求选择合适的容器（如 std::vector 或 std::list）可以显著提高程序性能。