Home > Back-end >  C template meta-programming: find out if variadic type list contains value
C template meta-programming: find out if variadic type list contains value

Time:04-09

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 templates are class or,help to overcome this issue.

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.

CodePudding user response:

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 ; 17 I think:

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

This one is short, simple and clear.

The simple pre- ones generate O(n^2) total symbol length without jumping through extensive hoops. The one is O(n) total symbol length, much nicer.

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

None of the 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 that avoids the O(n^2) symbol length.

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

don't ask.

CodePudding user response:

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

  • Related