How to sort a multiset to a container by the number of element occurences

Question

I want to get the elements sorted by the number of their occurence. This is what I have come up with (mHeights is a std::multiset):

namespace{
  template<class U,class T>
  class HistPair{
    public:
      HistPair(U count,T const& el):mEl(el),mNumber(count){      
      }
      T const&  getElement()const{return mEl;}

      U getCount()const{return mNumber;}
    private:
      T mEl;
      U mNumber;
  };

  template<class U,class T>
  bool operator <(HistPair<U,T> const& left,HistPair<U,T> const& right){
    return left.getCount()< right.getCount();
  }
}

std::vector<HistPair<int,double>  > calcFrequentHeights(){
  typedef HistPair<int,double> HeightEl;
  typedef std::vector<HistPair<int,double>  > Histogram;
  std::set<double> unique(mHeights.begin(),mHeights.end());
  Histogram res;
  boostForeach(double el, unique) {
    res.push_back(HeightEl(el,mHeights.count(el)));    
  }
  std::sort(res.begin(),res.end());
  std::reverse(res.begin(),res.end()); 
  return res;
}

So first I take all unique elements from the multiset, then I count them and sort them into a new container (I need the counts so I use a map). This looks quite complicated for such an easy task. Apart from the HistPair, which is used elsewhere as well, isn't there any stl algorithm that would simplify this task e.g. using equal_range or sth. alike.

Edit: I need the number of occurences as well, sorry I forgot about that

Answer 1

This snippet does what you want, by combining an std::set, a lambda and std::multiset::count:

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

int main() {
    std::multiset<int> st;
    st.insert(12);
    st.insert(12);
    st.insert(12);
    st.insert(145);
    st.insert(145);
    st.insert(1);
    st.insert(2);

    std::set<int> my_set(st.begin(), st.end());
    std::vector<int> my_vec(my_set.begin(), my_set.end());
    std::sort(my_vec.begin(), my_vec.end(), 
      [&](const int &i1, const int &i2) {
          return st.count(i1) < st.count(i2);
      }
    );

    for(auto i : my_vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
}

You might want to reverse the vector. This outputs:

1 2 145 12

Edit: Taking into account you also need the item count, this will do it:

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

int main() {
    typedef std::vector<std::pair<int, int>> MyVector;
    std::multiset<int> st;
    st.insert(12);
    st.insert(12);
    st.insert(12);
    st.insert(145);
    st.insert(145);
    st.insert(1);
    st.insert(2);

    std::set<int> my_set(st.begin(), st.end());
    MyVector my_vec;
    my_vec.reserve(my_set.size());

    for(auto i : my_set) 
        my_vec.emplace_back(i, st.count(i));

    std::sort(my_vec.begin(), my_vec.end(), 
      [&](const MyVector::value_type &i1, const MyVector::value_type &i2) {
          return i1.second < i2.second;
      }
    );

    for(const auto &i : my_vec)
        std::cout << i.first << " -> " << i.second << std::endl;
}

Which outputs:

1 -> 1
2 -> 1
145 -> 2
12 -> 3