1. std::map 和 std::unordered_map 的区别（含底层实现）

2. std::set 和 std::unordered_set 的区别

核心逻辑与 map/unordered_map 一致，核心差异在于存储结构：

• std::set：底层红黑树，存储唯一键值（键即值），有序、增删查 ​；
• std::unordered_set：底层哈希表，存储唯一键值，无序、平均增删查 ​；
• 补充：二者均不允许重复元素，如需重复可使用 multiset/unordered_multiset。

3. map 和 set 的区别及实现方式

底层实现

二者底层均为红黑树，均遵循二叉搜索树的特性，保证元素有序和操作的 ​ 复杂度。

核心区别

4. vector 和 list 的区别及适用场景

适用场景

• vector：需频繁随机访问、尾部插入删除、数据量固定或扩容少的场景（如算法刷题、存储有序序列）；
• list：需频繁在任意位置插入删除、数据量动态变化大的场景（如链表操作、任务队列）。

5. std::deque 与 vector 的区别及适用场景

6. std::string 的底层实现及优化

• 底层实现：多数标准库采用短字符串优化（SSO），短字符串直接存储在对象内部，长字符串则指向堆上的字符数组；
• 核心特性：支持随机访问、尾部插入高效，resize/reserve 与 vector 类似；
• 优化点：避免频繁扩容（预分配空间）、使用 std::string_view 避免不必要的拷贝。

7. 什么是迭代器失效，如何避免？

定义

迭代器本质是容器元素的“指针/引用”，当容器底层内存结构改变或元素位置移动时，迭代器指向的地址失效，访问会触发未定义行为。

常见失效场景与避免方法

8. STL 迭代器如何删除元素？

核心原则：通过容器的 erase 方法删除，而非迭代器自身，且需用 erase 的返回值更新迭代器，避免失效。

核心代码示例

