Template to determine most frequent entries within a collection

Question

The problem

Given an arbitrary collection of objects of some kind, count and report the top k most frequent, together with the associated count. For example, if the input array is {'a', b', 'a', 'c', 'b', 'b'} and for k = 2, the template would return { {b, 3}, {'a', 2} }. The idea for the template it to allow start and ending iterators for any kind of collection for which ::value_type is defined.

The inspiration

Writing this review reminded me that I had, at one point, written a template to solve exactly this kind of problem. So I searched the hard drive, found this, and thought I'd present it here to see if might be critiqued and improved.

Questions

In particular, I'd be interested in any scenario in which the template fails. Additionally, are there any checks that could be made to make sure that only suitable iterators are passed? If so, what might those be?

maxfreq.h

#ifndef MAXFREQ_H
#define MAXFREQ_H
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <iterator>

/* 
 * This template takes a start and ending iterator of a collection of
 * some kind.  It counts the number of occurences for each instance and
 * returns a vector of the top `k` instances each with their associated
 * count.
 */
template <class InputIt>
auto most_frequent_k(InputIt first, InputIt last, std::size_t k) -> std::vector<std::pair<typename InputIt::value_type, unsigned>> {
    typedef typename InputIt::value_type T;
    typedef typename std::pair<T, unsigned> Tcount;
    std::unordered_map<T, unsigned> count;
    for (; first != last; ++first) {
        ++count[*first];
    }
    std::vector<Tcount> pairs;
    auto m = count.size();
    pairs.reserve(m);
    k = std::min(k, m);
    std::copy(count.begin(), count.end(), std::back_inserter(pairs));
    std::partial_sort(pairs.begin(), pairs.begin()+k, pairs.end(), [](const Tcount &a, const Tcount &b) {
            return a.second > b.second;
            });
    pairs.erase(pairs.begin()+k, pairs.end());
    return pairs;
}

#endif // MAXFREQ_H

test.cpp

#include "maxfreq.h"
#include <iostream>
#include <sstream>

void test1()
{
    std::cout << "Test 1 {\n";
    std::vector<int> input{1,2,3,4,2,3,4,1,1,2,1,2,1,2,1,3,5};
    auto pairs = most_frequent_k(input.begin() , input.end(), 3);
    for (const auto &p : pairs) {
        std::cout << '\t' << p.first << ", " << p.second << '\n';
    }
    std::cout << "}\n";
}

void test2()
{
    std::cout << "Test 2 {\n";
    std::istringstream woodchuck{"how much wood would a woodchuck chuck if a woodchuck could chuck wood"};
    std::vector<std::string> input{};
    std::copy(std::istream_iterator<std::string>(woodchuck), std::istream_iterator<std::string>(), std::back_inserter(input) );
    auto pairs = most_frequent_k(input.begin() , input.end(), 3);
    for (const auto &p : pairs) {
        std::cout << '\t' << p.first << ", " << p.second << '\n';
    }
    std::cout << "}\n";
}

int main()
{
    test1();
    test2();
}

Output

Output from the test driver above looks like this:

Test 1 {
    1, 6
    2, 5
    3, 3
}
Test 2 {
    chuck, 2
    woodchuck, 2
    wood, 2
}

Answer 1

I think you can simplify the generation of the vector from this

std::vector<Tcount> pairs;
auto m = count.size();
pairs.reserve(m);
k = std::min(k, m);
std::copy(count.begin(), count.end(), std::back_inserter(pairs));

to that

std::vector<Tcount> pairs(count.begin(), count.end());

This simplifies your code to

std::vector<Tcount> pairs(count.begin(), count.end());
std::partial_sort(pairs.begin(), pairs.begin()+std::min(k, m), pairs.end(), [](const Tcount &a, const Tcount &b) {
        return a.second > b.second;
        });
pairs.erase(pairs.begin()+k, pairs.end());

With the added benefit, that you can now declare k as const. However, it would be arguable whether you should throw a warning in case k > min.

Answer 2

Well, nice to see you follow stdlib conventions for your algorithm and accept an iterator-range.
But you really should use std::iterator_traits<It> to query the iterators associated types, as-is you cannot handle pointers.

Let's hope the elements are efficiently copied, or the algorithm is staggeringly inefficient.

Next, the count of unique symbols is often much smaller than k, making first inserting all elements, then sorting and finally removing most quite inefficient.
Consider limiting the result-vector to never grow beyond k elements using a heap.
(The standard provides std::make_heap (and for sorted output alsostd::sort_heap), but not down_heap (a vastly more efficient combination of std::pop_heap and std::push_heap, building-block of make_heap).)