C++ concept that checks there are no repeating types in a variadic template

Question

I'm trying to figure out how to write a conecpt that checks that there are no repeated types in a variadic template.

I'm aware I can't call a concept recursively within itself, but if I could my solution would look something like this (ignoring the lack of stop condition):

#include <concepts>

template <class TYPE, class ... TYPE_LIST>
concept is_not_in_list = ((!std::same_as<TYPE, TYPE_LIST>) && ...);

template <class FIRST_TYPE_IN_LIST, class ... REST_OF_TYPE_LIST>
concept is_non_repeating_list_ = (_type_not_in_list_<FIRST_TYPE_IN_LIST, REST_OF_TYPE_LIST> && is_non_repeating_list<REST_OF_TYPE_LIST>);

// Usage

template<is_non_repeating_list ... TYPE_LIST>
class MyClass {}

I can't find a type traits or concepts in the standard library to help me solve this yet. Any thoughts?

Queston

Here are some pre concepts solutions: #18987060 – Managing

From @Managing 's linked question I'd prefer this answer – and you could then build your concept around this non-concept standard template. – Unsustainable

@Unsustainable - Aha ofcourse, there's no reason to start off with unrecursable cencepts. Just trying it now, but any chance you want to post an answer based on that? If not I'll do it – Queston

Related question: #69236976 – Omnivore

Answer 1

This was pitched in a comment with a link to anotehr SO post...

check variadic templates parameters for uniqueness

What I deam the cleanest solution of the many I've read so far (thanks all for your suggestions!), is to use type traits to achieve the recursive part that I couldn't achieve directly with concepts like so:

template<typename T, typename... Types>
constexpr bool are_types_unique_v = (!std::is_same_v<T, Types> && ...) && are_types_unique_v<Types...>;

template<typename T>
constexpr bool are_types_unique_v<T> = true;

And then use that to define the now quite simple concept:

template <class TYPE_LIST>
concept are_types_unqiue = (are_types_unique_v<TYPE_LIST>);

Queston

Answer 2

Most ways you might try to address this problem scale poorly with the length of the list of types -- compile time will be quadratic or worse, and naively walking the pack rather than using a fold expression can easily be cubic in the length of the pack.

Here's one way to do it in compile time that grows only linearly in the pack length, assuming std::make_index_sequence<N> is at worst linear in N:

#include <utility>

template<typename T> struct type_base {};
template<int N, typename T> struct indexed_type_base : type_base<T> {};
template<typename Indexes, typename ...T> struct indexed_types;
template<std::size_t ...Indexes, typename ...T>
struct indexed_types<std::index_sequence<Indexes...>, T...> : indexed_type_base<Indexes, T>... {};

template<typename ...T>
concept is_non_repeating_list =
    std::is_standard_layout_v<indexed_types<std::make_index_sequence<sizeof...(T)>, T...>>;

The trick here is indexed_types is a standard-layout class type if and only if all of its base classes are of distinct types, which happens if and only if the pack of types contains no duplicates. The index sequence and extra layer of base classes is used only to avoid indexed_types containing a repeated direct base class, which would be ill-formed.

Intestate

Answer 3

template<class T0, class...Ts>
constexpr std::size_t type_count_in_list_v =
   (std::is_same_v<T0, Ts>+...);

template <class...Ts>
concept is_non_repeating_list_ =
  sizeof...(Ts) == (type_count_in_list_v<Ts, Ts...> + ...);

this sort of insane structure fixes your recursion problem.

But it doesn't help that much, because

template<is_non_repeating_list ... TYPE_LIST>

doesn't pass TYPE_LIST to is_non_repeating_list like is_non_repeating_list<TYPE_LIST...>, but rather like is_non_repeating_list<TYPE_LIST>....

Ie, each is_non_repeating_list gets exactly one type from your tested TYPE_LIST.

You can do

template<class...TYPE_LIST> requires is_non_repeating_list<TYPE_LIST...>

however.

Guttle

This is a very nice solution. The issue with it is the limitation you have highlighted. It's the cleanest solution pitched so far that sticks overcomes the recursion with concepts as I was trying to do in question. The answer I submitted (based on someone elses comment linking to another SO post) is the direction I chose to go in though. I forgot there are other ways to define the recursive body of the concept – Queston

Answer 4

A simple solution that doesn't rely on type traits, fold expressions or recursion:

template<typename T>
struct tag {};

template<typename... Ts>
concept are_unique = requires
{
    [](){
        struct A : tag<Ts>... {};
    }();
};

This works because all the direct bases must have different types. The time complexity depends on the implementation.

