Vector

vector的底层实现⭐

C++ 标准库中的 std::vector 是一个动态数组，底层通过连续内存块实现，支持快速随机访问和动态扩容。其核心实现细节如下：

1. 底层数据结构

vector 内部维护三个指针（或等效的成员变量）来管理内存：

  • _start：指向数组的第一个元素（begin()）。
  • _finish：指向最后一个元素的下一个位置（end()）。
  • _end_of_storage：指向内存块的末尾（表示当前分配的容量上限）。
1
2
3
4
5
6
7
8
template <class T>
class vector {
private:
    T* _start;          // 指向第一个元素
    T* _finish;         // 指向最后一个元素的下一个位置
    T* _end_of_storage; // 指向内存块的末尾
    // ...
};

2. 内存分配与扩容

初始化

  • 默认构造时，vector 为空，三个指针均为 nullptr。
  • 添加元素时，若当前容量不足，触发动态扩容。

扩容机制

  • 当 size() == capacity()（即 _finish == _end_of_storage）时，扩容：
    1. 分配新内存块，容量通常是原容量的 2倍 或 1.5倍（标准未规定，但通用实现如此）。
    2. 将旧元素移动或拷贝到新内存（C++11 后优先用移动语义）。
    3. 释放旧内存，更新指针。

扩容复杂度

  • 均摊时间复杂度为 O(1)（例如，每次扩容为 2 倍时，均摊分析后插入单个元素的开销为常数）。

3. 关键操作实现

push_back

1
2
3
4
5
6
7
8
9
void push_back(const T& value) {
    if (_finish == _end_of_storage) {
        // 触发扩容（例如容量从 4 扩容到 8）
        reallocate(capacity() * 2); 
    }
    // 在 _finish 位置构造新元素
    construct(_finish, value);
    _finish++;
}

随机访问

1
2
3
T& operator[](size_t index) {
    return _start[index]; // 直接通过指针偏移访问
}

size() 和 capacity()

1
2
3
4
5
6
7
size_t size() const {
    return _finish - _start; // 元素数量
}

size_t capacity() const {
    return _end_of_storage - _start; // 总容量
}

4. 迭代器失效问题

  • 扩容操作会导致所有迭代器、指针、引用失效（内存地址改变）。
  • 插入/删除元素可能导致后续元素位置变动，具体是否失效取决于操作位置和容器状态。

总结

  • 动态数组：连续内存，支持 O(1) 随机访问。
  • 自动扩容：容量按几何级数增长，均摊 O(1) 时间复杂度。
  • 内存管理：通过指针跟踪元素范围，reserve() 可优化性能。
  • 迭代器安全：扩容会导致迭代器失效，需谨慎操作。

STL中使用vector要注意什么⭐

在使用C++ STL中的 vector时，需要注意以下关键点：

1. 扩容机制

  • 预分配内存（reserve()）：当预先知道元素数量时，使用 reserve(n) 提前分配足够内存，避免多次扩容（如 push_back 导致反复重新分配）。
  • 大小（size）等于容量（capacity）时进行扩容：扩容策略通常是倍增（如2倍），频繁扩容可能导致性能损失。

2. 元素访问与边界安全

  • 安全访问（at() vs operator[]）：
    • at(index)：进行边界检查，越界时抛出 std::out_of_range 异常。
    • operator[]：不检查边界，越界访问导致未定义行为。

3. 迭代器失效问题

  • 操作导致迭代器失效的场景：
    • 插入元素：若引发扩容（size > capacity），所有迭代器、指针、引用失效。
    • 删除元素：被删元素之后的迭代器失效。
    • reserve()/resize()：可能引发重新分配，导致所有迭代器失效。

4. 高效插入与构造

  • 使用 emplace_back 替代 push_back：emplace_back 直接在容器内构造元素，避免临时对象的拷贝/移动（C++11起支持）。

5. 对象生命周期与资源管理

  • 存储原始指针：需手动释放内存，避免内存泄漏。

  • 推荐使用智能指针：
    使用 std::unique_ptr 或 std::shared_ptr 自动管理资源。

    1
    2
    std::vector<std::unique_ptr<int>> vec;
    vec.push_back(std::make_unique<int>(42)); // 自动释放

6. 类型要求与移动语义

  • 元素类型的要求：

    • 可拷贝构造（若使用 push_back 拷贝）。
    • 可移动构造（若使用移动语义或 emplace_back）。

  • 利用移动语义：
    对于大型对象（如 std::string），使用 std::move 避免拷贝。

    1
    2
    3
    std::vector<std::string> vec;
    std::string str = "Hello";
    vec.push_back(std::move(str)); // 移动而非拷贝

vector的扩容机制⭐

