Question: I have a vector with integers. I would like to select the most common numbers. I would like to make a top 5 list. For example:

```
std::vector<int> numbers = {32, 32, 32, 12, 12, 11, 11, 11, 9};

```

the most common numbers are: TOP 1: 32, TOP 2: 11, TOP 3: 12, TOP 4: 9;

after I selected them, I would like to store it into an other vector: the most common numbers.

Answer: 
Here's another algorithm, the cost is going to be O(n) for any `k`, plus a decent cache locality.

1.First store all elements in a `unordered_map` O(N)

```
std::unordered_map<int, int> m;
for(const auto ele: numbers) {
  m[ele]++;   
}

```

2.Dump all elements in a vector of pairs O(N) 

```
std::vector<std::pair<int, int>> temp;  
for(const auto& ele: m) {
 temp.emplace_back(ele.first ,  ele.second);   
}

```

3.Now use the nth\_element to find kth rank O(N) 

```
std::nth_element( temp.begin(), temp.begin()+k ,
temp.end(), [](const auto& p1, const auto& p2) {
        // Strict weak ordering
        if (p1.second > p2.second) {
            return true;
        }  if (p1.second < p2.second) {  
            return false;
        }
        return p1.first > p2.first; // We have to print large element first
    } );

```

4.Display the output

```
std::for_each( temp.begin(), temp.begin() +k - 1, [](const auto & p) {
    std::cout << p.first << " ";
});

```

[`Demo Here`](https://rextester.com/JIP26813)
I've made this example and put comments in-line. It needs C++11 at least.

```
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>

int main(void) {
  std::map<int, int> ans;
  std::vector<int> numbers = {32, 32, 32, 12, 12, 11, 11, 11, 9};
  std::vector<std::pair<int, int>> sorted;
  std::vector<int> common;
  // Step 1 Accumulate into a map, counting occurrences
  for (auto number : numbers) {
    ans[number]++;
  }
  // Step 2 Make a linear list, putting the count first then the value
  for (auto& ent : ans) {
    sorted.emplace_back(ent.second, ent.first);
  }
  // Step 3 sort it, by count ascending
  std::sort(std::begin(sorted), std::end(sorted));

  // Step 4 Get commonest 5 (or fewer)
  for (int i = 1; i<= 5; ++i) {
    int index = sorted.size() - i;
    if (index >= 0) {
      common.push_back(sorted[index].second);
    }
  }

  // Step 5 print out
  for (auto i : common) {
    std::cout << i << std::endl;
  }
  return 0;
}

```