N4144, Searching and Manipulation of Parameter Packs

Doc No:	N4144
Date:	2014-09-11
Reply to:	`stdbill.h@pobox.com`

Searching and Manipulation of Parameter Packs

Bill Seymour
Stephan T. Lavavej
2014-09-11

Abstract:

This paper proposes that mechanisms for finding types in parameter packs, and for adding and removing types to/from parameter packs, be added to the standard library.

Revision history:

This paper is a revision of N4115 which proposed only the packer, is_contained_in and contains_types class templates along with the is_contained_in_v and contains_types_v value templates.

The basic idea:

This paper proposes seven new class templates, two new value templates, and four new template aliases for <type_traits>.

packer is a variadic class template the only purpose of which is to hold a parameter pack.
is_contained_in and contains_types compile to either true_type or false_type to report whether a parameter pack contains one or more types.
add_to and unique_add_to add zero or more types to a parameter pack.
remove_from removes zero or more types from a parameter pack.
uniqueify removes duplicate types from a parameter pack.

Some of the proposed standardese remains to be written.

As proof of concept, possible implementations (not necessarily the best) of the various class templates are shown; and Appendix A contains a listing for a crude test program that displays the results of instantiation on the standard output.

A class template that just holds a parameter pack:

    template <class... Args> struct packer { };

This is inspired by std::tuple, but it has no members, so it could serve as an empty base class, and an object of the ultimate type could always be instantiated (even if the parameter pack contains void or some type that lacks a default constructor).

Whether type T is in parameter pack P:

    template <class T, class... P> struct is_contained_in;

    template <class T, class... P>
      constexpr bool is_contained_in_v = is_contained_in<T,P...>::value;

One possible implementation:

    template <class T> struct is_contained_in<T> : false_type { };

    template <class First, class... Rest>
      struct is_contained_in<First, First, Rest...> : true_type { };

    template <class T, class First, class... Rest>
      struct is_contained_in<T, First, Rest...>
        : is_contained_in<T, Rest...> { };

Whether a `packer`, T, has a parameter pack that’s a superset of the pack of some minimum `packer`, U:

    template <class T, class U> struct contains_types;

    template <class T, class U>
      constexpr bool contains_types_v = contains_types<T,U>::value;

One possible implementation:

    template <class... TPack>
      struct contains_types<packer<TPack...>, packer<>> : true_type { };

    template <class... TPack, class UFirst, class... URest>
      struct contains_types<packer<TPack...>, packer<UFirst, URest...>>
        : integral_constant<bool,
            is_contained_in_v<UFirst, TPack...> &&
            contains_types_v<packer<TPack...>, packer<URest...>>> { };

Add type(s) to the end of what’s probably, but not necessarily, a parameter pack:

    template<class T, class U> struct add_to;

    template<class T, class U>
      using add_to_t = typename add_to<T,U>::type;

One possible implementation:

Note that T and U are permitted, but not required, to be packers. It’s not clear that H. sapiens would need all those possibilities; but they’re allowed for use in machine-generated code. This applies also to unique_add_to and to remove_from’s U parameter.

    template<class T, class U>
    struct add_to<T,U>
    {
        typedef packer<U,T> type;  // note T added to the end
    };

    template<class T, class... Args>
    struct add_to<T, packer<Args...>>
    {
        typedef packer<Args..., T> type;
    };

    template<class... Args, class U>
    struct add_to<packer<Args...>, U>
    {
        typedef packer<U, Args...> type;
    };

    template<class... TArgs, class... UArgs>
    struct add_to<packer<TArgs...>, packer<UArgs...>>
    {
        typedef packer<UArgs..., TArgs...> type;
    };

As above, but add the types only if they’re not already present in `U`.

    template<class T, class U> struct unique_add_to;

    template<class T, class U>
      using unique_add_to_t = typename unique_add_to<T,U>::type;

