how to get the number of the element that appears most in a multiset

Jun 27, 2011 at 11:21pm
I have a STL multiset
and I want to get the number of the elements that appears most in it
is there any existent function or method

for example, in a multiset, the elements are
1 3 3 3 4 4 4 4 5 5
then the elements that appears most is 4
and the number of 4's in the multiset is 5
so I will get 5
Jun 27, 2011 at 11:37pm
You can use the std::multiset::count method which returns the count for a specific key. You'll have to iterate over the keys, keeping track of the max count and the key associated with it.
Jun 28, 2011 at 12:29am
hmm, the complexity could be very high
I need to frequently get the number
Jun 28, 2011 at 12:35am
If you need to frequently get the mode, why not store it? Unless your values will be changing often...?
Jun 28, 2011 at 1:10am
I suggest a combination of what shacktar and LB suggested. After you build your multiset, count the elements and store the results in a std::map<int, int>. Also store the mode. You have to do this only once. Now, every time you change your set, modify the frequency map and, if necessary, change the mode. Does this look good?

EDIT: In fact, maybe a map is a better container for your data in the first place...
Last edited on Jun 28, 2011 at 1:16am
Jun 28, 2011 at 1:28am
Since a multiset is a sequenced container just as a map is, there is no need to store both a multiset of values and a map of counts. If you only stored a map of (value,count), you can easily reconstruct the multiset by performing an in-order walk of the map.

Walking the map to find the most common value will be more efficient than walking the multiset, particularly if there are many duplicates. However, if that isn't fast enough, you can consider using a boost::multi_index_container where the first index is your map/multiset sort criterion and the second is on the count.
Jun 28, 2011 at 4:59am
What would be wrong with treating the multiset as an array and iterating through it with two loops comparing each element with element[0], then each element with element[1] and so on, counting the repeats. You would not need to sort the set either. It doesn`t seem to be overly slow?
Topic archived. No new replies allowed.