EDIT: This doesn't work correctly on all compilers because the standard doesn't clarify if a lambda body is immediate context or not: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103760 When unsatisfied, the concept may trigger an error directly instead of evaluating to false. After some testing, it seems to work only on msvc.

Russianize

Interesting solution. What does the compiler error look like if you try to use multiple of the same type in a template that uses are_unique? – Queston

@IronAttorney I've done some research, and apparently my solution doesn't work on all compilers because of this: gcc.gnu.org/bugzilla/show_bug.cgi?id=103760 I tested it and it only works on msvc – Russianize

Answer 5

This seems to work (live demo):

#include <type_traits>

// Check for a single matching type

template<typename T,
     typename ...Args> struct does_not_repeat : std::true_type {};

template<typename T, typename U, typename ...Args>
struct does_not_repeat<T, U, Args...> :
    std::conditional_t< !std::is_same_v<T, U> &&
              does_not_repeat<T, Args...>::value,
              std::true_type, std::false_type> {};

// Now, check each type to see if it matches any of the following types

template<typename ...Args> struct no_repeating_type : std::true_type {};

template<typename T,
     typename ...Args>
struct no_repeating_type<T, Args...>
    : std::conditional_t< does_not_repeat<T, Args...>::value &&
                no_repeating_type<Args...>::value,
                std::true_type, std::false_type> {};

// Specialization to pull the parameters out of some template

template<typename T> struct no_repeated_params;

template<template<typename ...> typename T,
     typename ...Args>
struct no_repeated_params<T<Args...>> : no_repeating_type<Args...> {};

// And make it a concept

template<typename T>
concept unique_template_parameters = no_repeated_params<T>::value;

// Let's test this

template<unique_template_parameters  T> void only_unique()
{
}

template<typename ...> struct sample {};

void testsuite()
{
    only_unique<sample<int>>();        // OK
    only_unique<sample<int, float>>(); // OK

    only_unique<sample<int, int>>();              // ERROR
    only_unique<sample<char, int, float, int>>(); // ERROR
}

Royston

Answer 6

Here's a none-recursive implementation using fold expressions:

template<typename ... args>
struct type_list{
    constexpr static std::size_t size()
    { return sizeof...(args); };
};

tempalte<typename candidate, typename ... args>
constexpr std::size_t count(const type_list<args...>)
{ return (static _cast<std::size_t>(std::same_as<candidate,args>) + ...); };

template<typename ... candidates, typename ... args>
constexpr std::size_t count_list(const type_list<args...> tl, const type_list<candidates...>)
{ return (count<candidates>(tl) + ...); };

template<typename ... args>
constexpr std::size_t duplications =
count_list(type_list<args...>{}, type_list<args...>{});

template<typename ... args>
concept distinct = /*final untility:
total count of all types is the count of args,
or there's some duplications*/
(duplications<args...> == sizeof...(args));

This includes several other useful utilities including type_list, which is missing from STL.

Outwear

Does the non-recusrive nature affect compilation speed do you think? – Queston

What else can we do to speed it up? Recursion exhausts system memory at compile-time, besides compile-time overhead. – Outwear

Answer 7

A non-standard way is to convert each type to a string, and then apply the corresponding algorithm to check

#include <algorithm>
#include <string_view>
#include <vector>

template<class... Types>
concept non_repeating_list = [] {
  std::vector<std::string_view> types{type_name<Types>()...};
  std::ranges::sort(types);
  return std::ranges::adjacent_find(types) == types.end();
}();

Trematode

Does comparing type_name treat aliases as unequal? That would be a problem for my use case if it does. – Queston

Also, converting the types to string sounds a bit overkill, types can already be compared without using the type name so this feels a little unessecary – Queston

Answer 8

There are actually questions here: (1) How do you define the concept? and (2) How do you use the concept?

For the definition, with Boost.Mp11, this is a short one-liner (as always):

template <class... Ts>
concept is_non_repeating_list = mp_is_set<mp_list<Ts...>>::value;

Basically, just use algorithms that already exist.

But the usage-side is also important. What you wrote was:

template <is_non_repeating_list... Ts> class MyClass {};

What this means is:

template <class... Ts>
    requires (is_non_repeating_list<Ts> && ...)
class MyClass {};

That's not what you want, since that requirement is trivially true (every type by itself is of course a unique list of types). You need to manually write out the concept:

template <class... Ts>
    requires is_non_repeating_list<Ts...>
class MyClass {};

That will now actually check all the types together, not each one independently.

Encephalomyelitis