C++概念,检查可变模板中没有重复的类型

huangapple go评论100阅读模式
英文:

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

问题

我正在尝试找出如何编写一个概念来检查可变模板中是否有重复类型。

我知道我不能在概念内部递归调用它自己,但如果可以的话,我的解决方案会看起来像这样(忽略停止条件的缺失):

``` c++
#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 {}

我还找不到标准库中的类型特性或概念来帮助我解决这个问题。有什么想法吗?


<details>
<summary>英文:</summary>

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

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

``` c++
#include &lt;concepts&gt;

template &lt;class TYPE, class ... TYPE_LIST&gt;
concept is_not_in_list = ((!std::same_as&lt;TYPE, TYPE_LIST&gt;) &amp;&amp; ...);

template &lt;class FIRST_TYPE_IN_LIST, class ... REST_OF_TYPE_LIST&gt;
concept is_non_repeating_list_ = (_type_not_in_list_&lt;FIRST_TYPE_IN_LIST, REST_OF_TYPE_LIST&gt; &amp;&amp; is_non_repeating_list&lt;REST_OF_TYPE_LIST&gt;);

// Usage

template&lt;is_non_repeating_list ... TYPE_LIST&gt;
class MyClass {}

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

答案1

得分: 1

template&lt;class T0, class...Ts&gt;
constexpr std::size_t type_count_in_list_v =
   (std::is_same_v&lt;T0, Ts&gt;+...);

template &lt;class...Ts&gt;
concept is_non_repeating_list_ =
  sizeof...(Ts) == (type_count_in_list_v&lt;Ts, Ts...&gt; + ...);

这种疯狂的结构可以解决你的递归问题。

但并不是特别有用,因为

template&lt;is_non_repeating_list ... TYPE_LIST&gt;
并不会像 `is_non_repeating_list&lt;TYPE_LIST...&gt;` 那样将 `TYPE_LIST` 传递给 `is_non_repeating_list`,而是像 `is_non_repeating_list&lt;TYPE_LIST&gt;...` 那样传递。

也就是说,每个 `is_non_repeating_list` 只会从你测试的 `TYPE_LIST` 中获取 *正好一个* 类型。

你可以这样做

template&lt;class...TYPE_LIST&gt; requires is_non_repeating_list&lt;TYPE_LIST...&gt;
英文:
template&lt;class T0, class...Ts&gt;
constexpr std::size_t type_count_in_list_v =
   (std::is_same_v&lt;T0, Ts&gt;+...);

template &lt;class...Ts&gt;
concept is_non_repeating_list_ =
  sizeof...(Ts) == (type_count_in_list_v&lt;Ts, Ts...&gt; + ...);

this sort of insane structure fixes your recursion problem.

But it doesn't help that much, because

template&lt;is_non_repeating_list ... TYPE_LIST&gt;

doesn't pass TYPE_LIST to is_non_repeating_list like is_non_repeating_list&lt;TYPE_LIST...&gt;, but rather like is_non_repeating_list&lt;TYPE_LIST&gt;....

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

You can do

template&lt;class...TYPE_LIST&gt; requires is_non_repeating_list&lt;TYPE_LIST...&gt;

however.

答案2

得分: 1

以下是翻译好的内容:

大多数尝试解决这个问题的方式在类型列表的长度上呈糟糕的扩展性——编译时间会呈二次或更糟的增长,而简单地遍历这个类型包而不使用折叠表达式会很容易呈立方增长。

这里有一种在编译时进行的方式,它仅在类型包长度上呈线性增长,假设std::make_index_sequence&lt;N&gt;N上最坏情况下是线性的:

#include &lt;utility&gt;

template&lt;typename T&gt; struct type_base {};
template&lt;int N, typename T&gt; struct indexed_type_base : type_base&lt;T&gt; {};
template&lt;typename Indexes, typename ...T&gt; struct indexed_types;
template&lt;std::size_t ...Indexes, typename ...T&gt;
struct indexed_types&lt;std::index_sequence&lt;Indexes...&gt;, T...&gt; : indexed_type_base&lt;Indexes, T&gt;... {};

template&lt;typename ...T&gt;
concept is_non_repeating_list =
    std::is_standard_layout_v&lt;indexed_types&lt;std::make_index_sequence&lt;sizeof...(T)&gt;, T...&gt;&gt;;

这里的技巧在于,indexed_types是一个标准布局的类类型,当且仅当它的所有基类都是不同的类型时才会发生,这仅在类型包不包含重复项时才会发生。索引序列和额外的基类层级仅用于避免indexed_types包含一个重复的直接基类,这将是不合法的。

英文:

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&lt;N&gt; is at worst linear in N:

#include &lt;utility&gt;

template&lt;typename T&gt; struct type_base {};
template&lt;int N, typename T&gt; struct indexed_type_base : type_base&lt;T&gt; {};
template&lt;typename Indexes, typename ...T&gt; struct indexed_types;
template&lt;std::size_t ...Indexes, typename ...T&gt;
struct indexed_types&lt;std::index_sequence&lt;Indexes...&gt;, T...&gt; : indexed_type_base&lt;Indexes, T&gt;... {};

template&lt;typename ...T&gt;
concept is_non_repeating_list =
    std::is_standard_layout_v&lt;indexed_types&lt;std::make_index_sequence&lt;sizeof...(T)&gt;, T...&gt;&gt;;

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.

