在可变参数模板中实现STL函数

问题描述 投票：4回答：3

我一直致力于一个小型项目，以加快可变参数模板的速度。我实现了一个小的多维数组。我现在想定义一个对给定位置的最近邻居进行操作的函数 - 是否有一种优雅的方法来检索数组中给定位置的邻居值？

template<class T, size_t size, size_t... sizes>
struct MArr {
    typedef std::array<typename MArr<T, sizes...>::type, size> type;

    std::array<MArr<T, sizes...>,size> data;

    MArr<T, sizes...>& operator[](int i) {
        return data[i];
    }

};

template<class T, size_t size>
struct MArr<T, size> {
    typedef std::array<T, size> type;
    type data;

    T& operator[](int i) {
       return data[i];
    }

};

附录：我有点清楚如何通过使用递归来循环所有元素，例如：将任意函数应用于hyperdim。整数数组：

template <typename T, size_t size>
void func(MArr<T, size>& arr, std::function<void(int &)> f) {
    for (int i = 0; i < size; i++) {
       f(arr[i]);
    }
}


template <typename T, size_t size0, size_t size1, size_t ...sizes>
void func(MArr<T, size0, size1, sizes...>& arr, std::function<void(int &)> f) {
    for (int i =0; i < size0; i++) {
        func<T, size1, sizes...>(arr[i], f);
    }
}

我很好奇我将如何生成类似func(arr[i+1,j,k,…],arr[i-1,j,k,…],arr[i,j+1,k,…],arr[i,j-1,k,…],…)和给定func的东西（例如，添加相应的元素）。正如我所说的，对于可变参数模板来说还是一个新手，我感觉我还没有正确的心态......

c++ templates metaprogramming variadic-templates variadic-functions
3个回答
4
投票

您可以执行类似的操作（代码使用C ++ 17中的折叠表达式，但可以使用C ++ 11编写）：

template <std::size_t I, typename F, std::size_t ... Is, typename Tuple>
void helper(F&& f, std::index_sequence<Is...>, const Tuple& t)
{
    f((std::get<Is>(t) - (Is == I))...);
    f((std::get<Is>(t) + (Is == I))...);
}

template <typename F, std::size_t ... Is, typename Tuple>
void helper(F&& f, std::index_sequence<Is...> Seq, const Tuple& t)
{
    (helper<Is>(std::forward<F>(f), Seq, t), ...);
}

template <typename F, typename ... Ts>
void apply_to_neighboor(F&& f, Ts... indexes)
{
    helper(std::forward<F>(f), std::index_sequence_for<Ts...>(), std::tie(indexes...));
}

Demo

如果要检索所有邻居，可以将以上代码更改为：

template <std::size_t I, std::size_t ... Is, typename Tuple>
auto helper1(std::index_sequence<Is...>, const Tuple& t)
{
    return std::make_pair(std::make_tuple((std::get<Is>(t) - (Is == I))...),
                          std::make_tuple((std::get<Is>(t) + (Is == I))...));
}

template <std::size_t ... Is, typename Tuple>
auto helper(std::index_sequence<Is...> Seq, const Tuple& t)
{
    return std::tuple_cat(helper1<Is>(Seq, t)...);
}

template <typename F, typename ... Ts>
void apply_to_neighboor(F&& f, Ts... indexes)
{
    std::apply(std::forward<F>(f),
               helper(std::index_sequence_for<Ts...>(), std::tie(indexes...)));
}

Demo

2
投票

这是一个可能的实现，依赖于您的MArr提供自定义下标运算符：

// Subscript using an array of size_t
T operator[](const size_t (&idx)[sizeof... (sizes) + 1]) const;

这个想法如下：

  1. 您生成一个从0到2 * D * D - 1的序列（其中D是维数）。
  2. 使用此序列，您可以生成单个1D阵列中的所有索引x + 1，y，z，x - 1，y，z，...，x，y，z + 1，x，y，z - 1。
  3. 你将这个巨大的数组视为2 * D值的D数组（size_t [2 * D][D]）。
  4. 您可以使用此数组使用新定义的下标运算符来索引多维数组。

