欢迎关注本公众号，专注面试题拆解
分享一套视频课程《C++百万并发服务器开发》，有需要的加我微信获取：fb964919126
面试题：单纯的查询而言，是vector快还是map快？
答案：map快，因为map的时间复杂度是O(logn),而vector的查询时间是O(n).
题目拆解：
这道题目需要知道vector查询和随机访问的不同。
假设有一个包含 n 个元素的vector集合，需要查询某个特定的元素
如果知道元素的位置（索引），可以直接通过索引访问
std::vector<int> vec = {1, 2, 3, 4, 5};int index = 2; // 索引为 2 的元素int value = vec[index];std::cout << "Value at index " << index << ": " << value << std::endl;
这种情况时间复杂度为O(1)。
如果不知道元素的位置，需要遍历整个向量来查找：
std::vector<int> vec = {1, 2, 3, 4, 5};int target = 3; // 查找值为 3 的元素auto it = std::find(vec.begin(), vec.end(), target);if (it != vec.end()) {std::cout << "Found value " << target << " at index " << std::distance(vec.begin(), it) << std::endl;} else {std::cout << "Value " << target << " not found." << std::endl;}
在这种情况下，查找的时间复杂度为 O(n)。
1
std::vector
数据结构：std::vector 底层使用一个连续的内存块来存储元素。
查询方式：支持快速的随机访问（常数时间 O(1)），通过索引可以直接访问元素。
2
std::map
数据结构：std::map 底层使用红黑树（Red-Black Tree）来存储键值对。
查询方式：支持基于键的查询（对数时间 O(log n)），通过键可以查找对应的值。
3
对比
随机访问：
std::vector：支持快速的随机访问，通过索引访问元素的时间复杂度为 O(1)。
std::map：不支持随机访问，因为它是基于键进行查找的。
基于键的查询：
std::vector：不支持基于键的查询，因为 std::vector 存储的是连续的元素，没有键的概念。
std::map：支持基于键的查询，通过键查找元素的时间复杂度为 O(log n)，其中 n 是容器中的元素数量。
总结：
随机访问：如果你需要通过索引快速访问元素，使用 std::vector 更合适，因为它的查询时间复杂度为 O(1)。
基于键的查询：如果你需要根据键来查找元素，使用 std::map 更合适，因为它的查询时间复杂度为 O(log n)。
因此，在单纯查询性能方面：
对于随机访问：std::vector 快。
对于基于键的查询：std::map 快。
而题目中问的是查询，不是随机访问，所以这道题目答案是map快，其实实际测试过程中，当数量比较少的时候（1000以内），可能vector比较快，因为vector是一块连续的内存，而map底层是红黑树，内存不连续，数据量少的时候，算法的优势没有抵消掉缓存的优势。
end
CppPlayer
关注，回复【电子书】珍藏CPP电子书资料赠送
精彩文章合集
专题推荐
