首页 > 编程笔记

C++ list容器详解

在 C++ 中，虽然 vector 容器解决了数组存在的一些问题，但本质来讲 vector 还是一种数组，其元素在内存上是连续排列的，插入和删除元素的效率比较低。为了弥补 vector 的不足，C++ 引入了 list 容器。

list 是一个双向链表容器，定义在<list>头文件中。list 容器中的元素不是连续排放的，元素与元素之间是靠指针维系，即每一个元素都配备两个指针，分别指向它的下一个元素和前一个元素。

list 容器最大的优点是插入、删除元素的效率高。因为链表的节点间不是紧邻排列的，而是通过指针关联起来的，这样在插入、删除元素时只要重新设定指针的指向即可，而不需要移动元素。

list 容器的缺点是查找元素比较慢，因为元素间不是紧邻排列的，所以不能使用下标访问某个节点，即不能随机访问元素。

list容器的构造

list 容器本质是一个模板类，它提供了多种构造函数，以便适应不同的应用场景，包括：

// 创建一个空的list容器
explicit list (const allocator_type& alloc = allocator_type());

// 创建一个有 n 个元素的 list 容器，这些元素进行默认初始化
explicit list (size_type n);

// 创建一个有 n 个元素的 list 容器，并将这些元素初始化为 val
list (size_type n, const value_type& val, const allocator_type& alloc = allocator_type());

// 从两个迭代器 first 和 last 指定的范围中复制元素到新的 list 容器中
template <class InputIterator> 
list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());

// 拷贝构造函数，创建一个与 x 相同的新 list 容器
list (const list& x);
list (const list& x, const allocator_type& alloc);

// 移动构造函数，创建一个新的 list 容器，并从 x 中“移动”数据
list (list&& x);
list (list&& x, const allocator_type& alloc);

// 从一个初始化列表 il 中复制元素到新的 list 容器中
list (initializer_list<value_type> il, const allocator_type& alloc = allocator_type());

下面是一个完整的 C++ 示例，演示了用各种构造函数来创建 list 容器。

#include <iostream>
#include <list>

int main() {
    // 使用默认构造函数创建一个空的 list
    std::list<int> list1;
    std::cout << "list1: ";
    for (const auto& elem : list1) {
        std::cout << elem << ' ';
    }
    std::cout << '\n';

    // 创建一个含有 5 个元素的 list，每个元素进行默认初始化（对于 int 类型，这通常意味着初始化为 0）
    std::list<int> list2(5);
    std::cout << "list2: ";
    for (const auto& elem : list2) {
        std::cout << elem << ' ';
    }
    std::cout << '\n';

    // 创建一个含有 3 个元素的 list，每个元素都初始化为 7
    std::list<int> list3(3, 7);
    std::cout << "list3: ";
    for (const auto& elem : list3) {
        std::cout << elem << ' ';
    }
    std::cout << '\n';

    // 使用范围构造函数，从另一个 list（list3）复制元素
    std::list<int> list4(list3.begin(), list3.end());
    std::cout << "list4: ";
    for (const auto& elem : list4) {
        std::cout << elem << ' ';
    }
    std::cout << '\n';

    // 使用拷贝构造函数，从另一个 list（list4）复制元素
    std::list<int> list5(list4);
    std::cout << "list5: ";
    for (const auto& elem : list5) {
        std::cout << elem << ' ';
    }
    std::cout << '\n';

    // 使用移动构造函数，从另一个 list（list5）移动元素
    std::list<int> list6(std::move(list5));
    std::cout << "list6: ";
    for (const auto& elem : list6) {
        std::cout << elem << ' ';
    }
    std::cout << '\n';

    // 使用 initializer_list 初始化
    std::list<int> list7 = {1, 2, 3, 4, 5};
    std::cout << "list7: ";
    for (const auto& elem : list7) {
        std::cout << elem << ' ';
    }
    std::cout << '\n';

    return 0;
}

运行结果为：

list1:
list2: 0 0 0 0 0
list3: 7 7 7
list4: 7 7 7
list5: 7 7 7
list6: 7 7 7
list7: 1 2 3 4 5

list容器的使用

list 容器常做的操作就是插入和删除元素，可以借助 list 模板类中提供的成员函数实现。

下表罗列出了 list 模板类提供的所有成员函数以及各自的功能。

表 1 list 成员函数即功能
成员函数	功能
begin()	返回指向容器中第一个元素的双向迭代器。
end()	返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。
rbegin()	返回指向最后一个元素的反向双向迭代器。
rend()	返回指向第一个元素所在位置前一个位置的反向双向迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
empty()	判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
size()	返回当前容器实际包含的元素个数。
max_size()	返回容器所能包含元素个数的最大值。这通常是一个很大的值，一般是 2³²-1，所以我们很少会用到这个函数。
front()	返回第一个元素的引用。
back()	返回最后一个元素的引用。
assign()	用新元素替换容器中原有内容。
emplace_front()	在容器头部生成一个元素。该函数和 push_front() 的功能相同，但效率更高。
push_front()	在容器头部插入一个元素。
pop_front()	删除容器头部的一个元素。
emplace_back()	在容器尾部直接生成一个元素。该函数和 push_back() 的功能相同，但效率更高。
push_back()	在容器尾部插入一个元素。
pop_back()	删除容器尾部的一个元素。
emplace()	在容器中的指定位置插入元素。该函数和 insert() 功能相同，但效率更高。
insert()	在容器中的指定位置插入元素。
erase()	删除容器中一个或某区域内的元素。
swap()	交换两个容器中的元素，必须保证这两个容器中存储的元素类型是相同的。
resize()	调整容器的大小。
clear()	删除容器存储的所有元素。
splice()	将一个 list 容器中的元素插入到另一个容器的指定位置。
remove(val)	删除容器中所有等于 val 的元素。
remove_if()	删除容器中满足条件的元素。
unique()	删除容器中相邻的重复元素，只保留一个。
merge()	合并两个事先已排好序的 list 容器，并且合并之后的 list 容器依然是有序的。
sort()	通过更改容器中元素的位置，将它们进行排序。
reverse()	反转容器中元素的顺序。

有关表示各个成员函数的语法格式，读者不需要死记硬背，需要时直接去查 C++ 标准库即可，这里不再过多赘述。

下面的 C++ 代码演示了表中部分成员函数的用法：

#include <iostream>
#include <list>

int main() {
    // 构造一个 list 容器
    std::list<int> myList = {1, 2, 3, 4, 5};

    // 在列表的开头和末尾添加元素
    myList.push_front(0);
    myList.push_back(6);

    // 显示列表元素
    std::cout << "List elements: ";
    for(auto it = myList.begin(); it != myList.end(); ++it) {
        std::cout << *it << ' ';
    }
    std::cout << std::endl;

    // 删除第一个和最后一个元素
    myList.pop_front();
    myList.pop_back();

    // 再次显示列表元素
    std::cout << "List elements after pop: ";
    for(const auto& elem : myList) {
        std::cout << elem << ' ';
    }
    std::cout << std::endl;

    return 0;
}

运行结果为：

List elements: 0 1 2 3 4 5 6
List elements after pop: 1 2 3 4 5

C++ list容器详解

list容器的构造

list容器的使用

推荐阅读