这将是实施：

template <class T, std::size_t... Sizes, class F, class... Is,
          std::size_t... IsP2N, std::size_t... IsP2NN>
auto around_impl(MArr<T, Sizes...> const& arr,
                 std::index_sequence<IsP2N...>,
                 std::index_sequence<IsP2NN...>,
                 F &&f, Is&&... pt) {
    const std::size_t pts[] = {(std::size_t)pt... };
    const std::size_t pts2[2 * sizeof...(Sizes)][sizeof...(Sizes)] = {
        (pts[IsP2NN % sizeof...(Sizes)] 
         + (1 - 2 * ((IsP2NN / sizeof...(Sizes)) % 2)) 
            * (IsP2NN % sizeof...(Sizes) == IsP2NN / (2 * sizeof...(Sizes))))...

    };
    return f(arr[pts2[IsP2N]]... );
}

template <class T, std::size_t... Sizes, class F, class... Is>
auto around(MArr<T, Sizes...> const& arr, F &&f, Is&&... pt) {
    return around_impl(arr,
                       std::make_index_sequence<2 * sizeof...(Sizes)>{},
                       std::make_index_sequence<2 * sizeof...(Sizes) * sizeof...(Sizes)>{},
                       std::forward<F>(f),
                       std::forward<Is>(pt)... );
}

关于实施的小说明：

  • 括号内的计算在本答案的最后解释。
  • 从单个括号括起的列表中初始化2D数组是有效的C ++（据我所知）。
  • 其中大部分都是通过与-O3铿锵进行的。

然后你可以打电话：

// 3D array
MArr<int, 4, 4, 4> arr;

// Function to call:
auto myFun = [](int a, int b, int c, int d, int e, int f) { 
    return a + b + c + d + e + f;
};

// Call around:
around(arr, myFun, x, y, z);

致电：

myFun(arr[x + 1, y, z], arr[x - 1, y, z], 
      arr[x, y + 1, z], arr[x, y - 1, z],
      arr[x, y, z + 1], arr[x, y, z - 1]);

说明：

(pts[IsP2NN % sizeof...(Sizes)] 
 + (1 - 2 * ((IsP2NN / sizeof...(Sizes)) % 2)) 
    * (IsP2NN % sizeof...(Sizes) == IsP2NN / (2 * sizeof...(Sizes))))...
  • IsP2NN从0到2 * D * D - 1。
  • pts[...]对应x，y，z，x，y，z，......等等。
  • 1 - ...部分生成1，1，1，-1，-1，-1，1，1，1，-1，-1，-1等等......它在1和-1的序列之间交替。
  • 当尺寸不匹配时，* (...)将使之前的序列无效，它会生成1，0，0，1，0，0，0，1，0，0，1，0等等......

以下是发生情况的“矩阵”视图：

Is          0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17

Is % 3      0   1   2   0   1   2   0   1   2   0   1   2   0   1   2   0   1   2
Is / 3 % 2  0   0   0   1   1   1   0   0   0   1   1   1   0   0   0   1   1   1
Is / 6      0   0   0   0   0   0   1   1   1   1   1   1   2   2   2   2   2   2

pts  --     x   y   z   x   y   z   x   y   z   x   y   z   x   y   z   x   y   z
     --     1   0   0  -1   0   0   0   1   0   0  -1   0   0   0   1   0   0  -1
     --     1   0   0   1   0   0   0   1   0   0   1   0   0   0   1   0   0   1
---------------------------------------------------------------------------------
          x+1   y   z x-1   y   z   x y+1   z   x y-1   z   x   y z+1   x   y z-1
1
投票

首先，我创建一个索引类型。

template<std::size_t N>
using index=std::array<std::size_t, N>;

