Can Someone Please Explain the "Indices Trick"

Can someone please explain the indices trick ?

The problem is: we have a std::tuple<T1, T2, ...> and we have some function f that we can to call on each element, where f returns an int, and we want to store those results in an array.

Let's start with a concrete case:

template <typename T> int f(T ) { return sizeof(T); }

std::tuple<int, char, double> tup{42, 'x', 3.14};
std::array<int, 3> arr{ f(std::get<0>(tup)), 
                        f(std::get<1>(tup)),
                        f(std::get<2>(tup)) );

Except writing out all those gets is inconvenient and redundant at best, error-prone at worst.

First we need to include the utility header for std::index_sequence and std::make_index_sequence:

#include <utility>

Now, let's say we had a type index_sequence<0, 1, 2>. We could use that to collapse that array initialization into a variadic pack expansion:

template <typename Tuple, size_t... Indices>
std::array<int, sizeof...(Indices)> 
call_f_detail(Tuple& tuple, std::index_sequence<Indices...> ) {
    return { f(std::get<Indices>(tuple))... };
}

That's because within the function, f(std::get<Indices>(tuple))... gets expanded to f(std::get<0>(tuple)), f(std::get<1>(tuple)), f(std::get<2>(tuple)). Which is exactly what we want.

The last detail of the problem is just generating that particular index sequence. C++14 actually gives us such a utility named make_index_sequence

template <typename Tuple>
std::array<int, std::tuple_size<Tuple>::value>
call_f(Tuple& tuple) {
    return call_f_detail(tuple,
        // make the sequence type sequence<0, 1, 2, ..., N-1>
        std::make_index_sequence<std::tuple_size<Tuple>::value>{}
        );
}

whereas the article you linked simply explains how one might implement such a metafunction.

Bare is probably something like, from Luc Danton's answer:

template<typename T>
using Bare = typename std::remove_cv<typename std::remove_reference<T>::type>::type;

multidimensional array initialization using indices trick

This can be made a lot easier by changing the code to access the array, not the indices generation. What you basically want is a 1D to 2D access mapping.

Normally, people need it the other way around (2D to 1D), when they implement a 2D array in terms of a 1D array^†:

template<class T, unsigned M, unsigned N>
struct md_array{
  T elems[M * N]; // same layout as 'T elems[M][N];'
};

The formula to get the 1D index i from the 2D index (x,y) is then i == x * N + y. We can explain this if we imagine our 1D elems from above as a 2D array (using M == 2 and N == 3):

 0, 1, 2, 3, 4, 5 // indices (i)
[a, b, c, d, e, f]
v // we want them as M (2) packs of N (3) elements
 0, 1, 2   0, 1, 2 // element indices (y)
[a, b, c] [d, e, f]
\___0___/ \___1___/ // pack indices (x)
v // fusing the packs back together, we can see that we have
  // a constant offset for the packs, which is the N (3) times x
0*3+0, 0*3+1, 0*3+2, 1*3+0, 1*3+1, 1*3+2
[ a,     b,     c,     d,     e,     f ]

Thus, we get i == x * N + y. We now need to solve this formula not for i but for x and y. For x, it's rather easy (using math notation):

i = x * N + y | -y
i - y = x * N | *(1/N)
i - y
----- = x
  N

So x == (i - y) / N. Now, sadly, I don't know how to solve this for y using pure math, but we don't need that. Taking a look at the element indices, we can see that they wrap around N, and that can easily be done using the modulo operator. Thus, y == i % N.

Now we can implement a method that takes a linear index i and returns the element at the solved (x, y) from that:

template<unsigned I>
T& get(){ constexpr auto y = I % 3; return array[(I-y)/3][y]; }

and generalizing that:

template<unsigned I>
T& get(){ constexpr auto y = I % N, x = (I-y)/N; return array[x][y]; }

Using constexpr to ensure that all the computation is done at compile-time.
Now you can simply write assign as follows:

template<unsigned... Is, class... U>
void assign(indices<Is...>, U... args)
{
  [](...){}((get<Is>() = args)...);
}

Q.E.D. (Live example.)

---

† Now, you can make this easier on yourself by actually implementing the 2D array as a 1D array. :) This way, you can straight-forwardly use (array[Is] = args)... and for the other cases use a simple access function that does the mapping:

T& get(unsigned x, unsigned y){ return array[x * N + y]; }

Live example.

How do I get index of elements in parameter pack

It seems to me (if you can use at least C++14) a work for a delegating constructor

template <typename ... Ts>
class ClassA
 {
   private:
      template <std::size_t ... Is>
      ClassA (std::index_sequence<Is...> const &, Ts ... ts)
         : tup { std::make_tuple(ts, Is) ... }
       { }

   public:
      ClassA (Ts ... ts)
         : ClassA(std::make_index_sequence<sizeof...(Ts)>{}, ts...)
       { }

      std::tuple<std::tuple<Ts, std::size_t>...> tup;
 };

In C++11 this doesn't works because std::index_sequence and std::make_index_sequence are available only starting from C++14 but it isn't difficult to find (or develop) C++11 substitutes.

In numpy, how to create an array of the indices of the elements in a source array as they are found in a destination array?

Here is what I believe is the "direct" way:

# find order of src and dst
so = src.ravel().argsort()
do = dst.ravel().argsort()
# allocate combined map
tot = np.empty_like(src)

# next line is all you need to remember
tot.ravel()[so] = do

# go back to 2D indexing
indices = np.unravel_index(tot,dst.shape)

# check
dst[indices]
# array([[8, 1],
#        [2, 4]])

indices
# (array([[1, 0],
#         [1, 0]]), array([[0, 0],
#         [1, 1]]))

---

Related Topics