List

List是一个能够存放任意性别的双向链表（doubly linked list)

可以向List中介入一个子链表
为了使用List，必须用include指令包含如下文件，并通过std命名空间去访问：

#include <list>
int main() {
    std::list l;
}

List 的优势
- List 的优势在于其弹性 (scalability)，可随意插入和删除元素，所需之操作仅是改变下一节点中的前项 (Previous) 和后项 (Next) 的链接
- 对于插入、删除和替换等需要重排序列的操作，效率极高
- 对于移动元素到另一个 list、把一个排好序的 list 合并到另一个 list 之操作，实际上之改变 list 节点间的链接，没有发生元素复制
List 的劣势
- 只能以连续的方式存取 List 中的元素 - 查找任意元素的平均时间和 List 的长度成线型比例
- 对于查找、随机存取等元素定位操作，效率低
- 在每个元素节点上增加一些较为严重的开销：即每个节点的前向和后向指针

创建List

常用方式	代码
创建一个 T 型别的空 list	`std::list<T> l;`
创建一个容量是 n 的 T 型别的 list	`std::list<T> l(n);`
创建一个容量是 n 的 T 型别的 list，并且都初始化为 x	`std::list<T> l(n, x);`
创建一个已有 list 的拷贝	`std::list<T> copyOfList(l);`
通过一个数组创建一个 list	`std::wstring array[] = {<br> TEXT("Str-1"), TEXT("Str-2"), TEXT("Str-3")<br>};<br>std::list<std::wstring> l(array, array + 3);`

向list添加元素

向 list 添加元素的方法为调用其push_back、push_front函数，表示将元素添加至其尾部或头部：

std::list<std::wstring> l;
l.push_back(TEXT("Some text pushed at back"));
l.push_front(TEXT("Some text pushed at front"));

判断是否为空

std::list<std::wstring> l;
bool isEmpty = l.empty();

获取容量

std::wstring array[] = {TEXT("Str-1"), TEXT("Str-2"), TEXT("Str-3")};
std::list<std::wstring> l(array, array + 3);
std::size_t listSize = l.size();

删除list中的元素

clear：清除整个 list，内部是调用erase(begin(), end())

pop_back：弹出 list 尾部元素

std::wstring array[] = { TEXT("Str-1"), TEXT("Str-2"), TEXT("Str-3") };
std::list<std::wstring> l(array, array + 3);
l.pop_back(); // "Str-3" is removed

pop_front：弹出 list 头部元素

std::wstring array[] = { TEXT("Str-1"), TEXT("Str-2"), TEXT("Str-3") };
std::list<std::wstring> l(array, array + 3);
l.pop_front(); // "Str-1" is removed

remove：删除 list 中指定的元素

std::wstring array[] = { TEXT("Str-1"), TEXT("Str-2"), TEXT("Str-3") };
std::list<std::wstring> l(array, array + 3);
l.remove(TEXT("Str-2")); // "Str-2" is removed

remove_if：通过某一条件函数找到 list 中需要删除的元素。例如，假设一个 list 由下列元素构成，我们的目标是要删除 list 中所有含有 “C++” 的字符串的元素：

std::list<std::wstring> l;
l.push_back(TEXT("Standard Template Library"));
l.push_back(TEXT("The C++ Programming Languate"));
l.push_back(TEXT("Windows Internals"));
l.push_back(TEXT("Programming Applications for Windows"));
l.push_back(TEXT("Design Patterns"));
l.push_back(TEXT("Effective C++"));
l.push_back(TEXT("More Effective C++"));

我们还需要定义条件函数对象ContainsString：

struct ContainsString : public std::unary_function<std::wstring, bool> {
    ContainsString(const std::wstring& wszMatch) :
        m_wszMatch(wszMatch) {}

    bool operator()(const std::wstring& wszStringToMatch) const {
        return (wszStringToMatch.find(m_wszMatch) != -1);
    }