One possible implementation:

    template<class T, class U> struct unique_add_to
    {
        typedef packer<U,T> type;
    };

    template<class T> struct unique_add_to<T,T>
    {
        typedef packer<T> type;
    };

    template<class T, class... Args>
    struct unique_add_to<T, packer<Args...>>
    {
        typedef conditional_t<is_contained_in_v<T, Args...>,
                              packer<Args...>,
                              packer<Args..., T>> type;
    };

    template<class... Args, class U>
    struct unique_add_to<packer<Args...>, U>
    {
        typedef conditional_t<is_contained_in_v<U, Args...>,
                              packer<Args...>,
                              packer<U, Args...>> type;
    };

    template<class... Args>
    struct unique_add_to<packer<Args...>, packer<Args...>>
    {
        typedef packer<Args...> type;
    };

    template<class... Args>
    struct unique_add_to<packer<>, packer<Args...>>
    {
        typedef packer<Args...> type;
    };

    template<class TFirst, class... TRest, class... UArgs>
    struct unique_add_to<packer<TFirst, TRest...>, packer<UArgs...>>
    {
        typedef conditional_t<is_contained_in_v<TFirst, UArgs...>,
                              unique_add_to<packer<TRest...>, packer<UArgs...>>,
                              unique_add_to<packer<TRest...>, packer<UArgs..., TFirst>>
                             > type;
    };

It’s because of the recursion in unique_add_to when T is itself a packer with a non-empty parameter pack that we specify that the types be added at the end: if they were added at the front, their order would be reversed, which would likely be the greater surprise.

Remove one or more types from a `packer`’s parameter pack:

    template<class Unwanted, class Given, class Result = packer<>>
    struct remove_from;

    template<class U, class G>
      using remove_from_t = typename remove_from<U,G>::type;

One possible implementation:

    template<class U, class... Out>
    struct remove_from<U, packer<>, packer<Out...>>
    {
        typedef packer<Out...> type;
    };

    template<class U, class GFirst, class... GRest, class... Out>
    struct remove_from<U, packer<GFirst, GRest...>, packer<Out...>>
      : remove_from<U,
                    packer<GRest...>,
                    conditional_t<is_same_v<GFirst, U>,
                                  packer<Out...>,
                                  packer<Out..., GFirst>
                                 >
                   > { };

    template <class... U, class GFirst, class... GRest, class... Out>
    struct remove_from<packer<U...>,
                       packer<GFirst, GRest...>,
                       packer<Out...>>
      : remove_from<packer<U...>,
                    packer<GRest...>,
                    conditional_t<is_contained_in_v<GFirst, U...>,
                                  packer<Out...>,
                                  packer<Out..., GFirst>
                                 >
                   > { };

Partly-baked idea:

Is is necessary to require that G be a packer?

    template<class U, class G>
    struct remove_from<U, G>
    {
        typedef packer<G> type;
    };

    template<class U>
    struct remove_from<U, U>
    {
        typedef packer<> type;
    };

Remove duplicate types from a parameter pack:

    template<class T, class Result = packer<>> struct uniqueify;

    template<class T> using uniqueify_t = typename uniqueify<T>::type;

One possible implementation:

    template<class... Out> struct uniqueify<packer<>, packer<Out...>>
    {
        typedef packer<Out...> type;
    };

    template<class First, class... Rest, class... Out>
    struct uniqueify<packer<First, Rest...>, packer<Out...>>
    {
        typedef conditional_t<is_contained_in_v<First, Rest...>,
                              uniqueify<packer<Rest...>, packer<Out...>>,
                              uniqueify<packer<Rest...>, packer<Out..., First>>
                             > type;
    };

Note that, given the above implementation, uniqueify removes the first of two duplicates; so the order of the types in the resulting parameter pack might be surprising. For example, uniqueify_t<packer<one,two,one>> is packer<two,one>.

Standardese relative to N3936:

In 20.10.2 Header <type_traits> synopsis [meta.type.synop]:

Change “// 20.10.3, helper class:”
- Make the heading plural:
  // 20.10.3, helper classes:
- Add at the end:
```
    template<class... T> struct packer;
```

Everything else in the paper is an addition even though it’s not underlined.

