【LeetCode-C-Container】vector

emplace vs. insert

在C++ STL中，vector的emplace和insert方法都用于插入元素，但它们在实现机制和使用场景上有显著差异。

核心机制对比

临时对象处理
- insert：需要先构造临时对象，再将对象拷贝或移动到容器中。例如：
```
v.insert(pos, Foo(42, 3.14));  // 需显式构造Foo对象
```
- emplace：直接在容器内存中构造元素，通过完美转发和变参模板传递构造参数，避免临时对象：
```
v.emplace(pos, 42, 3.14);  // 直接在pos位置构造Foo对象
```

性能差异

emplace减少了拷贝/移动构造函数调用。例如，对于需要复杂构造的类：

// insert调用构造函数+移动构造函数
demo.insert(pos, testDemo(1));  // 输出："调用构造函数" + "调用移动构造函数"
// emplace仅调用构造函数
demo.emplace(pos, 1);           // 输出："调用构造函数"

对于基础类型（如int），性能差异可忽略；但对大型对象或频繁插入场景，emplace效率更高。

语法与功能对比

特性	`insert`	`emplace`
插入方式	插入已构造的对象	通过参数直接构造对象
参数类型	接受对象、初始化列表、范围等	仅接受构造参数（变参模板）
多元素插入	支持（如`insert(pos, n, elem)`）	仅支持单元素插入
显式构造函数	需显式构造临时对象	支持隐式参数传递（避免显式构造）

使用场景建议

优先使用emplace的情况
- 插入需要复杂构造的对象（如自定义类）
- 需要避免隐式类型转换（尤其是explicit构造函数）
- 对性能敏感的场景（如高频插入大型对象）
仍需使用insert的情况
- 需要插入多个元素（如批量插入或初始化列表）
- 需要复用已有对象（如从其他容器复制元素）

代码示例对比

// 插入自定义类对象
struct Bar {
    explicit Bar(int a, double b) { ... }
};

vector<Bar> v;
v.insert(v.end(), Bar(1, 2.0));  // 需显式构造临时对象
v.emplace(v.end(), 1, 2.0);      // 直接传递构造参数

// 插入多个元素
vector<int> nums{1, 2};
nums.insert(nums.begin(), 3, 5);      // 插入3个5
// nums.emplace(...) 无法实现多元素插入

总结

维度	`insert`	`emplace`
核心优势	灵活性高，支持多元素操作	性能优，避免临时对象构造
适用场景	批量插入、已有对象复用	复杂对象构造、高频插入场景

建议默认优先使用emplace，仅在需要多元素操作或已有对象复用时选择insert。

vector

C++ STL 中的 vector 类主要由以下部分构成：

动态数组：底层通过连续内存的数组实现，支持随机访问。
指针管理：
- _start（或 begin() 迭代器）：指向数组首元素。
- _finish（或 end() 迭代器）：指向最后一个元素的下一个位置（表示当前有效元素数量）。
- _endofstorage（或容量指针）：指向分配内存的末尾位置（表示当前总容量）。
元数据：
- size：通过 _finish - _start 计算当前元素数量。
- capacity：通过 _endofstorage - _start 计算总容量。
内存分配器：用于动态管理内存的分配和释放（默认使用 std::allocator）。

对于 vector<vector<int>> 的结构：

外层 vector 存储的是内层 vector<int> 的实例。每个内层 vector<int> 本身是一个独立的动态数组，可以存储 int 类型数据。
这种嵌套结构本质上是一个 二维动态数组，类似于表格的行列结构。例如：
```
vector<vector<int>> matrix = {{1,2}, {3,4}, {5,6}};
```
外层 matrix 的每个元素是一个 vector<int>，如 {1,2}、{3,4} 等，每个内层 vector 的长度可以不同，实现类似“锯齿数组”的效果。

关键特性补充：

扩容机制：当插入元素超过当前容量时，外层或内层 vector 会按倍数（通常 1.5 或 2 倍）重新分配更大内存，并迁移原有数据。
连续存储：尽管外层 vector 的元素（内层 vector）在堆上独立分配，但外层 vector 自身的内存布局是连续的（存储的是指向内层 vector 的指针或控制块）。