How to detect index of a specific number in a std::integer_sequence?

user_14081791 0
Viewed 302

I basically drafted compile time prime checking using this question as a reference: Compile time prime checking

I have a IsPrime<3>::value available.

I want to design a find meta function that basically identifies if there is a prime in my integer sequence at compile time, if there is then returns the index else returns -1;

example

  • find<std::integer_sequence<4,6,8,3>>::value // 3

  • find<std::integer_sequence<4,6,8,27>>::value // -1

  • find<std::integer_sequence<4,6,8,3,5,27>>::value // 3(as index 3 is the first prime, we do not care about others)

I am unable to wrap my head around parameter pack, any good examples or proper solution with explanation would help a lot.

Thinking out loud something like below, but not able to wrap my head around, how to get the index and how to stop iterating once you find the first prime in the sequence

template<typename T... args>
struct find_prime{
   static constexpr int value = is_prime<args>::value ? increement++ : is_prime<...>::args; 
};

Sorry if this sounds like a dumb approach, unable to figure out how to iterate with index

sfinae c++
2 Answers

This can be done with a recursive template. Recursion terminates early when a prime is found.

// Base failure case: our list is empty (or the specialization below would match)
template <int, int...>
struct find_prime_impl {
    static constexpr int value = -1;
};

// Specialization for at least one item remaining.  If it's prime, the current
// index is assigned to value; otherwise we recurse with an incremented index,
// and without the first item.
template <int Index, int Head, int... Tail>
struct find_prime_impl<Index, Head, Tail...> {
    static constexpr int value = [] {
        if constexpr (is_prime<Head>::value) {
            return Index;
        } else {
            return find_prime_impl<Index + 1, Tail...>::value;
        }
    }();
};

// Calls the recursive template with the initial index 0.
template <int... Values>
struct find_prime : find_prime_impl<0, Values...> {};

The immediately-invoked lambda lets us use if constexpr which means that the compiler can skip instantiating the recursive use of find_prime_impl when the terminating case is met. The ternary operator does not "short-circuit" instantiation in this way and would still instantiate the entire recursive chain all the way down to find_prime_impl<Index>.

(Demo)

To directly use std::integer_sequence, tweak the implementation to expect it:

// Failure case when the type isn't std::integer_sequence
template <int, typename>
struct find_prime_impl {};

// Failure case when our list is empty (or the specialization below would match)
template <typename TInt, int Index>
struct find_prime_impl<Index, std::integer_sequence<TInt>> {
    static constexpr int value = -1;
};

// Specialization for at least one item remaining.  If it's prime, the current
// index is assigned to value; otherwise we recurse with an incremented index,
// and without the first item.
template <typename TInt, int Index, TInt Head, TInt... Tail>
struct find_prime_impl<Index, std::integer_sequence<TInt, Head, Tail...>> {
    static constexpr int value = [] {
        if constexpr (is_prime<Head>::value) {
            return Index;
        } else {
            return find_prime_impl<
                Index + 1,
                std::integer_sequence<TInt, Tail...>
            >::value;
        }
    }();
};

// Calls the recursive template with the initial index 0.
template <typename T>
struct find_prime : find_prime_impl<0, T> {};
user_5012500

Here is an example that works with significantly less code:

template <int ...Ints>
constexpr int find_prime() {
    constexpr auto res = fp<Ints...>(std::make_index_sequence<sizeof...(Ints)>{}); 
    return (res == sizeof...(Ints)) ? -1 : res;
}

template <int ...Ints, auto ...Indices>
constexpr int fp(std::index_sequence<Indices...>) {
    return std::min({ (is_prime(Ints) ? Indices : sizeof...(Indices))... });
}

The idea is to bind each number to its index in the list and just return the smallest index from the list that is a prime. If all entries in the list of indices are the length of the list itself, the program shall return -1.

user_77035640
Related