vector 的扩容机制是其动态数组特性的核心实现，目的是在元素数量超过当前容量时自动扩展内存空间。

  1. 扩容触发条件
    当向 vector 中添加元素（如 push_back、emplace_back 或 insert）时，若当前元素数量（size()）已达到容量（capacity()），则会触发扩容：
  2. 扩容步骤
    • 分配新内存：分配一块更大的连续内存（通常是当前容量的 1.5 或 2 倍，取决于编译器实现）。
    • 迁移元素：将旧内存中的元素拷贝或移动到新内存。C++11 后，若元素类型支持移动语义（如 std::string、std::unique_ptr），优先使用移动而非拷贝。
    • 释放旧内存：销毁旧元素并释放原内存。
  3. 扩容策略
    • 倍数增长：每次扩容将容量乘以固定倍数（如 1.5 或 2），时间复杂度均摊为 O(1)。
    • MSVC：按 1.5 倍扩容。GCC/Clang：通常按 2 倍扩容。
    • 优势：倍数增长在时间（减少扩容次数）和空间（避免过度浪费）之间取得平衡。
  4. 时间复杂度
    单次扩容：O(n)（需要拷贝/移动 n 个元素）。
    均摊分析：多次插入操作的均摊时间复杂度为 O(1)。
    例如：从空 vector 插入 n 个元素，总扩容次数为 O(log n)，总操作次数为 O(n)。
  5. 手动优化扩容
    预分配内存：使用 reserve() 提前分配足够容量，避免多次扩容。

vector和list的底层实现及区别

底层实现

  1. vector的底层实现是动态数组。它使用一块连续的内存空间来存储元素。当需要增加容量时，vector会分配一块更大的内存（通常是当前容量的两倍），然后将原有数据复制到新内存中，并释放旧内存。这种实现方式使得vector支持快速随机访问，即可以通过索引直接访问任意元素。
  2. list的底层实现是双向链表。它由一系列节点组成，每个节点包含数据和指向前后节点的指针。由于节点在内存中不一定是连续的，每次插入或删除操作只需调整相关指针即可。这种实现方式使得list支持快速插入和删除操作，但不支持随机访问。

主要区别

  1. 存储结构：vector是顺序存储，底层是数组；list是链式存储，底层是双向链表。
  2. 内存分配：vector一次性分配较大的内存，不够时进行扩容；list每次插入新节点都会进行内存申请。
  3. 访问性能：vector支持快速随机访问，时间复杂度为O(1)；list不支持随机访问，需要遍历，时间复杂度为O(n)。
  4. 插入删除性能：vector插入和删除数据需要移动现有数据，时间复杂度为O(n)；list插入和删除数据只需调整指针，时间复杂度为O(1)。

使用场景

  1. vector适用于需要频繁随机访问元素的场景，如动态数组、栈等。
  2. list适用于需要频繁插入和删除元素的场景，如队列、链表等。

map和unordered_map的区别⭐⭐

map 和 unordered_map 都是 C++ 标准库中用于存储键值对的容器，它们在功能上有相似之处，但在实现原理、性能特点和使用场景等方面存在明显区别。

1. 实现原理

  • map：map基于红黑树（一种平衡二叉搜索树）实现，所有元素按照键（Key）的严格升序排列。插入元素时会自动维护树的平衡，确保查找效率稳定。
  • unordered_map：unordered_map 基于哈希表实现。哈希表使用哈希函数将键映射到一个哈希桶中，通过哈希函数计算出的哈希值来快速定位元素。当发生哈希冲突（即不同的键映射到同一个哈希桶）时，通常会使用开放定址法和链表法等来解决冲突。

2. 元素顺序

  • map：元素会按照键的大小进行排序，默认是按照键的升序排列。因此，当你遍历 map 时，会按照键的有序顺序依次访问元素。
  • unordered_map：元素是无序的，其存储顺序取决于哈希函数和哈希冲突的处理方式，与键的大小无关。遍历 unordered_map 时，元素的访问顺序是不确定的。

3. 时间复杂度

  • map：由于基于红黑树，查找、插入和删除操作的平均时间复杂度都是 O(logn)O(log n)。
  • unordered_map：在理想情况下，基于哈希表的 unordered_map 查找、插入和删除操作的平均时间复杂度为 O(1)O(1)。然而，在最坏情况下（如哈希冲突严重），时间复杂度可能会退化为 O(n)O(n)。

4. 内存占用

  • map：红黑树的每个节点除了存储键值对之外，还需要额外的指针和红/黑性质来维护树的结构，因此内存占用相对较高。
  • unordered_map：哈希表只需要维护一个哈希桶数组，内存开销通常较小，但需要额外的空间处理哈希冲突。

5. 使用场景

  • map：当你需要元素按照键的顺序进行排序，或者需要频繁进行范围查找（如查找某个区间内的所有元素）时，应该选择 map。例如，在实现一个字典，需要按照字母顺序遍历单词时，map 是一个不错的选择。
  • unordered_map：当你只关心元素的插入、查找和删除操作的速度，而不关心元素的顺序时，unordered_map 是更好的选择。例如，在实现一个缓存系统，需要快速查找某个键对应的值时，unordered_map 可以提供更高效的性能。