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)
you can do this: create a set so you get rid off duplicated, then find the frequency of every item of the set in the vector, with this result create a pair (something like int, int) push the pair in a vector and finally sort it using your own predicate:  

now for the top x you can do a for loop or just resize the vector if you are sure what the consequences of this are.

```
std::vector<int> numbers{32, 32, 32, 12, 12, 11, 11, 11, 9};
std::set<int> mySet(numbers.begin(), numbers.end());
std::vector<std::pair<int, int>> result{};

for(const auto& x : mySet)
{
    result.push_back(std::make_pair(x , std::count(numbers.begin(), numbers.end(), x)));
}
std::sort(result.begin(), result.end(), [](const std::pair<int, int>& a, const std::pair<int, int>& b){return (b.second < a.second);});
//result.resize(3);
std::cout << "Top: " << std::endl;
for(const auto& x : result)
{
   std::cout << x.first << ':' << x.second << std::endl;
}

```

the result will be:

> 
> Top: 11:3 32:3 12:2 9:1
> 
> 
>