【C++】List容器（1）-STL标准库-List举例说明-定义和初始化-成员函数的使用-运行效率对比-链接数据结构-和顺序表的对比

C++学习：list容器详解（一）

1.STL标准库

    C++ Standard Template Library（STL）是C++编程语言的一个库，它提供了一系列模板化的数据结构（比如向量、列表、队列等）和算法（比如排序、搜索、变换等），用于快速开发高效的程序。STL是C++程序设计中非常核心的部分，它不仅提高了编程的效率，也保证了程序的性能和可维护性。
    STL算法是标准算法，我们可以把它们应用在那些容器中的对象上。这些算法都有很著名的执行特性。它们可以给对象排序，删除它们，给它们记数，比较，找出特殊的对象，把它们合并到另一个容器中，以及执行其他有用的操作。 
    STL iterator就象是容器中指向对象的指针。STL的算法使用iterator在容器上进行操作。Iterator设置算法的边界 ，容器的长度，和其他一些事情。举个例子，有些iterator仅让算法读元素，有一些让算法写元素，有一些则两者都行。 Iterator也决定在容器中处理的方向。
    通过调用容器的成员函数begin()来得到一个指向一个容器起始位置的iterator。你可以调用一个容器的 end() 函数来得到过去的最后一个值（就是处理停在那的那个值）。 
    STL所有的东西，容器、算法、和允许算法工作在容器中的元素上的iterator。 算法以合适、标准的方法操作对象，并可通过iterator得到容器精确的长度。一旦做了这些，它们就在也不会“跑出边界”。 还有一些其他的对这些核心组件类型有功能性增强的组件，例如函数对象。我们将会看到有关这些的例子，现在 ，我们先来看一看STL的list。
1
2
3
4
5

2. list

std::list 是 C++ 标准库中的一个双向链表容器，它允许在序列的任何位置进行高效的插入和删除操作。以下是对 std::list 的定义、初始化以及常用成员函数的详细解释，并包括一个对比同类型算法运行效率的示例。

2.1 定义与初始化

定义 std::list 非常简单，只需要指定列表中元素的类型即可：

cpp代码

#include <list>  
  
std::list<int> myList; // 定义一个存储 int 类型元素的 list
1
2
3

初始化 std::list 可以通过插入元素的方式来实现：

cpp代码

#include <list>  
#include <iostream>  
  
