C++ unordered_map还是unordered_set :如果我想保持"isVisited“数据结构，应该使用什么？
提问于 2021-06-24 07:10:55
我希望保留一个数据结构，以存储到目前为止所见过的所有元素。考虑到将数组保留为元素是不可能的，因为元素的顺序是10^9，我应该使用什么数据结构来实现这一点：unordered_map还是unordered_set in C++？
在最坏情况下将访问的最大元素：10^5
-10^9 <= element <= 10^9
回答 3
Stack Overflow用户
回答已采纳
发布于 2021-06-24 07:29:55
正如@MikeCAT在评论中所说的那样，只有当您想要存储有关元素或访问的其他信息时，地图才会有意义。但是，如果您只想存储元素是否已被访问的真值，则映射将如下所示：
// if your elements were strings
std::unordered_map<std::string, bool> isVisited;这样就浪费了空间。存储真值是多余的，如果映射中字符串的存在已经表明它已被访问过。让我们来看看一个比较：
std::unordered_map<std::string, bool> isVisitedMap;
std::unordered_set<std::string> isVisitedSet;
// Visit some places
isVisitedMap["madrid"] = true;
isVisitedMap["london"] = true;
isVisitedSet.insert("madrid");
isVisitedSet.insert("london");
// Maybe the information expires so you want to remove them
isVisitedMap["london"] = false;
isVisitedSet.erase("london");现在，每个结构中存储的元素如下：
For the map:
{{"london", false}, {"madrid", true}} <--- 4 elements
{"madrid"} <--- 1 element. Much betterStack Overflow用户
发布于 2021-06-24 07:27:31
在一个项目中，为了优化目的，将二叉树转换为二进制DAG (葛拉普根)，我将探测函数从节点指针传递给bool。
std::map<BinaryDrag<conact>::node*, bool> &visited_fl该映射跟踪指针，以便在执行多次传递时不再遍历相同的节点。
你可以用std::unordered_map<Value, bool>。
Stack Overflow用户
发布于 2021-06-24 07:32:53
我希望保留一个数据结构，以存储到目前为止所见过的所有元素。
一种改头换面的方法，即“我希望有一个数据结构来存储我到目前为止所见过的所有元素的set”。线索就在名字里。如果没有更多的信息，std::unordered_set似乎是表示集合的合理选择。
这就是说，在实践中，它取决于细节，比如你打算用这个集合做些什么。数组也可能是一个很好的选择(是的，即使对于数十亿元素也是如此)，其他集合实现可能更好，在某些用例中映射可能很有用。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/68118371
复制相关文章
腾讯云开发者
