特定专业化的通用容器的功能

Question

我正在尝试编写一种算法，该算法应该适用于包含相同类型的不同容器（std::vector、QVector）：

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;
}

这个给了我

'Container' is not a template

template<template<typename> class Container>

我得到：

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)

调用代码：

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

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

我也试过这样的方法：

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]

还有一些错误...

Answer 1

你可以

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;
}

你的问题是 std::vector 有 2 个模板参数，类型 T 和一个分配器。

但你可以做得更简单：

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

    return true;
}

Answer 2

std::vector 有两个模板参数。

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

而 QVector 有一个。你可以用 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 3

您真的需要 Container 才能成为 class 模板吗？只需将其设为普通类型即可：

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

    return true;
}

这样您就可以使用其他可能不是模板的容器。比如，struct MySpecialPairContainer { ... };

Answer 4

一般来说，您不应该过度指定。如果我写：

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

难道我不能把 my_thing 传给你的 findpeaks 吗？

函数中绝对不需要 template<class...>class Container 模板，因此在界面中要求它是一种过度规范。

您需要的是消耗成对 int, double 的汇（图论汇 -- 汇是事物流入而不流出的地方）。理想情况下，您希望能够在没有额外样板的情况下传入容器。

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

现在你的函数看起来像：

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

  return true;
}

作为奖励，您现在可以将其放入 cpp 文件而不是 header。（std::function 的调度成本适中）。

这确实需要您在调用站点包装第二个参数：

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

你可能不喜欢。因为我们没有使用裸 std::function 而是 sink，所以我们可以解决这个问题。首先我们写一个元特征，然后是一些特征。

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...>;

这是一个元特征，可以让我们编写其他特征。

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 >;

现在我们有一个特征 can_push_back，即 true_type 当且仅当您可以将 X 推入容器 C。

我们现在增加接收器：

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;
};

这个新扩充的sink现在可以传一个支持.push_back(T)的容器，自动写一个函数给你解决问题

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

这很管用。

我们可以对支持 .insert(T) 的容器做同样的事情，然后我们可以使用 std::set<T> 甚至 std::map<int, double> 作为算法的接收器：

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

最后，这也支持模拟。您可以编写 test-sink 直接帮助 unit-test 您的 findpeaks 算法。

我发现 sink 的概念经常被使用，拥有支持这些东西的 sink 类型使我的代码更清晰，并减少它对任何一种容器的依赖。

在性能方面，std:function 中类型擦除的成本适中。如果您真的需要性能改进，可以将 sink<X> 换成 sink<X, F>，其中 F 是一个自由参数，并编写 make_sink 创建一个 sink，其中 Base 是一个 lambda，应该在代码的 body 几乎为零的变化下工作。但在你这样做之前，你可以进行更高级别的优化，比如以流方式处理 sink 的输出，或者提供给异步 queue，等等。

Answer 5

正如@Barry 的回答所表达的那样，我认为您在这里不需要模板模板参数。

但是，您似乎对表达有顾虑"a container that supports push_back with a pair of..."

我建议您改为在 sfinae 约束表达式中表达此约束。即使您的参数明确要求 std::pair 在 class 的第一个模板参数中，也不意味着它具有 push_back 功能，也不意味着假定存在push_back 将 std::pair 作为参数。

函数的参数目前是表达模板类型应该能够做什么或应该做什么的糟糕方式。你将不得不等待它的概念。

与此同时，您可以在函数签名中使用 sfinae 约束，明确表示您需要一个类型，该类型的成员 push_back 函数接受 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可以这样实现：

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

要使函数存在，decltype 中的表达式必须有效。如果不满足约束，编译器将尝试函数的其他重载 findpeaks.

特定专业化的通用容器的功能

function of generic container of specific specialization

c++

templates

vector

generic-programming

c++11