c++ - 存储分组关系和支持外观的最佳数据结构

Question

我需要创建一个数据结构来跟踪一些分组信息。假设元素只是字符串。例如，{'a', 'b', 'c'} 是一个组，{'e', 'f', 'g'} 是另一个组。我还需要支持按键查找，而按键都是字符串。现在，我可以考虑使用 map :

{a} -> {"a", "b", "c"}
{b} -> {"a", "b", "c"}

{e} -> {"e", "f", "g"}
{f} -> {"e", "f", "g"}

但在这种情况下，我会在 map 中复制大量信息，而且尺寸会爆炸。还有什么好的数据结构，既紧凑又支持快速查找？

Answer 1

But in this case, I am duplicating lots of information in the map and the size will explode. Any other good data structure which is compact and also support fast lookup?

不是将元素直接映射到组，而是可以引入一个额外的间接级别，通过将 std::string 元素映射到 来消除这种重复组 ID，它们是索引。然后，您可以保留组的 std::vector。您使用映射检索到的组 ID 来索引这个组 vector 。

作为实现这个想法的例子:

#include <unordered_map>
#include <unordered_set>
#include <string>
#include <vector>

class GroupRelation {
   std::unordered_map<std::string, group_id_t> elem2group_id_;
   std::vector<std::unordered_set<std::string>> groups_;
public:
   using group_id_t = size_t;

   auto num_groups() const { groups_.size(); }

   auto add_group(std::unordered_set<std::string> group) {
      auto grp_id = groups_.size();
      for (auto const& elem: group)
         elem2group_id_[elem] = grp_id;

      groups_.push_back(std::move(group));
      return grp_id; // return group_id_t of just added group
   }

   // for checking whether or not an element is in a group
   bool is_in_group(const std::string& elem) const {
      auto it = elem2group_id_.find(elem); 
      return elem2group_id_.end() != it;
   }

   // returns the group ID where the element belongs
   group_id_t group_id(const std::string& elem) const {
      auto it = elem2group_id_.find(elem); 
      return it->second;
   }

   const std::unordered_set<std::string>& group(group_id_t group_id) const {
      return groups_[group_id];
   }

   std::unordered_set<std::string>& group(group_id_t group_id) {
      return groups_[group_id];
   }
};

从元素中检索组 ID 平均可以在常数时间内完成。

使用示例:

auto main() -> int {
   GroupRelation grp_rel;

   grp_rel.add_group({"a", "b", "c"});   
   grp_rel.add_group({"e", "f", "g"});

   for (auto const& elem: grp_rel.group(0))
      std::cout << elem << ' ';
   std::cout << '\n';

   for (auto const& elem: grp_rel.group(1))
      std::cout << elem << ' ';
   std::cout << '\n';

}

我的输出:

b c a 
g f e