我正在使用 c++ STL unordered_map 库来解决一些 leetcode 问题。我可以使用 find 函数和 [] 运算符重载来访问我的元素。但我看到一些答案使用 for 循环来迭代 HashMap 的所有元素。根据我的理解, HashMap 的内部结构通常是一个 vector ,并且这个 vector 永远不会被完全使用(这意味着将有空槽来保持恒定的大O,以免发生太多碰撞)。但从答案中我看到人们正在迭代 vector ,但他们没有打印这些空索引,因为我没有看到任何垃圾值。我不明白这怎么可能。这是我见过的代码。
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for (string s : strs) {
mp[t].push_back(s);
}
vector<vector<string>> anagrams;
for (auto p : mp) { //this is the part I don't understand
anagrams.push_back(p.second);
}
return anagrams;
}
我希望迭代 HashMap 数据结构的基础 vector 的每个元素都具有垃圾值,因为并非所有成员都填充在 vector 中,但结果不包含这些值,仅给出正确的输出。我不明白怎么办。
最佳答案
从您的问题来看,您似乎可能认为 STL 容器的迭代器直接迭代底层数据结构。事实并非如此。迭代器本身可以包含字段和逻辑,以允许它以逻辑方式进行迭代。
标准库不规定算法实现,但所有常见的都可以支持迭代而无需遍历空元素:
您所写的封闭表实现(STL 的实现在实践中并未使用它)有一个条目数组,其中每个条目都被采用或不采用。每个条目可以通过具有一对数组(一个用于值,一个用于 bool 值)或使用两个数组来标记为已获取。在任何情况下,迭代时,迭代器都会在递增时简单地绕过所有未采用的条目。
更常见的实现是链表数组。这里,迭代器包含数组中的位置和列表的链接。当增加时,它尝试移动到下一个链接。如果不存在,则移至下一个非空列表。
关于c++ - c++ STL unordered_map 如何打印它的所有值?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57817008/