The problemGiven 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 inspirationWriting 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.QuestionsIn 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_Htest.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();}OutputOutput from the test driver above looks like this:Test 1 {    1, 6    2, 5    3, 3}Test 2 {    chuck, 2    woodchuck, 2    wood, 2}
Template to determine most frequent entries within a collection
c++;c++11;template meta programming