我搜索了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))的時間複雜度。
你是否願意浪費一些額外的內存以加速c值的枚舉? – 2011-02-17 01:40:03