STL面试

1.vector迭代器失效的问题？

vector中的插入/删除会改变元素的位置或数量，从而导致迭代器失效。对vector进行连续插入或者删除操作（insert/erase)，一定要更新迭代器。

2.array和vector的区别？

  • 大小是否可变：

    • std::array在编译时确定大小，运行时无法更改。
    • std::vector可在运行时动态调整大小

  • 底层实现：

    • std::array： 基于普通数组（连续存储）实现，直接存储在栈上（除非它是某个堆对象的一部分）。
    • std::vector： 基于动态数组实现，数据存储在堆上。（在使用vector这个结构的时候，如果vector在函数内部直接定义，则对象存储在栈上，数据存储在堆上；而通过new动态创建时，指针在栈上，对象和数据都在堆上。

  • 性能： vector插入或删除元素时可能需要重新分配内存和复制数据，导致性能下降。

    注：如果提前预留足够的容量（通过 reserve() 方法），可以减少动态分配的次数。

  • 容器大小：

    • std::array： 返回的是编译时固定的大小
    • std::vector：返回当前存储的元素数量

  • 迭代器失效：array迭代器永远不会失效，除非整个容器被销毁。

3.描述一下vetcor动态内存的基本原理

内存分配策略：

  • 分配更大的内存块：通过增长因子将容量翻倍（例如，从 4 → 8 → 16 → 32…）
  • 复制原有数据： 将原有数据从旧内存块复制到新内存块
  • 释放旧内存： 在完成数据迁移后，旧的内存块会被释放
  • 更新内部状态： 更新 capacity 和指向新内存块的指针。

4.介绍一下deque的底层结构

std::deque结合了数组和链表的特性

底层实现：分块存储

  • 主数组（Map 或索引数组）: 指针数组，存储指向各个小块（chunk）的指针。
  • 小块（Chunk）: 固定大小的连续内存区域，用于存储 std::deque 的实际数据。
  • 头部和尾部标记: std::deque 内部维护两个标记，分别指向当前数据的起始位置和结束位置。

注：deque支持随机访问

image-20250407170801444

5.list的底层结构是什么？

双向循环链表

6.容器适配器有哪些？底层结构是什么？

  • stack： 底层默认使用 std::deque
  • queue: 底层默认使用 std::deque
  • priority_queue: 底层默认使用std::vector。队列中的元素根据优先级排序，默认是大根堆。入队时进行排序，出队时排出优先级最高的元素，并对剩下的元素重新排序

容器适配器没有自己的数据结构，它的方法全部由底层依赖的容器进行实现