Подсчитайте записи и распечатайте K с помощью C/STL

Question

У меня есть большой текстовый файл с токенами в каждой строке. Я хочу подсчитать количество вхождений каждого токена и отсортировать его. Как я могу сделать это эффективно на C++, предпочтительно используя встроенные функции и кратчайшее кодирование (и, конечно, наиболее эффективное)? Я знаю, как это сделать в python, но не уверен, как это сделать, используя unordered_map в STL.

Answer 1

Я бы пошел с неупорядоченным подходом. Для выбора наиболее частых токенов k, считая, что k меньше, чем общее количество токенов, вы должны посмотреть на std::partial_sort.

Кстати, ++frequency_map[token] (где frequency_map есть, скажем, std::unordered_map<std::string, long>) вполне приемлемо в C++, хотя я думаю, что эквивалент в Python взорвется на вновь увиденных жетонах.

Хорошо, вот вы идете:

void most_frequent_k_tokens(istream& in, ostream& out, long k = 1) { 
    using mapT = std::unordered_map<string, long>; 
    using pairT = typename mapT::value_type; 
    mapT freq; 
    for (std::string token; in >> token;) ++freq[token]; 
    std::vector<pairT*> tmp; 
    for (auto& p : freq) tmp.push_back(&p); 
    auto lim = tmp.begin() + std::min<long>(k, tmp.size()); 
    std::partial_sort(tmp.begin(), lim, tmp.end(), 
     [](pairT* a, pairT* b)->bool { 
     return a->second > b->second 
       || (a->second == b->second && a->first < b->first); 
     }); 
    for (auto it = tmp.begin(); it != lim; ++it) 
    out << (*it)->second << ' ' << (*it)->first << std::endl; 
} 

Answer 2

Предполагая, что вы знаете, как читать строки из файла в C++, то это должно быть толчок в правильном направлении

std::string token = "token read from file"; 
std::unordered_map<std::string,int> map_of_tokens; 
map_of_tokens[token] = map_of_tokens[token] + 1; 

Вы можете распечатать их в качестве таковых (для теста):

for (auto i = map_of_tokens.begin(); i != map_of_tokens.end(); ++i) { 
    std::cout << i->first << " : " << i->second << "\n"; 
}