How to ensure that a template parameter has a value_type and is iterable?

Question

I would like to generalize a function using templates. And, the template parameter should be checked somehow.

As a minimum reproducable example I have written a function that will return the top frequent element of a container. For better understanding, please see the below simple code:

#include <iostream>
#include <utility>
#include <unordered_map>
#include <queue>
#include <vector>

// Predicate Functor
template <class Container> struct LessForSecondOfPair {
    bool operator () (const std::pair<typename Container::value_type, size_t>& p1, const std::pair<typename Container::value_type, size_t>& p2) { return p1.second < p2.second; }
};

// Function to get most frequent used number in a Container
template <class Container>
auto topFrequent(const Container& data) {

    using Counter = std::unordered_map<Container::value_type, size_t>;
    using MaxHeap = std::priority_queue<std::pair<Container::value_type, size_t>, std::vector<std::pair<Container::value_type, size_t>>, LessForSecondOfPair<Container>>;

    // Count all occurences of data
    Counter counter{};
    for (const auto& d : data) counter[d]++;

    // Build a Max-Heap
    MaxHeap maxHeap(counter.begin(), counter.end());

    // Return most frequent number
    return maxHeap.top().first;
}
int main() {

    std::vector test{ 1,2,2,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6,6 };

    std::cout << "\n\nMost frequent used number is: " << topFrequent(test) << "\n\n";
    return 0;
}

As you can see, I use Container::value_type. And I use a range based for, which requires also certain properties.

So, I simply write "value_type" and assume that it exists, without knowing.

How can I check that this works?

I searched a little bit and found stacks of templates and specialized templates, but is there no easier way?

Or shall I do simply nothing and let the compilation fail? No idea . . .

I am still on C++17

Answer 1

Since the range-for is required, you need to test if begin() and end() are supported. Here top_frequent_support re-uses this trick.

Moreover, expecting the value type to be named as Container::value_type (by the way, your code misses typename) might be an unnecessary constraint. You can simply deduce this type from *begin(), in a using alias declaration (ValueType here) without expecting a specific name for this type. This makes your example work even with a simple C-like array.

The tests in main() show the same behaviour for a standard container and a C-like array, but a fallback for any unsuitable argument.

/**
  g++ -std=c++17 -o prog_cpp prog_cpp.cpp \
      -pedantic -Wall -Wextra -Wconversion -Wno-sign-conversion \
      -g -O0 -UNDEBUG -fsanitize=address,undefined
**/

#include <iostream>
#include <utility>
#include <unordered_map>
#include <queue>
#include <vector>

using std::begin; // fallback if not found via ADL
using std::end; // fallback if not found via ADL

template<typename Container>
using top_frequent_support =
  decltype((begin(std::declval<const Container &>())),
           (end(std::declval<const Container &>())),
           void(), 1);

// Predicate Functor
template<typename Container,
         top_frequent_support<Container> =1>
struct LessForSecondOfPair2 {
    using ValueType = std::decay_t<decltype(*begin(
                      std::declval<const Container &>()))>;
    bool operator () (const std::pair<ValueType, size_t>& p1,
                      const std::pair<ValueType, size_t>& p2)
    { return p1.second < p2.second; }
};

template<typename Container,
         top_frequent_support<Container> =1>
auto topFrequent2(const Container &data) {
    using ValueType = std::decay_t<decltype(*begin(data))>;
    using Counter = std::unordered_map<ValueType, size_t>;
    using MaxHeap = std::priority_queue<std::pair<ValueType, size_t>,
                                        std::vector<std::pair<ValueType, size_t>>,
                                        LessForSecondOfPair2<Container>>;

    // Count all occurences of data
    Counter counter{};
    for (const auto& d : data) counter[d]++;

    // Build a Max-Heap
    MaxHeap maxHeap(counter.begin(), counter.end());

    // Return most frequent number
    return maxHeap.top().first;
}

auto topFrequent2(...) {
  return "container is not suitable";
}

int main() {
    std::vector test{ 1,2,2,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6,6 };
    std::cout << "Most frequent used number is: " << topFrequent2(test) << "\n";
    double arr[]={1.1, 2.2, 2.2, 3.3, 3.3, 3.3};
    std::cout << "Most frequent used number is: " << topFrequent2(arr) << "\n";
    double value=12.34;
    std::cout << "Most frequent used number is: " << topFrequent2(value) << "\n";
    return 0;
}