function of generic container of specific specialization

Question

I'm trying to write an algorithm that should work with different containers (std::vector, QVector) containing the same type:

template<class Container>
boolean findpeaks(cv::Mat &m, Container<std::pair<int, double>> &peaks) {
    // do stuff
    peaks.push_back(std::make_pair(1, 1.0));

    return true;
}

This one gives me

'Container' is not a template

template<template<typename> class Container>

I get:

error: no matching function for call to 'findpeaks(cv::MatExpr, std::vector >&)'

...

note: template argument deduction/substitution failed:

error: wrong number of template arguments (2, should be 1)

Calling code:

cv::Mat m(data, true);
std::vector<std::pair<int, double>> peaks;

QVERIFY(daf::findpeaks(m.t(), peaks));

I've also tried something like this:

template<template< template<typename, typename> typename > class Container>

warning: ISO C++ forbids typename key in template template parameter; use -std=c++1z or -std=gnu++1z [-Wpedantic]

And some more errors...

Answer 1

std::vector has two template parameters.

template<  
    class T,
    class Allocator = std::allocator<T>
> class vector;

And QVector has one. You can do it with variadic template:

template<template <typename...> class Container>
bool findpeaks(cv::Mat &m, Container<std::pair<int, double>> &peaks) {
    // do stuff
    peaks.push_back(std::make_pair(1, 1.0));

    return true;
}

Answer 2

Do you actually need Container to be a class template? Just make it a normal type:

template<class Container>
boolean findpeaks(cv::Mat &m, Container& peaks) {
    // do stuff
    peaks.push_back(std::make_pair(1, 1.0));

    return true;
}

This will let you use other containers that are potentially not templates. Like, struct MySpecialPairContainer { ... };

Answer 3

You may do

template<template <typename ...> class Container>
bool findpeaks(cv::Mat &m, Container<std::pair<int, double>> &peaks) {
    // do stuff
    peaks.push_back(std::make_pair(1, 1.0));

    return true;
}

Your problem is that std::vector has 2 template parameters, the type T and an allocator.

But you can do even simpler:

template<typename Container>
bool findpeaks(cv::Mat& m, Container& peaks) {
    // do stuff
    peaks.push_back(std::make_pair(1, 1.0));

    return true;
}

Answer 4

In general, you shouldn't over specify. If I wrote:

struct my_thing {
  void push_back( std::pair<int, double> const& ) {}
};

shouldn't I be able to pass my_thing to your findpeaks?

There is absolutely no need for the template<class...>class Container template within the function, so requring it in the interface is an overspecification.

What you need is a sink (graph theoretical sink -- a sink is where things flow into, and don't flow out of) that consumes pairs of int, double. Ideally you want to be able to pass in a container without extra boilerplate.

template<class T>
struct sink:std::function<void(T)> {
  using std::function<T>::function;
  // more
};

now your function looks like:

bool findpeaks(cv::Mat &m, sink<std::pair<int, double>const&> peaks) {
  // do stuff
  peaks(std::make_pair(1, 1.0));

  return true;
}

and as a bonus, you can now put it into a cpp file instead of a header. (The dispatching costs for a std::function are modest).

This does require that you wrap the second parameter up at the call site:

std::vector<std::pair<int, double>> v;
if(findpeaks( matrix, [&](auto&& e){v.push_back(decltype(e)(e));} ) {
  // ...

which you might not like. Because we didn't use a naked std::function but instead a sink, we can get around this. First we write a metatrait, then some traits.

namespace details {
  template<template<class...>class Z, class alwaysvoid, class...Ts>
  struct can_apply:std::false_type{};
  template<template<class...>class Z, class...Ts>
  struct can_apply<Z, std::void_t<Z<Ts...>>, Ts...>:std::true_type{};
}
template<template<class...>class Z, class...Ts>
using can_apply=details::can_apply<Z, void, Ts...>;

This is a meta trait that lets us write other traits.

template<class C, class X>
using push_back_result = decltype( std::declval<C>().push_back( std::declval<X>() ) );

template<class C, class X>
using can_push_back = can_apply< push_back_result, C, X >;

now we have a trait can_push_back that is true_type if and only if you can push an X into the container C.

We now augment sink:

template<class T, class Base=std::function<void(T)>>
struct sink:Base {
  using Base::Base;
  template<class C,
    std::enable_if_t< can_push_back< C&, T >{}, int> =0
  >
  sink( C& c ):
    Base( [&](auto&& t){ c.push_back(decltype(t)(t)); } )
  {}
  sink()=default;
  sink(sink const&)=default;
  sink(sink &&)=default;
  sink& operator=(sink const&)=default;
  sink& operator=(sink &&)=default;
};

This newly augmented sink now can be passed a container that supports .push_back(T) and automatically writes a function that solves the problem for you.

std::vector<std::pair<int, double>> v;
if(findpeaks( matrix, v ) {
  // ...

That just works.

We can do the same for containers that support .insert(T), and after that we can use std::set<T> or even std::map<int, double> as a sink for your algorithm:

std::set<std::pair<int, double>> s;
if(findpeaks( matrix, s ) {
  // ...
std::map<int, double> m;
if(findpeaks( matrix, m ) {
  // ...

Finally, this also supports mocking. You can write a test-sink that helps unit-test your findpeaks algorithm directly.

I find the concept of sink used sufficiently often that having a sink type that supports these kind of things makes my code clearer, and reduces its dependency on any one kind of container.

Performance wise, the cost of the type erasure in std:function is modest. if you really need performance improvement, swapping sink<X> for sink<X, F> where F is a free parameter is possible, and writing make_sink that creates a sink where Base is a lambda, should work with near zero changes in the body of the code. But before you do that, you can work on higher level optimizations, like having the output into sink be processed in a streaming manner, or fed to an async queue, or the like.

Answer 5

Just as expressed with @Barry's answer, I don't think you need a template template parameter here.

However, you seem to have concern about expressing "a container that supports push_back with a pair of..."

I suggest you to express this constraint in a sfinae constraint expression instead. Even if your parameter is explicitly requiring std::pair to be in the first template parameter of a class, it doesn't mean it has a push_back function, and doesn't mean the supposedly existing push_back is taking a std::pair as parameter.

Arguments of a function is currently a bad way of expressing what a template type should be able to do, or should be. You'll have to wait for concepts for that.

In the meantime, you can use a sfinae constraint in your function signature that explicitly express that you need a type that has a member push_back function that accept a std::pair:

template<class Container>
auto findpeaks(cv::Mat &m, Container& peaks)
        // Using trailing return type
        -> first_t<bool, decltype(peaks.push_back(std::make_pair(1, 1.0)))>
        // Here's the constraint -^    that expression need to be valid
    {

    // do stuff
    peaks.push_back(std::make_pair(1, 1.0));

    return true;
}

first_t can be implemented that way:

template<typename T, typename...>
using first_t = T;

For the function to exist, the expression inside the decltype must be valid. If the contraint is not satified, the compiler will try other overloads of the function findpeaks.