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)
There are many many ways how to achieve this. One of which may be.

```
std::vector numbers = {32, 32, 32, 12, 12, 11, 11, 11, 9};
int maxNumber = *std::max_element(numbers.begin(), numbers.end())
std::vector<int> occurrences(maxNumber + 1, 0);
for(auto& value : numbers)
{
   occurrences[value]++;
}

```

Then you just need to sort the array whilst keeping track of the indexes. This is a topic of another question [C++ sorting and keeping track of indexes](https://stackoverflow.com/questions/1577475/c-sorting-and-keeping-track-of-indexes).