面试题：C++ vector在复杂场景下的元素访问效率优化

数据访问策略：
- 由于vector<int>支持随机访问，其底层采用连续内存存储，可直接通过索引访问元素，时间复杂度为$O(1)$。这对于频繁随机访问的需求来说是非常合适的。例如：
```
std::vector<int> largeVector;
// 初始化largeVector
int value = largeVector[index];// 这里index为要访问的索引，这种访问方式效率很高
```
数据修改策略：
- 插入操作：如果在vector中间插入少量元素，vector的insert操作时间复杂度为$O(n)$，因为插入元素后需要移动插入位置之后的所有元素。为了减少这种开销，可以考虑预先分配足够的空间，避免在插入时频繁重新分配内存。例如：
```
largeVector.reserve(largeVector.size() + numElementsToInsert);
largeVector.insert(largeVector.begin() + insertIndex, elementToInsert);
```
- 删除操作：vector的erase操作时间复杂度同样为$O(n)$，因为删除元素后需要移动删除位置之后的所有元素。为了优化删除操作，可以采用“删除 - 标记”策略，即不立即删除元素，而是标记为已删除，在适当的时候（例如数据量达到一定阈值或者程序空闲时）再一次性清理这些标记的元素。代码示例如下：
```
std::vector<bool> deletedFlags(largeVector.size(), false);
// 标记要删除的元素
deletedFlags[deleteIndex] = true;
// 后续在合适时机清理
std::vector<int> newVector;
for (size_t i = 0; i < largeVector.size(); ++i) {
    if (!deletedFlags[i]) {
        newVector.push_back(largeVector[i]);
    }
}
largeVector = std::move(newVector);
```
综合优化：
- 可以考虑使用缓存机制，对于频繁访问的元素进行缓存，这样下次访问时可以直接从缓存中获取，进一步提高访问效率。例如使用std::unordered_map<int, int>作为缓存，键为元素的索引，值为对应的元素值。
```
std::unordered_map<int, int> cache;
int value;
if (cache.find(index) != cache.end()) {
    value = cache[index];
} else {
    value = largeVector[index];
    cache[index] = value;
}
```

通过上述策略，可以在保证频繁随机访问效率的同时，尽量减少在vector中间插入或删除少量元素对整体效率的影响。

星途面试题库

面试题：C++ vector在复杂场景下的元素访问效率优化

知识考点

面试题答案