4

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

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

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

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

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

4

2 回答 2

1

我搜索了 Boost.MultiIndex 文档，似乎找不到一种方法来做你想做的事。我有兴趣知道它是否可行。

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

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

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

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

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

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

于 2011-02-17T03:22:38.563 回答
0

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

const auto& indexedContainer = container.get<IndexType>();
const auto uniqueIndexRange = indexedContainer 
    | boost::adaptors::transformed([&](auto&& v) {
        return indexedContainer.key_extractor()(v); })
    | boost::adaptors::uniqued;
于 2021-11-08T23:16:59.977 回答