面试题：C++中优化vector和map查询性能的策略

vector优化策略及原理

使用二分查找
- 举例：假设vector已经按升序排序，例如std::vector<int> v = {1, 3, 5, 7, 9};，要查找元素5，可以使用std::lower_bound函数，代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> v = {1, 3, 5, 7, 9};
    auto it = std::lower_bound(v.begin(), v.end(), 5);
    if (it!= v.end() && *it == 5) {
        std::cout << "找到元素5" << std::endl;
    }
    return 0;
}

- **原理**：二分查找利用了`vector`连续存储且有序的特性，每次将查找区间减半，时间复杂度从线性的O(n)降低到对数的O(log n)，大大提高了查询效率。因为每次比较都能排除一半的元素，从而快速定位目标元素。

2. 减少动态内存分配 - 举例：在初始化vector时，如果已知大概的元素数量，可以使用reserve方法预先分配足够的空间。例如：

#include <vector>
std::vector<int> v;
v.reserve(1000); // 预先分配能容纳1000个int的空间
for (int i = 0; i < 1000; ++i) {
    v.push_back(i);
}

- **原理**：`vector`在元素数量超过其当前容量时会重新分配内存，这涉及到内存的申请、数据的拷贝和旧内存的释放，开销很大。通过`reserve`预先分配足够空间，避免了频繁的动态内存分配和数据迁移，从而提升查询性能，因为数据在内存中连续存储且稳定，有利于快速定位和访问。

map优化策略及原理

选择合适的键类型
- 举例：如果使用std::map存储自定义类型作为键，确保该类型有高效的比较函数。例如定义一个简单的自定义类作为键：

#include <iostream>
#include <map>
class Point {
public:
    int x;
    int y;
    bool operator<(const Point& other) const {
        if (x!= other.x) {
            return x < other.x;
        }
        return y < other.y;
    }
};
int main() {
    std::map<Point, int> m;
    Point p1 = {1, 2};
    m[p1] = 10;
    return 0;
}

- **原理**：`std::map`内部是基于红黑树实现的，键值的比较操作频繁发生。一个高效的比较函数可以减少比较次数，从而提升查询性能。红黑树通过比较键值来确定节点的位置，高效的比较逻辑能使树的结构更合理，查找路径更短。

2. 批量插入 - 举例：当需要插入多个元素时，使用insert的范围版本。例如：

#include <iostream>
#include <map>
#include <vector>
int main() {
    std::map<int, int> m;
    std::vector<std::pair<int, int>> data = {{1, 10}, {2, 20}, {3, 30}};
    m.insert(data.begin(), data.end());
    return 0;
}

- **原理**：`std::map`每次插入单个元素时，红黑树需要进行调整以保持平衡，这有一定的开销。批量插入时，树的调整次数相对较少，整体效率更高，进而在后续查询时，由于树结构更优，查询性能也得到提升。

面试题：C++中优化vector和map查询性能的策略

知识考点

面试题答案

vector优化策略及原理

map优化策略及原理