C++ unordered_map还是unordered_set :如果我想保持"isVisited“数据结构，应该使用什么？

Question

我希望保留一个数据结构，以存储到目前为止所见过的所有元素。考虑到将数组保留为元素是不可能的，因为元素的顺序是10^9，我应该使用什么数据结构来实现这一点：unordered_map还是unordered_set in C++？

在最坏情况下将访问的最大元素：10^5

-10^9 <= element <= 10^9

Answer 1

正如@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 better

Answer 2

在一个项目中，为了优化目的，将二叉树转换为二进制DAG (葛拉普根)，我将探测函数从节点指针传递给bool。

std::map<BinaryDrag<conact>::node*, bool> &visited_fl

该映射跟踪指针，以便在执行多次传递时不再遍历相同的节点。

你可以用std::unordered_map<Value, bool>。

Answer 3

我希望保留一个数据结构，以存储到目前为止所见过的所有元素。

一种改头换面的方法，即“我希望有一个数据结构来存储我到目前为止所见过的所有元素的set”。线索就在名字里。如果没有更多的信息，std::unordered_set似乎是表示集合的合理选择。

这就是说，在实践中，它取决于细节，比如你打算用这个集合做些什么。数组也可能是一个很好的选择(是的，即使对于数十亿元素也是如此)，其他集合实现可能更好，在某些用例中映射可能很有用。