c++ - boost multi_index : retrieve unique values of a non-unique key

Question

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

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

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

我现在需要检索一组 c 的所有不同值。这些值是无论如何不是唯一的，而是遍历所有条目(尽管是有序的)，或者使用 std::unique 似乎很浪费，考虑到c 的不同值的数量预计将 << 比总数条目数(例如，10 到 1000)。

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

Answer 1

我搜索了 Boost.MultiIndex 文档，但似乎无法找到一种方法来执行您想要的操作。我很想知道它是否可行。

也许您能做的最好的事情就是维护一个 std::map<C, size_t> (或 HashMap )与您的 multi_index_container 一起并让它们保持“同步”。

map 将 C 值与其出现次数(频率)相关联。它本质上是 C 值的直方图。每次添加 Elem给你的multi_index_container ，您增加直方图中的相应频率。当您删除 Elem来自你的 multi_index_counter ，您减少直方图中的相应频率。当频率达到零时，您从直方图中删除该条目。

要检索一组不同的 C 值，您只需遍历 <key,value>在直方图中配对并查看 key每对的一部分。如果您使用 std::map ，那么不同的 C 值将排序出来。

如果您打算只(或很少)检查一组不同的 C 值，那么我上面描述的方法可能有点矫枉过正。一种更简单的方法是将所有 C 值插入到 std::set<C> 中。然后遍历集合以检索不同的 C 值。

您说过不同 C 的集合比 C 的总数小得多。 std::set<C>因此，与将 C 复制到 std::vector 相比，该方法浪费的空间要少得多。 ，对 vector 进行排序，然后运行 ​​std::unique .

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