Add to “// 20.10.6, type relations:” (position and order at the discretion of the editor)

    template <class T, class... P> struct is_contained_in;
    template <class T, class U> struct contains_types;

    template <class T, class... P>
      constexpr bool is_contained_in_v = is_contained_in<T,P...>::value;
    template <class T, class U>
      constexpr bool contains_types_v = contains_types<T,U>::value;

Add to “// 20.10.7.6, other transformations:” (position and order at the discretion of the editor)

    template <class T, class U> struct add_to;
    template <class T, class U> struct unique_add_to;
    template <class T, class U, class Result = packer<>> struct remove_from;
    template <class T, class Result = packer<>> struct uniqueify;

    template <class T, class U>
      using add_to_t = typename add_to<T,U>::type;
    template <class T, class U>
      using unique_add_to_t = typename unique_add_to<T,U>::type;
    template <class T, class U>
      using remove_from_t = typename remove_from<T,U>::type;
    template <class T>
      using uniqueify_t = typename uniqueify<T>::type;

In 20.10.3 Helper classes [meta.help]:

Add just before the closing brace of namespace std:

    template<class... T> struct packer { };

Add a new paragraph after paragraph 1:
The class template packer simply holds a parameter pack.

In 20.10.6 Relationships between types [meta.rel], add to the end of Table 51:

template <class T, class... P> struct is_contained_in; Type T is contained
in parameter pack P

template <class T, class U> struct contains_types; T’s parameter pack contains
at least one instance
of each of the types
in U’s parameter pack T and U shall be packers
(20.10.3).

In 20.10.7.6 Other transformations [meta.trans.other],

Some standardese for Table 57’s Comments column remains to be written. It depends on whether the U template parameters are required to be packers. Also, does remove_from’s U parameter need to be a packer?

add to the end of Table 57:

template <class T, class U> struct add_to; The member typedef type shall name
a packer whose parameter pack contains
[more to do]

template <class T, class U> struct unique_add_to; The member typedef type shall name
a packer whose parameter pack contains
[more to do]

template <class T, class U, class Result = packer<>> struct remove_from; U shall be a packer (20.10.3). The member typedef type shall name
a packer whose parameter pack contains
each of the types in U’s parameter pack
excluding the type T, or if T is itself a
packer, excluding any type in T’s
parameter pack.

template <class U, class Result = packer<>> struct uniqueify; U shall be a packer (20.10.3). The member typedef type shall name
a packer whose parameter pack contains
each of the types in U’s parameter pack
exactly once. The order of the types in
type’s parameter pack is unspecified.

Appendix A, a crude test:

The actual code, in the public domain, can be found here.

#include <iostream>
#include <type_traits> // assume it has the additions proposed above
using namespace std;

//
// Some types to put in parameter packs:
//
struct one   { static const int value = 1; };
struct two   { static const int value = 2; };
struct three { static const int value = 3; };
struct four  { static const int value = 4; };
struct five  { static const int value = 5; };

typedef packer<one, two, three>   first_three;
typedef packer<four, five>        last_two;
typedef packer<three, four, five> last_three;

//
// Listing types on the standard output:
//
template<class... Args> void show_types(packer<Args...>);

template<> inline void show_types(packer<>) { }

template<class First, class... Rest>
void show_types(packer<First, Rest...>)
{
    cout << First::value << "  ";
    show_types(packer<Rest...>());
}

