All geek questions in one place

Implement STL functions in a variation pattern

I am working on a small project to speed up with variable templates. I implemented a small multidimensional array. Now I would like to define a function that works with the nearest neighbors of a given position - is there an elegant way to get the values ​​of the neighbors of a given position in my array?

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

};

Addition: It is somewhat clear to me how to loop all the elements using recursion, for example. applying an arbitrary function to a hyperdym. array of ints:

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

I am curious how I would generate something like func(arr[i+1,j,k,…],arr[i-1,j,k,…],arr[i,j+1,k,…],arr[i,j-1,k,…],…)and given func (which, for example, adds the appropriate elements). As I said, it’s completely new for variable templates, and I have the feeling that I don’t have the right mindset yet ...

+4
3

- ( ++ 17, ++ 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...));
}

, :

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

+4

, MArr, :

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

:

  • 0 2 * D * D - 1 ( D - ).
  • , 1D x + 1, y, z, x - 1, y, z,..., x, y, z + 1, x, y, z - 1.
  • 2 * D D (size_t [2 * D][D]).
  • .

:

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- , , ++ ( ).
  • clang -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
+2

.

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

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

( , 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()];
}

Once we do, your problem will become easier.

First we rewrite yours functo repeat the values index. This can be done the way you did it when you go through the callback, or you can implement nextthat promotes the index.

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

now the iteration might look like this:

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

which is cleaner, simpler and more efficient than your version (no type erasure).

The closest neighbor can be easily written in terms 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]--; }
  }
}
+1
source

Source: https://habr.com/ru/post/1691300/

More articles:


All Articles