Check if a template parameter appears more than twice in a homogeneous parameter pack

Question

I need to check if any of the parameters passed to a function appear more than twice. Essentially, I want the following behaviour

appearance<0,1,0,1>::value // should return true
appearance<2,0,1,2,2>::value // should return false
appearance<5,5,5>::value // should return false 

I know there is a question on finding the number of uniques, but it does not answer my question, since the solutions to that question return for instance

no_unique<0,1,0,1,0,1>::value // returns 2

But it does not say if the parameter appeared once, twice or three times.

How can I achieve this in C++11?

Answer 1

My answer by abuse multiple inheritance:

#include <utility>
#include <type_traits>

template <std::size_t I>
struct wrap {};

template <std::size_t ... Is>
struct derived : wrap<Is>...
{
};
template <>
struct derived<> {
};

template <typename, typename, std::size_t...>
struct appearance_impl;

template <std::size_t... I2, std::size_t... I1, std::size_t I, std::size_t...Is>
struct appearance_impl<derived<I2...>, derived<I1...>, I, Is...>
    : std::conditional<
        std::is_base_of<wrap<I>, derived<I2...>>::value, // If I in I2 => false
        std::false_type,
        typename std::conditional<
            std::is_base_of<wrap<I>, derived<I1...>>::value, // else if I in I1, add I to I2
            appearance_impl<derived<I, I2...>, derived<I1...>, Is...>,
            appearance_impl<derived<I2...>, derived<I, I1...>, Is...>
            >::type
        >::type
{
};

template <typename D2, typename D1>
struct appearance_impl<D2, D1> : std::true_type {};


template <std::size_t ...Is>
struct appearance : appearance_impl<derived<>, derived<>, Is...>::type { };

int main() {
    static_assert(appearance<0,1,0,1>::value, "");
    static_assert(!appearance<2,0,1,2,2>::value, "");
    static_assert(!appearance<5,5,5>::value, "");
}

Demo

Answer 2

Short and quite readable version using boost.hana:

#include <boost/hana/all_of.hpp>
#include <boost/hana/group.hpp>
#include <boost/hana/length.hpp>
#include <boost/hana/less.hpp>
#include <boost/hana/sort.hpp>
#include <boost/hana/tuple.hpp>
#include <boost/hana/type.hpp>

namespace hana = boost::hana;

template <int... ints>
struct appearance {
    static constexpr bool value =
        hana::all_of(
            hana::transform(
                hana::group(
                    hana::sort(
                        hana::make_tuple(hana::size_c<ints>...))),
                hana::length),
            hana::less.than(hana::size_c<3>));
};

On Coliru

Answer 3

Can I play too?

The following is my solution, heavely based on partial template specialization.

#include <iostream>

using IType = int; // or long? or unsigned? or size_t?

template <typename IT, IT ...>
struct intSeq
 { };

template <typename, typename, std::size_t>
struct no_more_than_val;

template <typename IT, IT I0, std::size_t M, IT Val, IT ... Is>
struct no_more_than_val<intSeq<IT, I0, Is...>, intSeq<IT, Val>, M>
 { static constexpr bool value
    { no_more_than_val<intSeq<IT, Is...>, intSeq<IT, Val>, M>::value }; };

template <typename IT, IT Val, std::size_t M, IT ... Is>
struct no_more_than_val<intSeq<IT, Val, Is...>, intSeq<IT, Val>, M>
 { static constexpr bool value
    { no_more_than_val<intSeq<IT, Is...>, intSeq<IT, Val>, M-1U>::value }; };

template <typename IT, IT I0, IT ... Is>
struct no_more_than_val<intSeq<IT, I0, Is...>, intSeq<IT, I0>, 0U>
 { static constexpr bool value { false }; };

template <typename IT, std::size_t M, IT Val>
struct no_more_than_val<intSeq<IT>, intSeq<IT, Val>, M>
 { static constexpr bool value { true }; };


template <typename, std::size_t>
struct no_more_than_list;

template <typename IT, std::size_t M>
struct no_more_than_list<intSeq<IT>, M>
 { static constexpr bool value { true }; };

template <typename IT, IT I0, IT ... Is>
struct no_more_than_list<intSeq<IT, I0, Is...>, 0U>
 { static constexpr bool value { false }; };

template <typename IT, std::size_t M, IT I0, IT ... Is>
struct no_more_than_list<intSeq<IT, I0, Is...>, M>
 {
   static constexpr bool value
    {    no_more_than_val<intSeq<IT, Is...>, intSeq<IT, I0>, M-1U>::value
      && no_more_than_list<intSeq<IT, Is...>, M>::value };
 };


template <IType ... Is>
struct appearance
   : public no_more_than_list<intSeq<IType, Is...>, 2U>
 { };


int main()
 {
   std::cout << appearance<0,1,0,1>::value << std::endl;   // print 1
   std::cout << appearance<2,0,1,2,2>::value << std::endl; // print 0
   std::cout << appearance<5,5,5>::value << std::endl;     // print 0
 }

If you can use C++14, you can use std::integer_sequence instead of intSeq. Anyway, you can use std::integral_constant<IT, Val> instead of intSeq<IT, Val>.

Answer 4

This is a little longer, but it should be pretty efficient and it avoids much cleverness.

// Map integers to types.
template< int i >
using intc = std::integral_constant< int, i >;

// Increment a type-integer.
template< typename intc >
using inc_intc = std::integral_constant< int, intc::value + 1 >;

// Count the appearances of an integer in a sequence.
template< int ... >
struct appearances { // Base case of induction: return zero for every value.
    template< int i >
    static intc< 0 > count( intc< i > );
};

// Recursive case: Add one to the base class count.
template< int i, int ... rem >
struct appearances< i, rem ... >
    : appearances< rem ... > {
    typedef appearances< rem ... > base;
    using base::count;

    static inc_intc< decltype( base::count( intc< i >{} ) ) >
        count( intc< i > );
};

// Find the sequences in question with early exit.
template< typename acc, typename seq, typename = void >
struct no_triple_occurrence_impl // Base case: empty sequence, no triples.
    : std::true_type {};

// Early exit case: found two instances of the next i.
template< typename acc, int i, int ... rem >
struct no_triple_occurrence_impl<
    acc,
    std::integer_sequence< int, i, rem ... >,
    std::enable_if_t< decltype(
        acc::count( intc< i >{} )
    ){} >= 2 >
> : std::false_type {};

// Recursive case: add the next i to the counter.
template< int ... done, int i, int ... rem >
struct no_triple_occurrence_impl<
    appearances< done ... >,
    std::integer_sequence< int, i, rem ... >,
    std::enable_if_t< decltype(
        appearances< done ... >::count( intc< i >{} )
    ){} < 2 >
> : no_triple_occurrence_impl<
    appearances< i, done ... >, // Keep done... at the end for memoization.
    std::integer_sequence< int, rem ... >
>::type {};

template< int ... seq >
constexpr bool no_triple_occurrence
    = no_triple_occurrence_impl<
        appearances<>,
        std::integer_sequence< int, seq ... >
    >::value; 

(on Coliru.)

Answer 5

Not really efficient but you could use the following:

#include <algorithm>
#include <type_traits>

template <size_t S, size_t... Sizes>
struct count;

template <size_t S>
struct count<S>: std::integral_constant<size_t, 0> {};

template <size_t S1, size_t... Sizes>
struct count<S1, S1, Sizes...>: 
    std::integral_constant<size_t, 1 + count<S1, Sizes...>{}> {};

template <size_t S1, size_t S2, size_t... Sizes>
struct count<S1, S2, Sizes...>: 
    count<S1, Sizes...> {};

template <size_t...>
struct max_count;

template <>
struct max_count<>: std::integral_constant<size_t, 0> { };

template <size_t S, size_t... Sizes>
struct max_count<S, Sizes...>:
    std::integral_constant<size_t, std::max(1 + count<S, Sizes...>{},
                                            max_count<Sizes...>::value)> { };

template <size_t... Sizes>
struct no_more_than_two: std::integral_constant<bool, max_count<Sizes...>{} <= 2> { };

static_assert(no_more_than_two<0,1,0,1>{}, "");
static_assert(!no_more_than_two<2,0,1,2,2>{}, "");
static_assert(!no_more_than_two<5,5,5>{}, "");

You first retrieve the maximum number of occurrences of any value and then compare it to 2.

If you only have C++11 (not C++14), replace std::max by a custom ct_max:

template <typename T>
constexpr const T& ct_max(T const& t1, T const& t2) {
    return t1 < t2 ? t2 : t1;
}