遍历 C++ unordered_map 的时间复杂度 [英] Time complexity of iterating through a C++ unordered_map

问题描述

我知道 C++ STL 中的 unordered_map 被实现为哈希表，由与哈希值对应的桶组成.插入、删除和元素搜索的时间保证摊销不变.但是我不太明白迭代器是如何处理这个数据结构的.当我增加迭代器时，它如何知道下一个位置在哪里?当我使用迭代器遍历 unordered_map 时，时间复杂度是多少?用于查找迭代器下一个位置的时间是常数吗?我在The C++ Standard Library: A tutorial and Reference一书中找到了一些关于 unordered_map 内部结构的信息，但我找不到我的问题的答案.希望有人能帮忙！

I know that the unordered_map in C++ STL is implemented as hashtable consisting of buckets that correspond to hashed values. The time for insertions, deletions and element search is guaranteed to be amortized constant. However I don't quite understand how the iterator works on this data structure. When I increment the iterator, how does it know where is the next position? And what would the time complexity be when I iterated through a unordered_map using an iterator? Is the time used to find the next position of the iterator constant ? I found some information on the internal structure of unordered_map in the book The C++ Standard Library: A tutorial and Reference but I couldn't find the answer to my questions. Hope someone can help!

谢谢.

推荐答案

哈希表是使用包含链表的桶实现的.所以迭代很容易:

Hash tables are implemented using buckets that contain linked lists. So iterating is easy:

1. 查看当前节点是否有下一个指针.如果是这样，请转到那个.
2. 如果当前节点没有next指针，则转到下一个有节点的bucket.
3. 如果没有这样的节点，那么你就完成了迭代.

(通过找到第一个包含节点的桶来找到第一个节点.)

(Find the first node by finding the first bucket with a node in it.)

直观地说，由于使用上述算法遍历整个哈希表的时间为 O(n)，因此每个下一个"操作似乎都摊销了常数时间.

Intuitively, since iterating through the whole hash table using the above algorithm is O(n), it would appear that each "next" operation is amortised constant time.

这篇关于遍历 C++ unordered_map 的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！