Ivy*_*Ivy 1 c++ optimization unordered-map
我有一个无序的字符串和字符串向量的地图,即un_map<string,vector<string> >.使用find函数搜索特定字符串时:
find((un_map[A].begin(),un_map[A].end(),field)==un_map[A].end())
无序映射和有序映射的查找函数的执行时间是相同的.谁能解释为什么这样？到目前为止,我知道由于散列,无序地图应该比有序地图快得多.我想优化查找功能.请帮忙
std::find正在使用标准迭代在所有容器上进行搜索,仅使用迭代器的增量.所以,这里的复杂性是O(n).
要加速查找元素,基于容器,您需要调用find容器的方法.
std::unordered_map::find 搜索O(1)的复杂性,因为正如您所指出的,它使用散列.
std::map::find 搜索复杂度为O(log(n)),因为它使用二进制搜索.