深入剖析list

List

1、list概述

相较于vector的连续线性空间，list是一个环状双向链表。

每次插入或删除一个元素，就配置或释放一个元素空间，时间复杂度为常数。

2、list的节点

以下是STL list的节点（node）结构：

template<class T>
struct  __list_node{
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data;
}

显然这是一个双向链表

3、list的迭代器

由于STL list是一个双向链表，迭代器必须具备前移、后移的能力，所以list提供的是Bidirectional Iterator。

在C++中，**双向迭代器（Bidirectional Iterator）**是一种迭代器类型，允许在容器中双向移动，即不仅可以从前向后遍历（如前向迭代器），还可以从后向前遍历。这类迭代器提供了比输入迭代器、输出迭代器和前向迭代器更多的功能，通常用于双向链表（如 std::list）等容器。

list有一个重要性质：插入操作（insert）和接合操作（splice）都不会造成原有的list迭代器失效。这在vector是不成立。因为vector的插入操作可能造成记忆体重新配置，导致原有迭代器全部失效。甚至list的元素删除操作，也只有"指向被删除元素"的那个迭代器失效，其他迭代器不受任何影响。

4、list的数据结构

SGI list是一个环状双向链表，所以只需要一个指针，便可以完整表现整个链表：

template<class T, class Alloc = alloc>
class list{
protected:
    typedef __list_node<T> list_node;
public:
    typedef list_node* link_type;
    
protected:
    link_type node;//只需要一个指针，便可完成整个环状环状双向链表
}

如果让指针node指向尾端的一个空白节点（也可以理解为头部的空白节点，因为这是一个环状双向链表），node便能符合STL对于“前闭后开”区间的原则，成为last迭代器

iterator begin() { return (link_type)(*node).next; }
iterator end() { return node; }
bool empty() { return node->next == node; }

5、list的常用API

构造函数

// 默认构造函数，构造一个空的list
list();

// 构造包含n个val元素的list
explicit list(size_type n, const T& val = T());

// 使用区间[first, last)构造list
template <class InputIterator>
list(InputIterator first, InputIterator last);

// 拷贝构造函数
list(const list& x);

// 移动构造函数
list(list&& x) noexcept;

// 列表初始化构造函数
list(std::initializer_list<T> ilist);

赋值操作符

// 赋值操作符
list& operator=(const list& x);

// 移动赋值操作符
list& operator=(list&& x) noexcept;

// 列表赋值操作符
list& operator=(std::initializer_list<T> ilist);

大小相关函数

// 返回list中的元素个数
size_type size() const noexcept;

// 判断list是否为空
bool empty() const noexcept;

// 返回list可以容纳的最大元素个数
size_type max_size() const noexcept;

访问元素

// 返回第一个元素的引用
T& front();
const T& front() const;

// 返回最后一个元素的引用
T& back();
const T& back() const;

修改list

// 在末尾插入元素
void push_back(const T& val);
void push_back(T&& val);

// 在开头插入元素
void push_front(const T& val);
void push_front(T&& val);

// 移除末尾元素
void pop_back();

// 移除开头元素
void pop_front();

// 清空所有元素
void clear() noexcept;

// 插入元素
iterator insert(const_iterator position, const T& val);
iterator insert(const_iterator position, T&& val);
iterator insert(const_iterator position, size_type n, const T& val);
template <class InputIterator>
iterator insert(const_iterator position, InputIterator first, InputIterator last);
iterator insert(const_iterator position, std::initializer_list<T> ilist);

// 删除指定位置的元素
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);

// 重置大小
void resize(size_type n);
void resize(size_type n, const T& val);

// 交换两个list
void swap(list& x) noexcept;

// 移除等于val的所有元素
void remove(const T& val);

// 移除满足谓词的所有元素
template <class Predicate>
void remove_if(Predicate pred);

迭代器

// 返回指向第一个元素的迭代器
iterator begin() noexcept;
const_iterator begin() const noexcept;
const_iterator cbegin() const noexcept;

// 返回指向末尾元素之后的迭代器
iterator end() noexcept;
const_iterator end() const noexcept;
const_iterator cend() const noexcept;

特殊操作

// 合并另一个已排序的list到当前list
void merge(list& x);
template <class Compare>
void merge(list& x, Compare comp);