int main() {  
    std::list<int> myList; // 空 list  
      
    // 插入元素  
    myList.push_back(1);  
    myList.push_front(0);  
    myList.insert(myList.begin(), 2); // 在开始位置插入元素  
    myList.insert(myList.end(), 3);   // 在末尾位置插入元素  
      
    // 输出 list 的内容  
    for (const auto& elem : myList) {  
        std::cout << elem << ' ';  
    }  
    std::cout << '\n';  
      
    return 0;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

输出：2 0 1 3

2.2 成员函数使用

std::list 提供了许多成员函数来操作链表。以下是一些常用的成员函数：

push_back(const value_type& val): 在链表尾部插入一个元素。
push_front(const value_type& val): 在链表头部插入一个元素。
pop_back(): 删除链表尾部的元素。
pop_front(): 删除链表头部的元素。
insert(iterator pos, const value_type& val): 在指定位置插入一个元素。
erase(iterator pos): 删除指定位置的元素。
remove(const value_type& val): 删除所有等于给定值的元素。
sort(): 对链表进行排序。
unique(): 删除所有连续重复的元素，只保留一个。
begin(), end(): 返回指向链表第一个元素和尾后位置的迭代器。
cbegin(), cend(): 返回指向链表第一个元素和尾后位置的常量迭代器。
size(): 返回链表中元素的数量。
empty(): 检查链表是否为空。

代码示例：

#include <iostream>  
#include <list>  
  
int main() {  
    // 创建一个空的 std::list  
    std::list<int> myList;  
  
    // 使用 push_back 在链表尾部插入元素  
    myList.push_back(1);  
    myList.push_back(2);  
    myList.push_back(3);  
  
    // 打印链表元素  
    std::cout << "List after push_back: ";  
    for (int value : myList) {  
        std::cout << value << " ";  
    }  
    std::cout << std::endl;  
  
    // 使用 push_front 在链表头部插入元素  
    myList.push_front(0);  
  
    // 打印链表元素  
    std::cout << "List after push_front: ";  
    for (int value : myList) {  
        std::cout << value << " ";  
    }  
    std::cout << std::endl;  
  
    // 使用 pop_back 删除链表尾部的元素  
    myList.pop_back();  
  
    // 打印链表元素  
    std::cout << "List after pop_back: ";  
    for (int value : myList) {  
        std::cout << value << " ";  
    }  
    std::cout << std::endl;  
  
    // 使用 pop_front 删除链表头部的元素  
    myList.pop_front();  
  
    // 打印链表元素  
    std::cout << "List after pop_front: ";  
    for (int value : myList) {  
        std::cout << value << " ";  
    }  
    std::cout << std::endl;  
  
    // 使用 insert 在指定位置插入元素  
    auto it = myList.begin();  
    ++it; // 指向第二个元素  
    myList.insert(it, 4);  
  
    // 打印链表元素  
    std::cout << "List after insert: ";  
    for (int value : myList) {  
        std::cout << value << " ";  
    }  
    std::cout << std::endl;  
  
    // 使用 erase 删除指定位置的元素  
    it = myList.begin();  
    ++it; // 指向要删除的元素  
    myList.erase(it);  
  
    // 打印链表元素  
    std::cout << "List after erase: ";  
    for (int value : myList) {  
        std::cout << value << " ";  
    }  
    std::cout << std::endl;  
  
    // 使用 remove 删除所有等于给定值的元素  
    myList.push_back(2);  
    myList.push_back(2);  
    myList.remove(2);  
  
    // 打印链表元素  
    std::cout << "List after remove: ";  
    for (int value : myList) {  
        std::cout << value << " ";  
    }  
    std::cout << std::endl;  
  
    // 使用 sort 对链表进行排序  
    myList.push_back(4);  
    myList.push_back(1);  
    myList.sort();  
  
    // 打印链表元素  
    std::cout << "List after sort: ";  
    for (int value : myList) {  
        std::cout << value << " ";  
    }  
    std::cout << std::endl;  
  
    // 使用 unique 删除所有连续重复的元素  
    myList.push_back(3);  
    myList.push_back(3);  
    myList.unique();  
  
    // 打印链表元素  
    std::cout << "List after unique: ";  
    for (int value : myList) {  
        std::cout << value << " ";  
    }  
    std::cout << std::endl;  
  
    // 使用 begin 和 end 获取迭代器，然后遍历链表  
    std::cout << "List using begin and end: ";  
    for (auto it = myList.begin(); it != myList.end(); ++it) {  
        std::cout << *it << " ";  
    }  
    std::cout << std::endl;  
  
    // 使用 size 获取链表大小  
    std::cout << "Size of the list: " << myList.size() << std::endl;  
  
    // 使用 empty 检查链表是否为空  
    std::cout << "Is the list empty? " << (myList.empty() ? "Yes" : "No") << std::endl;  
  
    return 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

【输出结果】：

List after push_back: 1 2 3
List after push_front: 0 1 2 3
List after pop_back: 0 1 2
List after pop_front: 1 2
List after insert: 1 4 2
List after erase: 1 2
List after remove: 1
List after sort: 1 4
List after unique: 1 4
List using begin and end: 1 4
Size of the list: 2
Is the list empty? No
在这个示例中，我们首先创建了一个空的 std::list，然后依次展示了如何使用不同的成员函数来操作链表。每个操作后，我们都通过遍历链表来打印其内容，以验证操作的结果。最后，我们使用 size() 函数获取链表的元素数量，使用 empty() 函数检查链表是否为空，并将结果打印出来。

请注意，std::list 是一个双向链表，其迭代器是双向的，这意味着它们可以向前和向后移动。此外，std::list 的插入和删除操作在链表中的任何位置都是常数时间复杂度，因为链表节点不需要像数组那样移动来保持连续的内存空间。这使得 std::list 在某些情况下比 std::vector 或 std::array 更为灵活和高效。

2.3 运行效率对比

std::list 在随机访问方面不如 std::vector 或 std::array，但在插入和删除操作方面效率更高。这是因为链表中的元素通过指针或迭代器链接在一起，插入和删除操作只需要更新几个指针，而不需要像数组那样移动大量元素。

下面是一个简单的示例，比较 std::list 和 std::vector 在插入元素时的效率：

cpp 代码

```cpp
#include <iostream>  
#include <chrono>  
#include <list>  
#include <vector>  
  
int main() {  
    const int N = 100000;  
  
    // 测试 std::list 的插入效率  
    {  
        std::list<int> list;  
        auto start = std::chrono::high_resolution_clock::now();  
        for (int i = 0; i < N; ++i) {  
            list.push_back(i);  
        }  
        auto end = std::chrono::high_resolution_clock::now();  
        std::cout << "Time for std::list insertion: "   
                  << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()   
                  << " ms\n";  
    }  
    // 测试 std::vector 的插入效率  
    {  
        std::vector<int> vec;  
        vec.reserve(N); // 预分配空间以提高效率  
        auto start = std::chrono::high_resolution_clock::now();  
        for (int i = 0; i < N; ++i) {  
            vec.push_back(i);  
        }  
        auto end = std::chrono::high_resolution_clock::now();  
        std::cout << "Time for std::vector insertion: "   
                  << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()   
                  << " ms\n";  
    }  
  
    return 0;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

在上面的代码中，我们分别测试了向 std::list 和 std::vector中插入N个元素所需的时间。对于std::vector，我们使用了 reserve 函数预先分配了足够的空间，以避免在插入过程中进行多次内存分配和元素移动。

通常，对于少量的插入操作或者随机访问需求较高的场景，std::vector 会更加高效。但是，在需要频繁地在序列中间插入或删除元素的场景中，std::list 通常会提供更好的性能，因为它不需要移动其他元素来腾出空间。

在上面的示例中，由于 std::vector 预先分配了空间，其插入操作的性能与 std::list 相差不大，甚至可能更快一些（特别是在现代编译器和处理器上，std::vector 的优化可能更加出色）。然而，如果 std::vector 没有预先分配空间，或者需要进行大量的中间插入操作，那么 std::list 的性能优势就会更加明显。

需要注意的是，性能比较结果会受到多种因素的影响，包括数据规模、编译器优化、硬件性能等。因此，在实际应用中，应该根据具体的需求和场景来选择合适的数据结构。

总结起来，std::list 是一个双向链表，适合在序列中间进行频繁的插入和删除操作。它提供了丰富的成员函数来操作链表，但在随机访问方面不如 std::vector。在选择数据结构时，应该根据具体需求来权衡不同数据结构的优缺点。

2.4 链表数据结构

具有其独特的优点和缺点。以下是链表的主要优缺点分析：

优点：

动态大小：链表可以在运行时动态地增加或减少元素，而不需要预先分配固定大小的空间。这使得链表在处理不确定大小的数据集时非常灵活。

高效插入和删除：在链表中，插入和删除操作可以在常数时间内完成，特别是在链表的头部或已知位置的节点处。相比之下，数组或向量在插入或删除元素时可能需要移动大量元素，导致时间复杂度较高。

无需连续内存空间：链表中的元素是通过指针或引用链接在一起的，不需要像数组那样占用连续的内存空间。这使得链表在内存分配上更加灵活，可以充分利用碎片化的内存空间。
1
2
3
4
5

缺点：

```bash
访问元素慢：链表中访问特定位置的元素通常比数组慢，因为需要从链表头部开始遍历，直到找到目标元素。这种顺序访问的特性使得链表在需要频繁访问元素的场景中表现不佳。

额外的空间开销：链表中的每个节点都需要额外的空间来存储指向下一个节点的指针或引用。这增加了链表的内存开销，尤其是在存储小型数据时，指针或引用的开销可能会占比较大。

缓存不友好：由于链表中的元素在内存中可能不连续，这可能导致缓存未命中的概率增加，从而降低访问性能。相比之下，数组或向量等连续内存结构更能充分利用缓存优势。

操作复杂：链表的操作相对于数组来说通常更为复杂，需要处理指针或引用的操作，这增加了编程的难度和出错的可能性。
1
2
3
4
5
6
7
8
9

综上所述，链表在需要动态调整大小、频繁插入和删除元素的场景中表现出色，但在需要快速访问元素的场景中则可能不是最佳选择。在实际应用中，应根据具体需求和数据特点来选择合适的数据结构。

2.5 链表和顺序表相比优缺点

链表和顺序表相比，各自具有不同的优缺点。下面我将通过代码示例来演示这些优缺点。

链表
优点：
动态性：链表可以在运行时动态地添加或删除元素。
插入和删除效率高：在链表的头部或尾部插入或删除元素时效率很高。

缺点：
访问元素慢：需要从头节点开始遍历才能找到指定位置的元素。
额外的空间开销：每个节点除了存储数据外，还需要存储指向下一个节点的指针。
1
2
3
4
5
6
7
8

代码示例：

#include <iostream>  
  
struct ListNode {  
    int val;  
    ListNode *next;  
    ListNode(int x) : val(x), next(nullptr) {}  
};  
  
int main() {  
    // 创建链表：1 -> 2 -> 3  
    ListNode *head = new ListNode(1);  
    head->next = new ListNode(2);  
    head->next->next = new ListNode(3);  
      
    // 访问链表的第三个元素（值为3）  
    ListNode *current = head;  
    for (int i = 0; i < 2; ++i) { // 需要遍历两次才能到达第三个元素  
        current = current->next;  
    }  
    std::cout << "Third element: " << current->val << std::endl;  
      
    // 在链表头部插入元素0  
    ListNode *newHead = new ListNode(0);  
    newHead->next = head;  
    head = newHead;  
      
    // 删除链表的第二个元素（值为2）  
    ListNode *prev = head;  
    current = head->next;  
    prev->next = current->next;  
    delete current;  
      
    // 遍历并打印链表元素  
    current = head;  
    while (current != nullptr) {  
        std::cout << current->val << " ";  
        current = current->next;  
    }  
    std::cout << std::endl;  
      
    // 释放链表内存（略）  
      
    return 0;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

顺序表（数组）

优点：
访问元素快：可以通过下标直接访问任意位置的元素。
空间利用率高：数据在内存中连续存储，没有额外的指针开销。

缺点：
插入和删除操作效率低：在数组中间插入或删除元素时，需要移动大量元素。
大小固定：数组在创建时需要预先分配固定大小的内存空间。
1
2
3
4
5
6
7

代码示例：

#include <iostream>  
#include <vector>  
  
int main() {  
    // 创建顺序表（数组）并初始化：1, 2, 3  
    std::vector<int> arr = {1, 2, 3};  
      
    // 访问顺序表的第三个元素（值为3）  
    std::cout << "Third element: " << arr[2] << std::endl;  
      
    // 在顺序表头部插入元素0（需要移动所有元素）  
    arr.insert(arr.begin(), 0);  
      
    // 删除顺序表的第二个元素（值为2）  
    arr.erase(arr.begin() + 1);  
      
    // 遍历并打印顺序表元素  
    for (int i = 0; i < arr.size(); ++i) {  
        std::cout << arr[i] << " ";  
    }  
    std::cout << std::endl;  
      
    return 0;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

通过上面的代码示例，我们可以看到链表和顺序表在访问元素、插入和删除操作方面的不同。链表在动态性和插入/删除操作方面表现出色，而顺序表则在访问元素和空间利用率方面更胜一筹。在实际应用中，我们需要根据具体需求和数据特点来选择合适的数据结构。