// vector 删除元素（避免失效）
vector<int> vec = {1, 2, 3, 4};
for (auto it = vec.begin(); it != vec.end();) {
    if (*it == 2) {
        it = vec.erase(it); // 用返回值更新迭代器，指向被删元素的下一个
    } else {
        it++;
    }


// map 删除元素（erase(it++) 写法）
map<int, string> mp = {{1, "a"}, {2, "b"}};
for (auto it = mp.begin(); it != mp.end();) {
    if (it->first == 2) {
        mp.erase(it++); // 先移动迭代器，再删除原位置元素
    } else {
        it++;
    }
}

9. 如何删除 std::vector 中的特定元素？

方法一：遍历+erase（适合少量删除）

vector<int> vec = {1, 2, 2, 3};
for (auto it = vec.begin(); it != vec.end();) {
    if (*it == 2) it = vec.erase(it);
    else it++;
}

方法二：erase-remove 惯用法（适合大量删除，效率更高）

核心：remove 仅将非删除元素移到容器前部，返回新尾迭代器；erase 删除尾部冗余元素。

#include <algorithm>
vector<int> vec = {1, 2, 2, 3};
// 删除所有值为2的元素
vec.erase(remove(vec.begin(), vec.end(), 2), vec.end());

10. resize 和 reserve 的区别（针对 vector）

二者均针对 vector（string 同理），核心差异在于操作目标不同：

vector<int> vec;vec.reserve(10); // capacity=10，size=0vec.resize(5);   // capacity=10，size=5，元素为默认值0

11. STL 迭代器的分类及特点

• 输入迭代器：只读，单次遍历（如 istream_iterator）；
• 输出迭代器：只写，单次遍历（如 ostream_iterator）；
• 前向迭代器：可读写，支持多次遍历（如 forward_list 的迭代器）；
• 双向迭代器：支持前后遍历（如 list/map/set 的迭代器）；
• 随机访问迭代器：支持随机访问、下标操作（如 vector/deque/string 的迭代器）。

12. std::advance 和 std::next 的区别

• std::advance(it, n)：将迭代器 it 前进 n 步，无返回值，会修改原迭代器；
• std::next(it, n)：返回迭代器 it 前进 n 步后的新迭代器，不修改原迭代器；
• 注意：advance 对双向迭代器支持负数步长，对随机访问迭代器效率为 ​，对其他迭代器为 ​。

13. STL 容器的时间复杂度（vector、list、map、unordered_map）

14. vector 的实现原理

vector 是动态连续数组，核心由三个迭代器（指针）实现：

1. start：指向数组起始位置；
2. finish：指向最后一个有效元素的下一个位置；
3. end_of_storage：指向内存缓冲区的末尾。

核心机制

• 扩容机制：当插入元素导致 size() == capacity() 时，触发扩容（通常为原容量的 2 倍或 1.5 倍），步骤为：分配新内存 → 拷贝/移动原元素 → 释放原内存 → 更新指针；
• 内存管理：通过分配器（allocator）管理内存，实现内存分配与对象构造分离；
• 尾插/尾删：直接操作 finish 指针，未扩容时效率极高。

15. map 的实现原理

std::map 底层基于红黑树（一种自平衡的二叉搜索树）实现，核心特性：

1. 有序性：按键的升序排列，二叉搜索树的中序遍历即为有序序列；
2. 自平衡性：通过变色、旋转（左旋/右旋）保证树的高度为 ​，避免退化为链表；
3. 存储结构：每个节点存储 std::pair<const Key, T>，键不可修改，保证二叉搜索树的特性；
4. 操作逻辑：增删查改均通过二叉搜索树的特性实现，时间复杂度稳定在 ​。

16. vector 与 list 的具体实现及常见操作时间复杂度

std::vector 实现与复杂度

• 实现：动态连续数组，由起始指针、有效尾指针、容量尾指针控制，依赖分配器管理内存，扩容时重新分配内存并移动元素。
• 核心复杂度：随机访问 ​、尾插/尾删均摊 ​、中间/头部插入/删除 ​。

std::list 实现与复杂度

• 实现：双向循环链表，每个节点包含数据、前驱指针、后继指针，头尾节点相连，支持双向遍历。
• 核心复杂度：随机访问 ​、任意位置插入/删除（找到位置后） ​、头尾插入/删除 ​。

17. unordered_map 的底层实现（哈希表）

• 核心结构：由哈希桶数组和链表（或红黑树）组成，开链法解决哈希冲突；
• 哈希函数：将键映射为桶索引，理想情况下均匀分布；
• 扩容机制：当负载因子（元素数/桶数）超过阈值（默认 0.75）时，触发扩容，重新哈希所有元素到新桶；
• 性能影响：哈希函数质量、负载因子、冲突解决策略直接影响查询效率。

18. std::array 与 std::vector 的区别

19. std::shared_ptr 的引用计数工作原理

1. 核心机制：shared_ptr 内部包含两个指针——指向实际对象的资源指针，和指向控制块的指针；
2. 控制块内容：引用计数（当前指向对象的 shared_ptr 数量）、弱引用计数、析构函数、删除器等；
3. 计数变化：拷贝 shared_ptr 时，引用计数加 1；shared_ptr 析构或赋值时，引用计数减 1；当引用计数变为0时，自动调用析构函数释放对象内存；
4. 线程安全：引用计数的增减是原子操作，多线程拷贝/析构 shared_ptr 线程安全，但访问对象仍需加锁。

20. std::unique_ptr 的实现及特点

• 核心特性：独占所有权，同一时间仅一个 unique_ptr 指向对象，不可拷贝，可移动；
• 实现：仅包含一个裸指针，无额外引用计数开销，析构时自动释放对象；
• 自定义删除器：支持指定删除器（如 unique_ptr<FILE, decltype(&fclose)>），适配非堆资源；
• 适用场景：资源独占、生命周期明确的场景，性能优于 shared_ptr。

21. std::weak_ptr 的作用及使用场景

• 作用：弱引用，不增加引用计数，仅观察 shared_ptr 管理的对象是否存在，避免循环引用；
• 使用场景：打破 shared_ptr 循环引用（如双向链表、父子对象）；缓存对象（如缓存中存储 weak_ptr，对象释放后自动失效）；
• 核心操作：lock() 方法将 weak_ptr 转为 shared_ptr，对象存在则返回有效指针，否则返回空。

22. 智能指针与裸指针的选择

• 优先使用智能指针：自动管理内存，避免泄漏和悬挂指针；
• unique_ptr：优先选择，性能高，独占所有权；
• shared_ptr：多所有者共享资源时使用，注意避免循环引用；
• 裸指针：仅用于非所有权的观察或传递（如函数参数），不负责内存管理。

23. 如何自己实现一个简化版的 std::vector？

核心实现内存分配与对象构造分离，包含构造、析构、尾插、扩容、下标访问等核心功能：

#include <memory>
#include <algorithm>

template <typename T>
class SimpleVector {
public:
    // 构造函数
    SimpleVector() : start(nullptr), finish(nullptr), end_cap(nullptr) {}

    // 析构函数
    ~SimpleVector() {
        // 析构所有有效元素
        for (T* p = start; p != finish; ++p) {
            p->~T();
        }
        // 释放内存
        alloc.deallocate(start, capacity());
    }

    // 尾插元素
    void push_back(const T& val) {
        if (finish == end_cap) {
            // 扩容：首次为4，后续2倍
            reserve(capacity() == 0 ? 4 : capacity() * 2);
        }
        // 构造元素
        alloc.construct(finish, val);
        finish++;
    }

    // 预分配内存
    void reserve(size_t n) {
        if (n <= capacity()) return;
        // 分配新内存
        T* new_start = alloc.allocate(n);
        T* new_finish = new_start;
        // 移动原元素
        for (T* p = start; p != finish; ++p) {
            alloc.construct(new_finish, std::move(*p));
            p->~T();
            new_finish++;
        }
        // 释放原内存
        alloc.deallocate(start, capacity());
        // 更新指针
        start = new_start;
        finish = new_finish;
        end_cap = start + n;
    }

    // 下标访问
    T& operator[](size_t idx) {
        return start[idx];
    }

    // 大小和容量
    size_t size() const { return finish - start; }
    size_t capacity() const { return end_cap - start; }

private:
    std::allocator<T> alloc; // 内存分配器
    T* start;                // 起始指针
    T* finish;               // 有效尾指针
    T* end_cap;              // 容量尾指针
};

24. STL 容器动态链接可能产生的问题？

1. ABI 不兼容问题：不同编译器、编译器版本对 STL 的实现细节（如 vector 扩容倍数、string 存储方式）不同，动态链接时会导致内存布局不匹配，触发崩溃或内存泄漏；
2. 单例/静态变量重复：STL 容器作为全局/静态变量时，动态链接库与主程序可能各自实例化，导致数据不一致；
3. 迭代器失效跨模块：在动态库中修改容器（如 vector 扩容），主程序持有的迭代器会失效，访问时触发未定义行为；
4. 解决方法：统一编译器和版本、使用静态链接、跨模块传递容器时使用值传递而非引用/指针、遵循相同的 STL 实现规范。

25. STL 分配器（allocator）的作用

• 核心作用：解耦容器与内存管理，容器不直接调用 new/delete，而是通过分配器分配/释放内存、构造/析构对象；
• 自定义分配器：可实现内存池、对齐分配、NUMA 感知分配等优化，提升性能；
• 标准分配器：std::allocator 默认使用全局 operator new/operator delete，线程安全且兼容大多数场景。

26. std::sort 的实现原理（内省排序）

• 核心实现：内省排序（Introsort），结合快速排序、堆排序和插入排序：优先使用快速排序（三路快排），递归深度控制在 ​ 以内；若递归深度超过阈值，切换为堆排序，避免快排最坏情况 ​；小区间（如 n<16）改用插入排序，减少递归开销；
• 特点：不稳定排序，时间复杂度稳定在 ​，空间复杂度 ​（递归栈）。

27. 如何选择 STL 容器？

• 需频繁随机访问：vector/array/deque；
• 需频繁在头尾插入删除：deque；
• 需频繁在任意位置插入删除：list；
• 需有序存储且支持范围查询：map/set；
• 需高频查询且无需有序：unordered_map/unordered_set；
• 需固定大小且栈上存储：array。

28. STL 容器的线程安全问题

• 默认线程安全：无，STL 容器不保证线程安全；
• 多线程场景：读操作并发安全（多个线程同时读）；写操作或读写并发需加锁（如 std::mutex）；迭代器遍历：遍历期间禁止修改容器，否则迭代器失效；
• 替代方案：使用线程安全容器（如 tbb::concurrent_vector）或自行封装同步逻辑。

29. std::move 与容器性能优化

• std::move 的作用：将左值转为右值引用，触发移动语义，避免不必要的拷贝；
• 容器优化：移动构造/赋值：vector/string 等容器支持移动操作，转移内存所有权，时间复杂度 ​；emplace 系列函数：emplace_back/emplace 直接在容器内构造对象，避免拷贝/移动；
• 注意：移动后原对象处于有效但未定义状态，不应再使用。

30. STL 中常见的“坑”及避坑指南

• 迭代器失效：修改容器时注意迭代器有效性，优先使用 erase 返回值更新迭代器；
• 容器拷贝开销：避免无意义的容器拷贝，使用移动语义或 std::string_view；
• unordered_map 哈希冲突：自定义哈希函数和相等比较，避免键类型哈希质量差；
• 动态链接 ABI 问题：统一编译器和版本，跨模块传递容器时谨慎；
• 线程安全：多线程操作容器必须加锁，避免数据竞争。