STLDay2

std::list

简介：双向链表，大小可动态调整，用于频繁插入或删除。支持双向遍历。

注：

list同vector极其类似！！！！！

#include <iostream>
#include <list>

int main() {
    // 初始化
    std::list<int> list = {1, 2, 3, 4};

    // 添加元素
    list.push_back(5);  // 尾部插入
    list.push_front(0); // 头部插入

    // 删除元素
    list.pop_back();  // 删除尾部元素
    list.pop_front(); // 删除头部元素

    // 遍历元素
    std::cout << "Elements: ";
    for (int i : list) {
        std::cout << i << " "; // 输出: 1 2 3 4
    }
    std::cout << std::endl;

    // 访问元素
    std::cout << "First element: " << list.front() << std::endl; // 输出: 1
    std::cout << "Last element: " << list.back() << std::endl;   // 输出: 4

    // 获取大小
    std::cout << "Size: " << list.size() << std::endl; // 输出: 4

    return 0;
}

1.初始化

#include <list>
// 默认初始化
std::list<int> list1;
// 初始化大小为 5，所有元素为 0
std::list<int> list2(5);
// 初始化大小为 5，所有元素为 42
std::list<int> list3(5, 42);
// 使用初始化列表
std::list<int> list4 = {1, 2, 3, 4, 5};

2.添加元素

list.push_back(6);  // 在尾部插入元素 6
list.push_front(0); // 在头部插入元素 0
list.insert(it, 10); // 在迭代器 it 指向的位置插入元素 10

3.删除元素

list.pop_back();  // 删除尾部元素
list.pop_front(); // 删除头部元素
list.erase(it);   // 删除迭代器 it 指向的元素
list.clear();     // 清空所有元素

4.访问元素

int first = list.front(); // 访问头部元素
int last = list.back();   // 访问尾部元素
//访问内部元素同 vector 类似！！！

5.获取大小

size_t size = list.size(); // 获取元素数量
bool isEmpty = list.empty(); // 判断是否为空

6.遍历元素（范围-based for 循环&使用迭代器）

// 使用范围-based for 循环
for (int i : list) {
    std::cout << i << " ";
}

// 使用迭代器
for (auto it = list.begin(); it != list.end(); ++it) {
    std::cout << *it << " ";
}

7.排序和合并

list.sort(); // 对链表进行排序
list.merge(otherList); // 合并另一个链表

merge()

语法：

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

• merge(other):
  • 直接合并 other 到当前 std::list，默认按 升序 合并，要求 this 和 other 都是 已排序的。
  • other 变为空链表。
• merge(other, comp):
  • 允许使用 自定义比较函数 comp（如降序或自定义排序方式）进行合并。

1）合并两个已排序的链表

#include <iostream>
#include <list>
int main() {
    std::list<int> list1 = {1, 3, 5, 7};
    std::list<int> list2 = {2, 4, 6, 8};

    // 合并 list2 到 list1
    list1.merge(list2);

    // 输出合并后的 list1
    std::cout << "Merged list: ";
    for (int num : list1) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 输出 list2（应该为空）
    std::cout << "List2 is now empty, size: " << list2.size() << std::endl;

    return 0;
}

输出

Merged list: 1 2 3 4 5 6 7 8
List2 is now empty, size: 0

---

2）使用 merge() 进行降序合并

如果两个链表是 降序排序的，你需要提供自定义的比较函数 comp 来确保合并后的顺序正确。

#include <iostream>
#include <list>

bool descending(int a, int b) {
    return a > b;  // 降序排列
}

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

    // 使用自定义比较函数进行合并
    list1.merge(list2, descending);

    // 输出合并后的 list1
    std::cout << "Merged list in descending order: ";
    for (int num : list1) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出

Merged list in descending order: 8 7 6 5 4 3 2 1

注意事项

1. merge() 只适用于已排序的 std::list

   • 两个链表必须是已排序的，否则合并结果可能是错误的！

   • 如果 list1 或 list2 不是有序的，先调用 sort() 进行排序：

     list1.sort();
     list2.sort();
     list1.merge(list2);

2. 合并后，other 变为空

   • merge() 不会创建新链表，而是直接修改 this 并清空 other，所以合并后 other.size() 变为 0。

3. merge() 只适用于 std::list

   • 由于 std::list 采用的是 双向链表，其 merge() 操作是 O(N) 复杂度（线性时间）。
   • std::vector **没有 merge()**，因为 std::vector 采用的是动态数组，不支持高效的合并。