C++ Найти N-й наивысший элемент карты

Question

У меня есть вектор-строка std::vector<string> list, и я пытаюсь найти N-й самый высокий повторяющийся элемент вектора.

У меня есть карта, включающая элементы вектора и число повторений из них.

std::map<std::string , int> mapa; 
for(int i = 0 ; i<list.size() ; i++) 
    mapa[list[i]]++; 

Как найти N-ю самую высокую из них по карте?

Пример вектор:

qwe asd qwe asd zxc asd zxc qwe qwe asd sdf asd fsd 

, если N 2, мне нужно из положить как

asd 5 
qwe 4 

Answer 1

Вы можете использовать std::partial_sort:

std::map<std::string, std::size_t> 
compute_frequencies(const std::vector<std::string>& words) 
{ 
    std::map<std::string, std::size_t> res; 
    for(const auto& word : words) { 
     res[word]++; 
    } 
    return res;  
} 

std::vector<std::pair<std::string, std::size_t>> 
as_vector(const std::map<std::string, std::size_t>& m) 
{ 
    return {m.begin(), m.end()}; 
} 

int main() { 
    const std::vector<std::string> words{ 
     "qwe", "asd", "qwe", "asd", "zxc", "asd", 
     "zxc", "qwe", "qwe", "asd", "sdf", "asd", "fsd" 
    }; 
    auto frequencies = as_vector(compute_frequencies(words)); 
    std::partial_sort(frequencies.begin(), frequencies.end(), frequencies.begin() + 2, 
     [](const auto& lhs, const auto& rhs) { 
      return lhs.second > rhs.second;  
     }); 
    for (std::size_t i = 0; i != 2; ++i) { 
     std::cout << frequencies[i].first << " " << frequencies[i].second << std::endl; 
    } 
} 

Demo