升压multi_index：获取的非唯一键

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>（或哈希地图）旁边的multi_index_container，并保持他们两个“同步”。

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

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

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

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

让我们比较复制到集合与复制到矢量的时间复杂度，排序，然后运行unique。令N为C值的总数，并且令M为不同C值的数目。根据我的估算，设置的方法应该具有O（N * log（M））的时间复杂度。由于M很小并且在较高的N下增长不多，所以复杂度有效地变为O（N）。另一方面，排序+独特技术应该具有O（N * log（N））的时间复杂度。