//
// The tests:
//
int main()
{
    cout << boolalpha;

    cout << contains_types<first_three, packer<>>::value << '\n';
    cout << contains_types<first_three, packer<one>>::value << '\n';
    cout << contains_types<first_three, packer<two>>::value << '\n';
    cout << contains_types<first_three, packer<three>>::value << '\n';
    cout << contains_types<first_three, packer<one,two>>::value << '\n';
    cout << contains_types<first_three, packer<one,three>>::value << '\n';
    cout << contains_types<first_three, packer<two,three>>::value << '\n';
    cout << contains_types<first_three, first_three>::value << '\n';

    cout << '\n';

    cout << contains_types<first_three, packer<four>>::value << '\n';
    cout << contains_types<first_three, last_two>::value << '\n';
    cout << contains_types<first_three, last_three>::value << '\n';
    cout << contains_types<packer<one,two>, first_three>::value << '\n';

    cout << '\n';

    show_types(add_to<three, first_three>());
    cout << '\n';
    show_types(add_to<four, first_three>());
    cout << '\n';
    show_types(add_to<last_two, first_three>());
    cout << '\n';
    show_types(add_to<last_three, first_three>());

    cout << "\n\n";

    show_types(unique_add_to<three, first_three>());
    cout << '\n';
    show_types(unique_add_to<four, first_three>());
    cout << '\n';
    show_types(unique_add_to<last_two, first_three>());
    cout << '\n';
    show_types(unique_add_to<last_three, first_three>());

    cout << "\n\n";

    show_types(remove_from<one, first_three>::type());
    cout << '\n';
    show_types(remove_from<two, first_three>::type());
    cout << '\n';
    show_types(remove_from<three, first_three>::type());
    cout << '\n';
    show_types(remove_from<four, first_three>::type());
    cout << '\n';
    show_types(remove_from<last_two, first_three>::type());
    cout << '\n';
    show_types(remove_from<last_three, first_three>::type());


    cout << "\n\n";

    show_types(uniqueify<first_three>::type());
    cout << '\n';
    show_types(uniqueify<packer<one, two, one>>::type());
    cout << '\n';
    show_types(
      uniqueify<packer<one, one, two, three, four, two, four, four>>::type());
}

Expected output:

true
true
true
true
true
true
true
true

false
false
false
false

1  2  3  3
1  2  3  4
1  2  3  4  5
1  2  3  3  4  5

1  2  3
1  2  3  4
1  2  3  4  5
1  2  3  4  5

2  3
1  3
1  2
1  2  3
1  2  3
1  2

1  2  3
2  1
1  3  2  4

Reply to: stdbill.h@pobox.com

`template <class T, class... P> struct is_contained_in;`	Type `T` is contained in parameter pack `P`
`template <class T, class U> struct contains_types;`	`T`’s parameter pack contains at least one instance of each of the types in `U`’s parameter pack	`T` and `U` shall be `packer`s (20.10.3).

`template <class T, class U> struct add_to;`		The member typedef `type` shall name a `packer` whose parameter pack contains [more to do]
`template <class T, class U> struct unique_add_to;`		The member typedef `type` shall name a `packer` whose parameter pack contains [more to do]
`template <class T, class U, class Result = packer<>> struct remove_from;`	`U` shall be a `packer` (20.10.3).	The member typedef `type` shall name a `packer` whose parameter pack contains each of the types in `U`’s parameter pack excluding the type `T`, or if `T` is itself a `packer`, excluding any type in `T`’s parameter pack.
`template <class U, class Result = packer<>> struct uniqueify;`	`U` shall be a `packer` (20.10.3).	The member typedef `type` shall name a `packer` whose parameter pack contains each of the types in `U`’s parameter pack exactly once. The order of the types in `type`’s parameter pack is unspecified.

Searching and Manipulation of Parameter Packs

Bill SeymourStephan T. Lavavej2014-09-11

Abstract:

Revision history:

The basic idea:

A class template that just holds a parameter pack:

Whether type T is in parameter pack P:

One possible implementation:

Whether a packer, T, has a parameter pack that’s a superset of the pack of some minimum packer, U:

One possible implementation:

Add type(s) to the end of what’s probably, but not necessarily, a parameter pack:

One possible implementation:

As above, but add the types only if they’re not already present in U.

One possible implementation:

Remove one or more types from a packer’s parameter pack:

One possible implementation:

Partly-baked idea:

Remove duplicate types from a parameter pack:

One possible implementation:

Standardese relative to N3936:

Appendix A, a crude test:

Expected output:

Bill Seymour
Stephan T. Lavavej
2014-09-11

Whether a `packer`, T, has a parameter pack that’s a superset of the pack of some minimum `packer`, U:

As above, but add the types only if they’re not already present in `U`.

Remove one or more types from a `packer`’s parameter pack: