Boost multi_index：检索非唯一键的唯一值

Question

我有一个 boost::multi_index_container ，其元素是这样的结构：

struct Elem {
    A a;
    B b;
    C c;
};

主键（在数据库意义上）是 a 的 composite_key 和b。其他 键的存在是为了执行各种类型的查询。

我现在需要检索 c 的一组所有不同值。这些值是 无论如何不是唯一的，但是迭代所有条目（尽管是有序的）， 或使用 std::unique 似乎相当浪费，考虑到 c 的不同值的数量预计为 <<比总数 条目数（例如 10 到 1000）。

我是否缺少一种更有效地获得此结果的简单方法？

Answer 1

我搜索了 Boost.MultiIndex 文档，似乎找不到一种方法来完成您想要的操作。我有兴趣知道这是否可行。

也许您能做的最好的事情就是在您的 multi_index_container 旁边维护一个 std::map （或哈希映射），并使它们保持“同步”。

该映射将 C 值与其出现次数（频率）相关联。它本质上是 C 值的直方图。每次将 Elem 添加到 multi_index_container 时，都会增加直方图中相应的频率。当您从 multi_index_counter 中删除 Elem 时，直方图中相应的频率就会减少。当频率达到零时，您可以从直方图中删除该条目。

要检索一组不同的 C 值，您只需迭代直方图中的 对并查看每对的 key 部分即可。如果您使用了 std::map，那么不同的 C 值将会排序。

如果您只想检查一组不同的 C 值一次（或很少），那么我上面描述的方法可能有点矫枉过正。一种更简单的方法是将所有 C 值插入到 std::set中，然后迭代该集合以检索不同的 C 值。

你说不同的 C 的集合比 C 的总数小得多。因此，std::set 方法比将 C 复制到 std::vector、对向量进行排序，然后运行 ​​std 浪费的空间要少得多::独特。

让我们比较一下复制到集合与复制到向量、排序然后运行 ​​unique 的时间复杂度。令 N 为 C 值的总数，令 M 为不同 C 值的数量。根据我的计算，集合方法的时间复杂度应该为 O(N*log(M))。由于 M 很小并且不会随着 N 的增加而增长太多，因此复杂度实际上变成了 O(N)。另一方面，排序+独特技术的时间复杂度应该为 O(N*log(N))。

Answer 2

我解决这个问题的方法是使用升压范围适配器，如下所示

const auto& indexedContainer = container.get<IndexType>();
const auto uniqueIndexRange = indexedContainer 
    | boost::adaptors::transformed([&](auto&& v) {
        return indexedContainer.key_extractor()(v); })
    | boost::adaptors::uniqued;