C++ template meta-programming: find out if variadic type list contains value

user_10940989 0
Viewed 113

I'm trying to write a function that evaluates to true if a parameter passed at run-time is contained in a list of ints set up at compile-time. I tried adapting the print example here: https://www.geeksforgeeks.org/variadic-function-templates-c/#:~:text=Variadic%20templates%20are%20class%20or,help%20to%20overcome%20this%20issue.

And have tried this:

bool Contains(int j) { return false; }

template<int i, int... is>
bool Contains(int j) { return i == j || Contains<is...>(j); }

However, it gives me a compiler error saying "'Contains': no matching overloaded function found".

I've tried fiddling with angle-brackets but can't seem to get it to work.

variadic-templates c++
2 Answers

Your problem is that the recursive call is

Contains<is...>(j)

this looks for template overloads of Contains.

Your base case:

bool Contains(int j) { return false; }

is not a template. So the final call, when the pack is empty, of:

Contains<>(j)

cannot find the non-template.

There are a few easy fixes.

The best version requires a version of C++ greater than c++11; 17 I think:

template<int... is>
bool Contains(int j) { return ((is == j) || ...); }

This one is short, simple and clear.

The simple pre-c++14 ones generate O(n^2) total symbol length without jumping through extensive hoops. The c++17 one is O(n) total symbol length, much nicer. The c++14 one is obtuse, but also O(n) total symbol length.

So here are some c++11 ones that are suitable for modest lengths of packs:

None of the c++11 ones support empty packs:

template<class=void>
bool Contains(int j) { return false; }

template<int i, int... is>
bool Contains(int j) { return i == j || Contains<is...>(j); }

It relies on the fact that the first overload will never be selected except on an empty pack. (It is, due to a quirk in the standard, illegal to put any check that the pack is empty).

Another way that does not support empty packs is:

template<int i>
bool Contains(int j) { return i==j; }

template<int i0, int i1, int... is>
bool Contains(int j) { return Contains<i0>(j) || Contains<i1, is...>(j); }

which is more explicit than the first one.

The technique to get the total symbol length below O(n^2) involves doing a binary tree repacking of the parameter pack of integers. It is tricky and confusing, and I'd advise against it.

Live example.

Finally, here is a hacky one in c++14 that avoids the O(n^2) symbol length problem:

template<int...is>
bool Contains(int j) {
  using discard=int[];
  bool result = false;
  (void)discard{0,((void)(result = result || (is==j)),0)...};
  return result;
}

don't ask how it works. It is a technique that c++17 rendered obsolete on purpose.

user_17746670

You can achieve what you want with a fold expression (C++17):

template<int... is>
bool Contains(int j) { return ((is == j) || ...);

Called like so:

std::cout << std::boolalpha << Contains<1, 2, 3>(1) << "\n"; // true
std::cout << std::boolalpha << Contains<1, 2, 3>(4);         // false

Live Demo

user_276780
Related