    std::wstring m_wszMatch;
};

调用remove_if:

// remove string that contains "C++"
l.remove_if(ContainsString(TEXT("C++")));

C++11写法：

// 使用初始化列表创建list（C++11特性）
std::list<std::wstring> l = {
    L"Standard Template Library",
    L"The C++ Programming Language",
    L"Windows Internals",
    L"Programming Applications for Windows",
    L"Design Patterns",
    L"Effective C++",
    L"More Effective C++"
};

// 使用lambda表达式作为条件（C++11特性）
// 删除所有包含"C++"的字符串
l.remove_if([](const std::wstring& str) {
    return str.find(L"C++") != std::wstring::npos;
});

// 打印结果
for (const auto& item : l) {  // 范围for循环（C++11特性）
    std::wcout << item << std::endl;
}

向list中插入元素

std::list<std::wstring>::const_iterator it = l.begin();
l.insert(it, anotherList.begin(), anotherList.end());

Splice操作

splice 函数用于将一个 list 中的元素转移到另一个 list 中，不会发生元素的复制，只是修改节点间的链接，效率很高。它有三种常用形式：

list1.splice(pos, list2)
将 list2 的所有元素移动到 list1 中 pos 位置前，list2 会变为空
list1.splice(pos, list2, it)
将 list2 中迭代器 it 指向的单个元素移动到 list1 中 pos 位置前
list1.splice(pos, list2, first, last)
将 list2 中 [first, last) 范围内的元素移动到 list1 中 pos 位置前

示例：

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

// 打印list内容的辅助函数
void printList(const std::list<std::wstring>& lst, const std::wstring& name) {
    std::wcout << name << L": ";
    for (const auto& item : lst) {
        std::wcout << item << L" ";
    }
    std::wcout << std::endl;
}

int main() {
    // 创建两个list并初始化
    std::list<std::wstring> list1 = {L"Apple", L"Banana", L"Cherry"};
    std::list<std::wstring> list2 = {L"Dog", L"Cat", L"Bird"};

    printList(list1, L"初始 list1");
    printList(list2, L"初始 list2");

    // 1. 将list2的所有元素移动到list1的开头
    // 1. 将list2的所有元素移动到list1的开头
    list1.splice(list1.begin(), list2);
    printList(list1, L"list2移动到list1开头后 list1");
    printList(list2, L"操作后 list2（已为空）");

    // 重新给list2添加元素
    list2 = {L"Red", L"Green", L"Blue"};
    printList(list2, L"重新初始化后 list2");

    // 2. 将list2的第一个元素移动到list1的末尾
    auto it = list2.begin();  // 指向"Red"
    list1.splice(list1.end(), list2, it);
    printList(list1, L"移动list2首个元素到list1末尾后 list1");
    printList(list2, L"操作后 list2");

    // 3. 将list2的剩余元素移动到list1中"Banana"的前面
    // 先找到"Banana"在list1中的位置
    auto bananaIt = list1.begin();
    while (bananaIt != list1.end() && *bananaIt != L"Banana") {
        ++bananaIt;
    }
    // 移动list2中从begin到end的所有元素
    list1.splice(bananaIt, list2, list2.begin(), list2.end());
    printList(list1, L"移动list2剩余元素到Banana前  list1");
    printList(list2, L"操作后 list2（再次为空）");

    return 0;
}

输出信息：

初始 list1: Apple Banana Cherry 
初始 list2: Dog Cat Bird 
list2移动到list1开头后 list1: Dog Cat Bird Apple Banana Cherry 
操作后 list2（已为空）: 
重新初始化后 list2: Red Green Blue 
移动list2首个元素到list1末尾后 list1: Dog Cat Bird Apple Banana Cherry Red 
操作后 list2: Green Blue 
移动list2剩余元素到Banana前  list1: Dog Cat Bird Apple Green Blue Banana Cherry Red 
操作后 list2（再次为空）: