Dar*_*i99 3 performance unordered-map hashtable hashmap multimap
C++库中的内置映射和集合(包括unordered_map和multimap)要求find函数(用于查找特定元素)使用迭代器来遍历元素.C++参考站点声称使用这些数据结构查找元素平均需要时间,就像常规哈希表一样.但是,迭代器是否必须遍历整个列表,在找到元素之前平均得到这个O(n)时间？
Net*_*peC 10
你的陈述不是真的:
map,set,multimap和multiset通常为二叉树(例如:在VS实现为红黑树)来实现,在这种情况下,find方法使用在一个节点的属性进行搜索的关键left child is less不是节点(根据比较器)和the right child is greater比节点(根据比较器).根据标准的要求,给出O(log n).unordered_map和unordered_set被实现为哈希表,通常作为桶的集合实现的(例如:std::vector<Bucket>)和铲斗被实现为的元素的集合unordered_map(例如:std::vector<elem>或者std::list<elem>),假设散列函数是恒定的时间(或排除时间),此集合中的搜索是平均恒定时间O(1)(散列给出放置元素的桶,如果桶中搜索的元素很少,那么目标元素之间).最坏的情况是,在这种情况下,当所有元素都在同一个桶中时,目标元素的搜索将需要遍历桶中的所有元素,直到找到或不存在(在O(n)中).通过良好的散列函数,您可以在桶中增加足够均匀分裂的概率(获得预期的恒定时间).注意:find函数返回一个iterator并不意味着使用迭代器来搜索请求的元素.