【嵌入式八股2】C++：STL容器与算法

1. STL常见容器及其内部实现的数据结构

2. deque底层数据结构

deque 底层实现通常是分段连续的内存结构，即由多个 vector 组成，允许高效的从两端进行元素的插入和删除。

3. 红黑树

红黑树是一种非严格平衡的二叉查找树，具有自动排序的功能。每个节点存储一个颜色（红或黑），并且通过调整树的结构保持特定的平衡条件，从而保证最坏情况下的查找效率。

4. 常见排序算法

4.1 sort()

• 适用容器：仅支持随机访问的容器，如 vector、deque、array。
• 功能：快速排序。

bool func(int a, int b) {
    return a > b;  // 降序排列
}
sort(vec.begin(), vec.end(), func);  // 对vector进行排序

4.2 partial_sort()

• 功能：对部分元素进行排序，使用堆排序实现。
• 参数：排序范围，默认排序前 n 个元素。

int n = 4;  // 需要排序的元素个数
partial_sort(vec.begin(), vec.begin() + n, vec.end(), func);  // 排序前4个元素

4.3 is_sorted()

• 功能：检查容器是否已排序。
• 返回值：布尔值，true 表示已排序。

bool result = is_sorted(vec.begin(), vec.end(), func);

4.4 is_sorted_until()

• 功能：返回第一个破坏排序规则的元素位置。

auto it = is_sorted_until(vec.begin(), vec.end(), func);

5. 查找操作

5.1 find()

• 功能：查找指定元素。

vector<int> vec{10, 20, 30, 40, 50};
auto it = find(vec.begin(), vec.end(), 30);  // 查找30
if (it != vec.end()) {
    cout << "查找成功：" << *it;
} else {
    cout << "查找失败";
}

5.2 find_if()

• 功能：根据自定义谓词查找元素。

bool mycomp(int i) {
    return (i % 2) == 1;  // 查找奇数
}
vector<int> myvector{4, 2, 3, 1, 5};
auto it = find_if(myvector.begin(), myvector.end(), mycomp);

6. 使用 vector 避免频繁的内存重新分配

vector 在扩容时通常会以 2 倍容量增长，这会导致频繁的内存分配和元素拷贝。为了优化性能，可以采取以下策略：

6.1 预分配内存

在创建 vector 时，可以使用 reserve() 方法预先分配内存，以减少多次扩容。

6.2 合理选择初始容量

根据数据的预计大小选择合适的初始容量，避免不必要的扩容操作。

6.3 优化算法

使用时间复杂度较低的算法，避免在数据量增大时造成性能瓶颈。

7. vector 的 resize() 与 reserve()

7.1 resize()

• 功能：调整容器的大小。
• 效果：如果 n 小于当前大小，则删除尾部元素；如果 n 大于当前大小，新的元素会被默认构造并添加到尾部。

7.2 reserve()

• 功能：调整容器的容量，不会改变当前大小。
• 效果：用于减少扩容次数，确保容器有足够的内存空间。

8. vector 扩容原理

• 扩容过程：每次扩容时，vector 会分配新的内存块并将现有元素复制到新内存中，旧内存被释放。
• 扩容系数：通常情况下，vector 容量每次会翻倍或增加 1.5 倍，这可以减少频繁的扩容。

8.1 Linux中的内存管理

在Linux系统中，内存区域以2的倍数扩容，以便进行高效的内存分配。

8.2 Windows中的内存管理

在Windows系统中，内存分配通常会增加1.5倍，以便更好地利用已经释放的内存。

9. 迭代器

迭代器是STL中用于访问容器元素的一种抽象工具。通过迭代器，容器元素的访问具有一致的接口，并且可以实现多态。

注意：迭代器只能前进，不能回退。

10. 迭代器失效的情况

迭代器可能会因为容器结构的修改而失效。不同类型的容器失效的情况略有不同：

• 数组型数据结构（如 vector）：insert 和 erase 操作会使插入或删除点之后的所有迭代器失效。
• 链表型数据结构（如 list）：erase 操作只会使指向删除元素的迭代器失效，其他迭代器不受影响。
• 树型数据结构（如 map）：erase 操作会使指向删除元素的迭代器失效，其他迭代器不受影响。 insert 操作不会使任何迭代器失效。