升壓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））的時間複雜度。