答案3

得分: 1

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

这是在评论中提出的,附带了链接到另一个 Stack Overflow 帖子...

What I deem 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_unique = (are_types_unique_v<TYPE_LIST>);
英文:

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

https://stackoverflow.com/questions/18986560/check-variadic-templates-parameters-for-uniqueness/67106430#67106430

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&lt;typename T, typename... Types&gt;
constexpr bool are_types_unique_v = (!std::is_same_v&lt;T, Types&gt; &amp;&amp; ...) &amp;&amp; are_types_unique_v&lt;Types...&gt;;

template&lt;typename T&gt;
constexpr bool are_types_unique_v&lt;T&gt; = true;

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

template &lt;class TYPE_LIST&gt;
concept are_types_unqiue = (are_types_unique_v&lt;TYPE_LIST&gt;);

答案4

得分: 0

这似乎有效(在线演示):

英文:

This seems to work (live demo):

#include &lt;type_traits&gt;

// Check for a single matching type

template&lt;typename T,
	 typename ...Args&gt; struct does_not_repeat : std::true_type {};

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

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

template&lt;typename ...Args&gt; struct no_repeating_type : std::true_type {};

template&lt;typename T,
	 typename ...Args&gt;
struct no_repeating_type&lt;T, Args...&gt;
	: std::conditional_t&lt; does_not_repeat&lt;T, Args...&gt;::value &amp;&amp;
			    no_repeating_type&lt;Args...&gt;::value,
			    std::true_type, std::false_type&gt; {};

// Specialization to pull the parameters out of some template

template&lt;typename T&gt; struct no_repeated_params;

template&lt;template&lt;typename ...&gt; typename T,
	 typename ...Args&gt;
struct no_repeated_params&lt;T&lt;Args...&gt;&gt; : no_repeating_type&lt;Args...&gt; {};

// And make it a concept

template&lt;typename T&gt;
concept unique_template_parameters = no_repeated_params&lt;T&gt;::value;

// Let&#39;s test this

template&lt;unique_template_parameters  T&gt; void only_unique()
{
}

template&lt;typename ...&gt; struct sample {};

void testsuite()
{
	only_unique&lt;sample&lt;int&gt;&gt;();        // OK
	only_unique&lt;sample&lt;int, float&gt;&gt;(); // OK

	only_unique&lt;sample&lt;int, int&gt;&gt;();              // ERROR
	only_unique&lt;sample&lt;char, int, float, int&gt;&gt;(); // ERROR
}

答案5

得分: 0

这是一个使用折叠表达式的非递归实现:

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

template<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));

这包括了几个其他有用的实用程序,包括了在STL中缺失的type_list


<details>
<summary>英文:</summary>

Here&#39;s a none-recursive implementation using fold expressions:
```C++
template&lt;typename ... args&gt;
struct type_list{
    constexpr static std::size_t size()
    { return sizeof...(args); };
};

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

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

template&lt;typename ... args&gt;
constexpr std::size_t duplications =
count_list(type_list&lt;args...&gt;{}, type_list&lt;args...&gt;{});

template&lt;typename ... args&gt;
concept distinct = /*final untility:
total count of all types is the count of args,
or there&#39;s some duplications*/
(duplications&lt;args...&gt; == sizeof...(args));

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

答案6

得分: 0

不规范的方法是将每种类型转换为字符串,然后应用相应的算法来检查

#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();
}();
英文:

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

#include &lt;algorithm&gt;
#include &lt;string_view&gt;
#include &lt;vector&gt;

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

答案7

得分: 0

(1) 如何定义这个概念?

使用Boost.Mp11,这是一个简短的一行代码:

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

(2) 如何使用这个概念?

你之前写的是:

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

这意味着:

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

这不是你想要的,因为这个要求是平凡真的(每种类型本身当然是一个唯一的类型列表)。你需要手动编写这个概念:

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

这将实际上检查所有类型,而不是每个类型独立检查。

英文:

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 &lt;class... Ts&gt;
concept is_non_repeating_list = mp_is_set&lt;mp_list&lt;Ts...&gt;&gt;::value;

Basically, just use algorithms that already exist.

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

template &lt;is_non_repeating_list... Ts&gt; class MyClass {};

What this means is:

template &lt;class... Ts&gt;
    requires (is_non_repeating_list&lt;Ts&gt; &amp;&amp; ...)
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 &lt;class... Ts&gt;
    requires is_non_repeating_list&lt;Ts...&gt;
class MyClass {};

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

答案8

得分: 0

不依赖于类型特征、折叠表达式或递归的简单解决方案:

template
struct tag {};

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


这是因为所有直接基类必须具有不同的类型。时间复杂度取决于实现。

**编辑:并非所有编译器都能正常工作**,因为标准未明确 lambda 主体是否为直接上下文:https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103760
在不满足条件时,该概念可能会直接触发错误,而不是计算为 false。经过一些测试,似乎只在 MSVC 上有效。
英文:

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

template&lt;typename T&gt;
struct tag {};

template&lt;typename... Ts&gt;
concept are_unique = requires
{
	[](){
		struct A : tag&lt;Ts&gt;... {};
	}();
};

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.

huangapple
  • 本文由 发表于 2023年4月6日 20:01:39
  • 转载请务必保留本文链接:https://go.coder-hub.com/75949291.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定