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>.

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]:
Everything else in the paper is an addition even though it’s not underlined.

In 20.10.3 Helper classes [meta.help]:


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