Finding the position of the first occurrence of a value in an std::integer_sequence

Question

I want to find the position of the first occurrence of a value in an std::integer_sequence.

1. Is there an algorithm in the standard library for this task?
2. If not, what would be a good way to do it?

--

Below is my attempt. It works, but I don't find it very elegant; also it fails to produce a clean error ("value not found") when the value is not present (code commented out due to compilation). (Also, having to specify the integer type in Find_in_integer_sequence feels redundant, but I suppose there is no way around it.)

The code is there just for your amusement, it is not supposed to be a starting point for a proposed solution.

# include <iostream>
# include <utility>
# include <type_traits>

namespace detail
{
  template < int Idx, typename T, T Match, T ...Values >
  struct Find;

  template < int Idx, bool B, typename T, T Match, T ...Values >
  struct Find_impl;

  template < int Idx, typename T, T Match, T ...Values >
  struct Find_impl<Idx, true, T, Match, Values...>
  {
    static const int value = Idx;
  };

  template < int Idx, typename T, T Match, T Value, T ...Other_values >
  struct Find_impl<Idx, false, T, Match, Value, Other_values...>
    : public Find<(Idx + 1), T, Match, Other_values...>
  {
  };

  template < int Idx, typename T, T Match, T Value, T ...Other_values >
  struct Find<Idx, T, Match, Value, Other_values...>
    : public Find_impl<Idx, (Match == Value), T, Match, Value, Other_values...>
  {
  };

  //template < int Idx, typename T, T Match >
  //struct Find<Idx, T, Match>
  //{
  //  static_assert(false, "value not found");
  //};
}

template < typename T, T Match, T ...Values >
struct Find
  : public detail::Find<0, T, Match, Values...>
{
};

template < typename T, T Match, typename TIS >
struct Find_in_integer_sequence;

template < typename T, T Match, T ...Values>
struct Find_in_integer_sequence<T, Match, std::integer_sequence<T, Values...>>
  : public Find<T, Match, Values...>
{
};

int main()
{
  using i1 = std::integer_sequence<int, 2, 3, 3, 2, 3, 2, 0>;
  auto k = Find_in_integer_sequence<int, 0, i1>::value;
  std::cout << k << std::endl; # prints "6"
  return 0;
}

Answer 1

C++14 constexpr is awesome:

template<  class U, class T, T...ts >
constexpr std::size_t find( U t, std::integer_sequence<T, ts...> s )
{
    T s_arr[] = {ts...};
    for (std::size_t i = 0; i != sizeof...(ts); ++i) {
        if (s_arr[i] == t) return i;
    }
    return sizeof...(ts);
}

just search. Linearly.

---

This is a far more complex solution involving building binary trees with logarithmic depth. It is based on what you have to do to do this with types, which cannot be stored in flat arrays in constexpr functions. This version could be modified to work in C++11 with a lot of work:

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

template<class T, T...t0s, T...t1s>
constexpr std::integer_sequence<T, t0s..., t1s... >
join( std::integer_sequence<T,t0s...>, std::integer_sequence<T,t1s...>){
  return {};
}
template<class T, T...ts>
constexpr auto split( index<0>, std::integer_sequence<T,ts...> s ){
  return std::make_pair( std::integer_sequence<T>{}, s );
}
template<class T, T t0,  T...ts>
constexpr auto split( index<1>, std::integer_sequence<T, t0, ts...> s ){
  return std::make_pair( std::integer_sequence<T, t0>{}, std::integer_sequence<T,ts...>{} );
}

template<std::size_t N, class T, T...ts>
constexpr auto split( index<N>, std::integer_sequence<T, ts...> s ){
  auto a = split(index<N/2>{}, s );
  auto b = split(index<(N+1)/2>{}, a.second );
  return std::make_pair( join(a.first, b.first), b.second );
}
template< class T, T t0, T t1 >
constexpr index<1> find( std::integral_constant<T,t0>, std::integer_sequence<T, t1> )
{ return {}; }

template< class T, T t0, T...ts >
constexpr index<0> find( std::integral_constant<T,t0>, std::integer_sequence<T, t0, ts...> )
{ return {}; }
template< class T, T t0, T...ts >
constexpr index<1> find( std::integral_constant<T,t0>, std::integer_sequence<T> )
{ return {}; }
template< class T, T t0, T...ts >
constexpr auto find( std::integral_constant<T,t0> t, std::integer_sequence<T, ts...> s )
{
  index<sizeof...(ts)/2> half;
  auto halves = split( half, s );
  auto front = find( t, halves.first );
  auto back = find( t, halves.second );
  return index<(front < half)?front:(back+half)>{};
}

This solves the problem with logarithmic recursion depth, allowing searching million-entry lists of integers.

Live example of both.

Answer 2

Another way is with constexpr functions:

#include <iostream>
#include <utility>
#include <type_traits>

template<class T>
constexpr int find_(std::integer_sequence<T>, T, int Idx) {
    return Idx;
}

template<class T, T Head, T... Tail>
constexpr int find_(std::integer_sequence<T, Head, Tail...>, T Value, int Idx) {
    return Value == Head ? Idx : find_(std::integer_sequence<T, Tail...>{}, Value, Idx + 1);
}

template<class S, class T>
constexpr auto findT(S s, T Value) {
    return find_(s, Value, 0);
}

int main() {
    using i1 = std::integer_sequence<int, 2, 3, 3, 2, 3, 2, 0>;
    constexpr auto k = findT(i1{}, 0);
    static_assert(k == 6, "Compile time constant check.");
    std::cout << k << std::endl; // prints "6"
}