C++编程：list与deque特性分析及示例

"这篇文档主要介绍了C++中的两种容器，list和deque，它们都是STL（Standard Template Library，标准模板库）的一部分。郭炜和刘家瑛在北京大学的程序设计实习课程中讲解了这两个数据结构的特点和使用方法。文档特别强调了list和deque在插入、删除操作上的优势以及它们与数组或向量的区别。" 在C++的STL中，`list`和`deque`是两种常用的序列容器，它们各自有着不同的特性和用途。 **list容器** list是一个双向链表实现的容器，其主要优点在于**在任意位置插入和删除元素的时间复杂度为O(1)**，这是因为链表结构不需要移动元素来完成这些操作。然而，由于它不是连续存储的，所以**不支持通过下标进行随机访问**，这意味着你不能像对待数组那样快速访问第N个元素。list提供了丰富的成员函数，包括： 1. `push_front()`：在链表开头添加元素。 2. `pop_front()`：移除链表的第一个元素。 3. `sort()`：对链表进行排序，list特有的sort函数，可以自定义比较函数。 4. `remove()`：删除所有与给定值相等的元素。 5. `unique()`：删除所有与前一个元素相同的元素。 6. `merge()`：合并两个list，并清空被合并的list。 7. `reverse()`：反转链表。 8. `splice()`：在指定位置插入另一个list的一个或多个元素，并从源list中删除它们。 **注意**：list的迭代器是双向迭代器，不支持完全随机访问，因此不能进行大于/小于比较、[]运算符操作或随机移动。 **deque容器** deque（双端队列）是另一种序列容器，它在内部实现上类似于一段可变大小的数组，支持在两端进行O(1)时间复杂度的插入和删除。deque的主要优点是**支持随机访问**，即可以通过下标快速访问任何位置的元素。与list相比，deque更适合那些需要频繁访问中间元素的场景。 例如，以下代码展示了如何定义一个类A，并重载<, ==和<<运算符以支持list的排序功能： ```cpp class A { private: int n; public: A(int n_) : n(n_) {} friend bool operator<(const A& a1, const A& a2); // 用于排序 friend bool operator==(const A& a1, const A& a2); // 用于检查相等性 friend std::ostream& operator<<(std::ostream& o, const A& a); // 用于输出 }; bool operator<(const A& a1, const A& a2) { return a1.n < a2.n; } bool operator==(const A& a1, const A& a2) { return a1.n == a2.n; } std::ostream& operator<<(std::ostream& o, const A& a) { o << a.n; return o; } ``` 在实际编程中，可以根据具体需求选择使用list还是deque。如果你需要高效地在两端插入和删除元素，但不关心中间元素的访问速度，那么list可能是更好的选择。相反，如果需要随机访问元素且插入和删除主要发生在两端，deque可能更合适。