如果我已经“处理”了一个对象，std::unordered_map 是否适合记录？

Question

我有一个名为 Col 的结构：

struct Col
{
   Object* o1;
   Object* o2;
   Object* o3;

   bool operator==(const Col &other) const
   { 
       return o1 == o1 && o2 == o2 && o3 == o3;
   }
};

我对此定义了一个哈希：

template <>
struct std::hash<Col>
{
  std::size_t operator()(const Col& k) const
  {
    using std::size_t;

    std::hash<void> void_hash;

    std::size_t res = void_hash(k.o1) + void_hash(k.o2) + void_hash(k.o3;

    return res;
  }
};

然后，我有很多包含重复项std::vector的Col对象（根据我对相等的定义），并且我希望仅“处理”每个唯一元素一次。

这就是我所做的：

std::unordered_map<Col, bool> done_list;

for (Col c : col_list)
{
    if (done_list.find(c) == done_list.end())
    {
        process(c);

        done_list[c] = true;
    }
    else
    {
        continue;
    }
}

这是检查是否已处理相同对象集合的合理方法吗？稀疏矩阵会更好吗？

Answer 1

std::unordered_set你的方法是可以的，但是你可以通过使用而不是来简化它std::unordered_map。

该集合将包含您已经处理过的值。

#include <unordered_set>

std::unordered_set<Col> done_list;

for (Col const & c : col_list)
{
    if (done_list.find(c) == done_list.end())
    {
        process(c);
        done_list.insert(c);
    }
    else
    {
        continue;
    }
}

请注意，我const &在范围 for 循环中使用了以避免c. const如果需要改变它，你可以删除它。

如果您使用的是 c++20，您可以使用std::unordered_set::contains使检查更加简单：

    if (done_list.contains(c) == false)
    // ...

另一种变体利用了std::unordered_set::insert返回一对的重载，其中bool second指示该项目是否已插入（如果该项目已存在于集合中，则不会插入）：

    auto[it, inserted] = done_list.insert(c);
    if (inserted)
    {
        process(c);
    }
    else
    {
        continue;
    }