「C/C++」C++ STL容器库 之 std::list 双向链表容器

std::list容器详解

上图截取自C++黑马课程

1. 容器说明

std::list是C++标准模板库（STL）中的一种双向链表容器，属于顺序容器的一种。与std::vector和std::deque等容器不同，std::list在插入和删除操作上具有显著优势，特别是在容器的中间部分。std::list的每个元素包含指向前一个元素和后一个元素的指针，这使得在链表的任意位置进行插入和删除操作的时间复杂度为O(1)。然而，std::list不支持随机访问，访问某个位置的元素需要O(n)时间。

2. 引用头文件

在使用std::list之前，必须包含对应的头文件：

#include <list>

3. 函数构造与对象初始化

std::list提供了多种构造函数来初始化对象，包括默认构造函数、拷贝构造函数、赋值构造函数、初始化列表构造函数、迭代器范围构造函数、大小和值构造函数以及移动构造函数等。

• 默认构造函数：创建一个空的list容器。
• 拷贝构造函数：用另一个list容器来初始化一个新的list容器。
• 赋值构造函数：通过赋值运算符从一个list容器创建另一个list容器。
• 初始化列表构造函数：使用初始化列表来初始化list容器。
• 迭代器范围构造函数：使用两个迭代器（指向容器或其他序列的起始和结束位置）来初始化list容器。
• 大小和值构造函数：使用指定的大小和值来初始化list容器。
• 移动构造函数（C++11开始支持）：从另一个list容器移动元素来初始化新的list容器。

示例代码：

#include <list>
#include <iostream>

int main() {
    // 默认构造函数
    std::list<int> lst1;

    // 初始化列表构造函数
    std::list<int> lst2 = {1, 2, 3, 4, 5};

    // 大小和值构造函数
    std::list<int> lst3(5, 10);

    // 拷贝构造函数
    std::list<int> lst4(lst2);

    // 输出list元素
    for (int elem : lst4) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

4. 元素访问

std::list不支持通过下标随机访问元素，只能通过迭代器进行访问。访问某个位置的元素需要从头或尾开始遍历链表。

#include <list>
#include <iostream>

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

    std::cout << lst.front() << std::endl; // 输出：1
	std::cout << lst.back() << std::endl;  // 输出：5
    return 0;
}

5. 迭代器

std::list的迭代器可以双向移动，支持向前和向后遍历链表。迭代器的稳定性使得在插入和删除操作时，除了被删除的迭代器外，其余迭代器仍然有效。

#include <list>
#include <iostream>

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

    // 使用迭代器访问元素
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

6. 容器修改器

std::list提供了多种成员函数来修改容器，包括添加元素（push_back、push_front）、删除元素（pop_back、pop_front）、插入元素（insert）、删除指定位置的元素（erase）、合并和拼接（merge、splice）、移除元素（remove、remove_if）、排序（sort）等。

示例代码：

#include <list>
#include <iostream>

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

    // 在末尾添加元素
    lst.push_back(6);

    // 在前面添加元素
    lst.push_front(0);

    // 删除末尾元素
    lst.pop_back();

    // 删除前面元素
    lst.pop_front();

    // 插入元素
    auto it = lst.begin();
    ++it; // 移动到第二个位置
    lst.insert(it, 10); // 在第二个位置插入10

    // 删除指定位置的元素
    it = lst.begin();
    ++it; // 移动到第二个位置
    lst.erase(it); // 删除第二个位置的元素

    // 输出修改后的list元素
    for (const auto& elem : lst) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

7. 元素比较

std::list的元素比较通常通过迭代器来实现，可以使用标准库中的算法函数（如std::equal）来比较两个list容器是否相等或具有相同的元素顺序。

8.反转\排序\交换

#include <list>
#include <iostream>
using namespace std;

void printList(const list<int>& L) {

	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main()
{
	list<int> l = {90,20,30,40,50};
	
	//反转容器的元素
	l.reverse();
	printList(l); // 50 40 30 20 90 

	//排序
	l.sort(); //默认的排序规则 从小到大
	printList(l); // 20 30 40 50 90 

	list<int> l2 = {10,30,50,70,90};
	l.swap(l2);
	printList(l); // 10 30 50 70 90 
}

总结与场景应用

std::list容器具有动态大小、高效插入删除、内存分配灵活和双向遍历等优点，但访问元素速度较慢且内存开销较大。因此，std::list适用于需要在两端频繁插入和删除元素的场景，如排序算法中维护活跃连接列表、实现某种内存池或对象池等。同时，std::list也适用于处理大小动态变化的集合和需要双向遍历的场景。

通过合理的使用std::list容器，可以显著提高程序的灵活性和效率，特别是在需要频繁修改容器内容的场景中。