template<class T, size_t size, size_t... sizes>
struct MArr {
  using my_index=index<sizeof...(sizes)+1>;

和索引引用。要么使用gsl::span，要么自己编写：

namespace utility {
  template<class It>
  struct range {
    It b,e;
    It begin()const{return b;}
    It end()const{return e;}
    std::size_t size()const{return std::distance(begin(),end());}
    bool empty()const{return begin()==end();}

    using reference=typename std::iterator_traits<It>::reference;

    reference front()const{return *begin();}
    reference back()const{return *std::prev(end());}
  };
  template<class T>
  struct span:range<T*> {
    span(T* s, T*f):range<T*>{s,f}{}
    span():span(nullptr,nullptr){}
    span(T*s,std::size_t len):span(s,s+len){}
    T&operator[](std::size_t i)const{return this->begin()[i];}
    T* data()const{return this->begin();}
    span without_front(std::size_t n=1)const{ return {this->begin()+(std::min)(n,this->size()), end()}; }
    span without_back(std::size_t n=1)const{ return {this->begin(), end()-(std::min)(n,this->size())}; }
    span only_front(std::size_t n=1)const{ return {this->begin(),this->begin()+(std::min)(n,this->size())}; }
    span only_back(std::size_t n=1)const{ return {end()-(std::min)(n,this->size()),end()}; }
    span mid(std::size_t start, std::size_t len)const{ return without_front(start).only_front(len); }

    template< class U >
    using compatible=std::integral_constant<bool, std::is_convertible<U*,T*>{}&&(sizeof(U)==sizeof(T))>;
    template<class R>
    using compatible_range=compatible< std::decay_t<decltype( *std::declval<R>().data() )> >;
    template<class C,
      std::enable_if_t< compatible_range< C& >, bool> =true, // has .data() that returns good type
      std::enable_if_t< !std::is_same<span, std::decay_t<C>>{}, bool> =true // not own type
    >
    span(C&& c): span( c.data(), c.size() ){}
    template<std::size_t N>
    span( T(&arr)[N] ):span(arr, N){}
    // etc
  };
}

一旦你有了span（如上所述，或者来自gsl），代码变得更加清晰：

template<std::size_t N>
using index=std::array<std::size_t, N>;

using index_cref=utility::span<std::size_t const>;
using index_ref=utility::span<std::size_t>;

template<class T, size_t size, size_t... sizes>
struct MArr {
  using my_index=index<sizeof...(sizes)+1>;
  T& operator[]( index_cref r ){ return data[r.front()][ r.without_front() ]; }

在一个昏暗的情况下

T& operator[](index_cref r) {
   return data[r.front()];
}

一旦我们这样做了，你的问题就变得容易了。

首先，我们重写你的func来迭代index的值。这可以通过您执行此操作的方式完成，您可以在其中传递回调，或者您可以实现推进索引的next。

bool next_index( index_ref r, index_cref bounds ){
  if (r.empty()||bounds.empty()) return false;
  ++r.back();
  if (r.back()!=bounds.back()) return true;
  r.back()=0;
  return next_index( r.without_back(), bounds.without_back() );
}

现在迭代可以看起来像这样：

template<class MArr, class F>
void foreach_index( MArr const&, F&& f ){
  using index=typename MArr::index;
  index const bounds = MArr::bounds(); // todo: write
  index cur = {{0}};
  do {
    f(cur);
  } while( next_index(cur, bounds) );
}

这比你的版本更清晰，更简单，更高效（没有类型擦除）。

最近的邻居可以很容易地用index_ref来写。

template<class F>
void foreach_neighbour( index_ref where, index_cref bounds, F&& f ){
  for(std::size_t i=0; i<(std::min)(where.size(),bounds.size());++i){
    if (where[i]){ where[i]--; f(where); where[i]++; }
    if (where[i]+1<bounds[i]) { where[i]++; f(where); where[i]--; }
  }
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.