// 反转list中元素的顺序
void reverse() noexcept;

// 移除重复的元素
void unique();
template <class BinaryPredicate>
void unique(BinaryPredicate binary_pred);

// 对list中的元素进行排序
void sort();
template <class Compare>
void sort(Compare comp);

6、与vector进行比较

1. 底层实现

• std::list：双向链表，每个元素都存储有前后两个指针，指向前一个和后一个元素。
• std::vector：动态数组，内存是连续的，元素按顺序排列在一块连续的内存空间中。

2. 内存分配

• std::list：由于链表的性质，std::list 中的元素分散存储，每个元素都有指向下一个和上一个节点的指针，内存不连续，存储效率较低。每次插入和删除时，可能需要动态分配或释放内存。
• std::vector：std::vector 使用连续的内存块存储数据，内存效率更高，但如果 vector 扩展空间时需要重新分配内存，可能会导致性能下降。

3. 元素访问

• std::list：由于是链表结构，无法通过下标直接访问元素。访问某个元素必须通过迭代器从头或尾遍历，时间复杂度为 O(n)。
• std::vector：支持随机访问，可以通过下标直接访问任何元素，时间复杂度为 O(1)。

4. 插入和删除操作

• std::list：在中间或两端插入或删除元素的时间复杂度为 O(1)，因为只需要调整指针即可。插入或删除操作非常高效，适合频繁插入删除的场景。
• std::vector：插入和删除操作在两端（末尾）的时间复杂度为 O(1)，在中间的插入删除操作需要移动大量元素，时间复杂度为 O(n)。

5. 迭代器的稳定性

• std::list：list 的迭代器在插入或删除其他元素时仍然有效（除非是删除该迭代器指向的元素）。即，迭代器是稳定的。
• std::vector：vector 的迭代器在重新分配内存（如扩容）时会失效，即迭代器在发生插入或删除操作后可能会变得无效。

6. 适用场景

• std::list：适用于需要频繁在中间插入和删除元素的场景，如实现队列、双端队列等。同时适合大小不定的场景，因为不需要频繁分配和移动内存。
• std::vector：适用于需要随机访问和频繁查询的场景，如实现堆栈、数组等。由于支持快速随机访问，vector 更适合需要频繁读取的情况。

7. 性能比较

• 内存开销：std::list 由于每个元素存储了两个指针（前驱和后继），因此在内存上开销较大。std::vector 的内存开销较小，因为它只存储元素本身，且内存是连续的。
• 插入删除：std::list 插入和删除的性能通常优于 std::vector，特别是在中间位置插入删除时。std::vector 插入和删除的性能会因内存搬移和重新分配而下降。
• 遍历和访问：std::vector 在遍历和随机访问时具有更好的性能，因为内存是连续的，能更好地利用缓存。std::list 的遍历速度较慢，特别是随机访问时性能较差。

8. 扩展性

• std::list：每次插入或删除操作都只需调整相关节点的指针，不需要像 vector 那样重新分配或移动大块内存。因此，list 适合不确定大小的动态操作。
• std::vector：当容量不足时，vector 会一次性分配更多的内存，并将现有元素复制到新内存中，这样可以减少频繁的内存重新分配。因此，vector 的扩展策略是一种渐进式的优化方式。

9. 常见操作的时间复杂度

操作	std::list 时间复杂度	std::vector 时间复杂度
访问元素	O(n)	O(1)
插入/删除（中间）	O(1)	O(n)
插入/删除（末尾）	O(1)	O(1)
插入/删除（开头）	O(1)	O(n)
迭代器遍历	O(n)	O(n)

结论：

• 使用 std::list：当你需要频繁在容器中间插入或删除元素时，std::list 是更好的选择，因为它能够在常数时间内完成这些操作。
• 使用 std::vector：当你需要频繁访问元素，特别是随机访问时，std::vector 是更好的选择，它能够在常数时间内完成随机访问操作，并且在遍历时性能更好。

选择建议：

• 如果你的应用程序中更多是读取操作（比如通过下标访问元素），并且插入和删除操作相对较少，使用 std::vector。
• 如果你的应用程序中需要频繁地在容器中插入和删除元素，尤其是在中间位置操作，使用 std::list。

原文地址：https://blog.csdn.net/2404_87273268/article/details/142554094

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！