Does C++ support compile-time counters?

2019-01-01 08:22发布

问题:

For the purpose of introspection, sometimes I\'ve wanted to automatically assign serial numbers to types, or something similar.

Unfortunately, template metaprogramming is essentially a functional language, and as such lacks global variables or modifiable state which would implement such a counter.

Or is it?


Example code by request:

#include <iostream>

int const a = counter_read;
counter_inc;
counter_inc;
counter_inc;
counter_inc;
counter_inc;

int const b = counter_read;

int main() {
    std::cout << a << \' \' << b << \'\\n\'; // print \"0 5\"

    counter_inc_t();
    counter_inc_t();
    counter_inc_t();

    std::cout << counter_read << \'\\n\'; // print \"8\"

    struct {
        counter_inc_t d1;
        char x[ counter_read ];
        counter_inc_t d2;
        char y[ counter_read ];
    } ls;

    std::cout << sizeof ls.x << \' \' << sizeof ls.y << \'\\n\'; // print \"9 10\"
}

回答1:

Well… yes, template metaprogramming lacks side effects as it is intended. I was misled by a bug in older versions of GCC and a little unclear wording in the Standard to believe that all those features were possible.

However, at least the namespace-scope functionality can be achieved with little use of templates at all. Function lookup can extract numeric state from the set of declared functions, as demonstrated below.

Library code:

template< size_t n > // This type returns a number through function lookup.
struct cn // The function returns cn<n>.
    { char data[ n + 1 ]; }; // The caller uses (sizeof fn() - 1).

template< typename id, size_t n, size_t acc >
cn< acc > seen( id, cn< n >, cn< acc > ); // Default fallback case.

/* Evaluate the counter by finding the last defined overload.
   Each function, when defined, alters the lookup sequence for lower-order
   functions. */
#define counter_read( id ) \\
( sizeof seen( id(), cn< 1 >(), cn< \\
( sizeof seen( id(), cn< 2 >(), cn< \\
( sizeof seen( id(), cn< 4 >(), cn< \\
( sizeof seen( id(), cn< 8 >(), cn< \\
( sizeof seen( id(), cn< 16 >(), cn< \\
( sizeof seen( id(), cn< 32 >(), cn< 0 \\
/* Add more as desired; trimmed for Stack Overflow code block. */ \\
                      >() ).data - 1 ) \\
                      >() ).data - 1 ) \\
                      >() ).data - 1 ) \\
                      >() ).data - 1 ) \\
                      >() ).data - 1 ) \\
                      >() ).data - 1 )

/* Define a single new function with place-value equal to the bit flipped to 1
   by the increment operation.
   This is the lowest-magnitude function yet undefined in the current context
   of defined higher-magnitude functions. */
#define counter_inc( id ) \\
cn< counter_read( id ) + 1 > \\
seen( id, cn< ( counter_read( id ) + 1 ) & ~ counter_read( id ) >, \\
          cn< ( counter_read( id ) + 1 ) & counter_read( id ) > )

Quick demo (see it run):

struct my_cnt {};

int const a = counter_read( my_cnt );
counter_inc( my_cnt );
counter_inc( my_cnt );
counter_inc( my_cnt );
counter_inc( my_cnt );
counter_inc( my_cnt );

int const b = counter_read( my_cnt );

counter_inc( my_cnt );

#include <iostream>

int main() {
    std::cout << a << \' \' << b << \'\\n\';

    std::cout << counter_read( my_cnt ) << \'\\n\';
}

C++11 Update

Here is an updated version using C++11 constexpr in place of sizeof.

#define COUNTER_READ_CRUMB( TAG, RANK, ACC ) counter_crumb( TAG(), constant_index< RANK >(), constant_index< ACC >() )
#define COUNTER_READ( TAG ) COUNTER_READ_CRUMB( TAG, 1, COUNTER_READ_CRUMB( TAG, 2, COUNTER_READ_CRUMB( TAG, 4, COUNTER_READ_CRUMB( TAG, 8, \\
    COUNTER_READ_CRUMB( TAG, 16, COUNTER_READ_CRUMB( TAG, 32, COUNTER_READ_CRUMB( TAG, 64, COUNTER_READ_CRUMB( TAG, 128, 0 ) ) ) ) ) ) ) )

#define COUNTER_INC( TAG ) \\
constexpr \\
constant_index< COUNTER_READ( TAG ) + 1 > \\
counter_crumb( TAG, constant_index< ( COUNTER_READ( TAG ) + 1 ) & ~ COUNTER_READ( TAG ) >, \\
                                                constant_index< ( COUNTER_READ( TAG ) + 1 ) & COUNTER_READ( TAG ) > ) { return {}; }

#define COUNTER_LINK_NAMESPACE( NS ) using NS::counter_crumb;

template< std::size_t n >
struct constant_index : std::integral_constant< std::size_t, n > {};

template< typename id, std::size_t rank, std::size_t acc >
constexpr constant_index< acc > counter_crumb( id, constant_index< rank >, constant_index< acc > ) { return {}; } // found by ADL via constant_index

http://ideone.com/yp19oo

The declarations should be put inside a namespace, and all names used in the macros except counter_crumb should be fully qualified. The counter_crumb template is found via ADL association with the constant_index type.

The COUNTER_LINK_NAMESPACE macro can be used to increment one counter in the scope of multiple namespaces.



回答2:

I believe both MSVC and GCC support a __COUNTER__ preprocessor token that has a monotonically increasing value substituted in its place.



回答3:

I was thinking to solve this problem for quite sometime, and have come up with a very short-clean solution. At least I deserve one upvote to try this out. :))

Following library code achieves namespace level functionality. i.e. I am successful to implement counter_read and counter_inc; but not the counter_inc_t (which is incremented inside function because template classes are not allowed inside function)

template<unsigned int NUM> struct Counter { enum { value = Counter<NUM-1>::value }; };
template<> struct Counter<0> { enum { value = 0 }; };

#define counter_read Counter<__LINE__>::value
#define counter_inc template<> struct Counter<__LINE__> { enum { value = Counter<__LINE__-1>::value + 1}; }

This technique uses template meta-programming and leverages the __LINE__ macro. See the result for the code from your answer.



回答4:

You could use BOOST_PP_COUNTER from Boost.Preprocessor.

Advantage: it works even for macros

Disadvantage: there is only one \"counter kind\" for the whole program, but the mechanism may be reimplemented for dedicated counters



回答5:

Here\'s another alternative implementation. https://stackoverflow.com/a/6174263/1190123 is probably better, but even after manually working through a couple increments on paper I still don\'t quite understand the math/filtering.

This uses constexpr function recursion to count the number of non-template declared Highest functions. __COUNTER__ is used as a generational mechanism to prevent new declarations of Highest from doing self recursion.

This only compiles on clang for me (3.3). I\'m not sure it\'s compliant, but I\'m hopeful. g++ 4.8 fails due to some unimplemented feature (according to the error). Intel compiler 13 also fails, due to a constexpr bug.

256 level counter

The maximum count per counter is 250 (CounterLimit). CounterLimit can be increased to 256 unless you implement the LCount stuff below.

Implementation

#include <iostream>
#include <type_traits>

constexpr unsigned int CounterLimit = 250;

template <unsigned int ValueArg> struct TemplateInt { constexpr static unsigned int Value = ValueArg; };

template <unsigned int GetID, typename, typename TagID>
constexpr unsigned int Highest(TagID, TemplateInt<0>)
{
    return 0;
}

template <unsigned int GetID, typename, typename TagID, unsigned int Index>
constexpr unsigned int Highest(TagID, TemplateInt<Index>)
{
    return Highest<GetID, void>(TagID(), TemplateInt<Index - 1>());
}

#define GetCount(...) \\
Highest<__COUNTER__, void>(__VA_ARGS__(), TemplateInt<CounterLimit>())

#define IncrementCount(TagID) \\
template <unsigned int GetID, typename = typename std::enable_if<(GetID > __COUNTER__ + 1)>::type> \\
constexpr unsigned int Highest( \\
    TagID, \\
    TemplateInt<GetCount(TagID) + 1> Value) \\
{ \\
      return decltype(Value)::Value; \\
}

Testing

struct Counter1 {};
struct Counter2 {};
constexpr unsigned int Read0 = GetCount(Counter1);
constexpr unsigned int Read1 = GetCount(Counter1);
IncrementCount(Counter1);
constexpr unsigned int Read2 = GetCount(Counter1);
IncrementCount(Counter1);
constexpr unsigned int Read3 = GetCount(Counter1);
IncrementCount(Counter1);
constexpr unsigned int Read4 = GetCount(Counter1);
IncrementCount(Counter1);
IncrementCount(Counter2);
constexpr unsigned int Read5 = GetCount(Counter1);
constexpr unsigned int Read6 = GetCount(Counter2);

int main(int, char**)
{
    std::cout << \"Ending state 0: \" << Highest<__COUNTER__, void>(Counter1(), TemplateInt<0>()) << std::endl;
    std::cout << \"Ending state 1: \" << Highest<__COUNTER__, void>(Counter1(), TemplateInt<1>()) << std::endl;
    std::cout << \"Ending state 2: \" << Highest<__COUNTER__, void>(Counter1(), TemplateInt<2>()) << std::endl;
    std::cout << \"Ending state 3: \" << Highest<__COUNTER__, void>(Counter1(), TemplateInt<3>()) << std::endl;
    std::cout << \"Ending state 4: \" << Highest<__COUNTER__, void>(Counter1(), TemplateInt<4>()) << std::endl;
    std::cout << \"Ending state 5: \" << Highest<__COUNTER__, void>(Counter1(), TemplateInt<5>()) << std::endl;
    std::cout << Read0 << std::endl;
    std::cout << Read1 << std::endl;
    std::cout << Read2 << std::endl;
    std::cout << Read3 << std::endl;
    std::cout << Read4 << std::endl;
    std::cout << Read5 << std::endl;
    std::cout << Read6 << std::endl;

    return 0;
}

Output

Ending state 0: 0
Ending state 1: 1
Ending state 2: 2
Ending state 3: 3
Ending state 4: 4
Ending state 5: 4
0
0
1
2
3
4
1

250 * 250 level counter

If you want higher values than 256, I think you can combine counters. I did 250 * 250 (although I didn\'t really test counting past 2). CounterLimit has to be lowered to around 250 for compiler compile time recursion limits. Just to note, this took significantly more time to compile for me.

Implementation

template <typename, unsigned int> struct ExtraCounter { };

template <unsigned int GetID, typename, typename TagID>
constexpr unsigned int LHighest(TagID)
{
    return Highest<GetID, void>(ExtraCounter<TagID, CounterLimit>(), TemplateInt<CounterLimit>()) * CounterLimit +
        Highest<GetID, void>(
            ExtraCounter<TagID, Highest<GetID, void>(ExtraCounter<TagID , CounterLimit>(), TemplateInt<CounterLimit>())>(),
            TemplateInt<CounterLimit>());
}
#define GetLCount(TagID) \\
LHighest<__COUNTER__, void>(TagID())

#define LIncrementTag_(TagID) \\
typename std::conditional< \\
    GetCount(ExtraCounter<TagID, GetCount(ExtraCounter<TagID, CounterLimit>)>) == CounterLimit - 1, \\
    ExtraCounter<TagID, CounterLimit>, \\
    ExtraCounter<TagID, GetCount(ExtraCounter<TagID, CounterLimit>)>>::type
#define IncrementLCount(TagID) \\
template <unsigned int GetID, typename = typename std::enable_if<(GetID > __COUNTER__ + 7)>::type> \\
constexpr unsigned int Highest( \\
    LIncrementTag_(TagID), \\
    TemplateInt<GetCount(LIncrementTag_(TagID)) + 1> Value) \\
{ \\
      return decltype(Value)::Value; \\
}

Testing

struct Counter3 {};
constexpr unsigned int Read7 = GetLCount(Counter3);
IncrementLCount(Counter3);
constexpr unsigned int Read8 = GetLCount(Counter3);


回答6:

Since sharing is caring and I spent a few hours fiddling around with the base example this side provides I\'m going to post my solution as well.

The version linked to in the article has two major downsides. The max number it can count too is very low, due to max recursion depth (usually something around 256). And the time it takes to compile as soon as a count of more than a few hundred has been reached is huge.

By implementing binary search to detect if a flag for a counter has already been set or not, it\'s possible to massively increase the max count (controllable through MAX_DEPTH) and also improve compile time at the same time. =)

Usage example:

static constexpr int a = counter_id();
static constexpr int b = counter_id();
static constexpr int c = counter_id();

#include <iostream>

int main () {
    std::cout << \"Value a: \" << a << std::endl;
    std::cout << \"Value b: \" << b << std::endl;
    std::cout << \"Value c: \" << c << std::endl;
}

Fully working code with example at the end: (Except for clang. See comments.)

// Number of Bits our counter is using. Lower number faster compile time,
// but less distinct values. With 16 we have 2^16 distinct values.
#define MAX_DEPTH 16

// Used for counting.
template<int N>
struct flag {
    friend constexpr int adl_flag(flag<N>);
};

// Used for noting how far down in the binary tree we are.
// depth<0> equales leaf nodes. depth<MAX_DEPTH> equals root node.
template<int N> struct depth {};

// Creating an instance of this struct marks the flag<N> as used.
template<int N>
struct mark {
    friend constexpr int adl_flag (flag<N>) {
        return N;
    }

    static constexpr int value = N;
};

// Heart of the expression. The first two functions are for inner nodes and
// the next two for termination at leaf nodes.

// char[noexcept( adl_flag(flag<N>()) ) ? +1 : -1] is valid if flag<N> exists.
template <int D, int N, class = char[noexcept( adl_flag(flag<N>()) ) ? +1 : -1]>
int constexpr binary_search_flag(int,  depth<D>, flag<N>,
        int next_flag = binary_search_flag(0, depth<D-1>(), flag<N + (1 << (D - 1))>())) {
    return next_flag;
}

template <int D, int N>
int constexpr binary_search_flag(float, depth<D>, flag<N>,
        int next_flag = binary_search_flag(0, depth<D-1>(), flag<N - (1 << (D - 1))>())) {
    return next_flag;
}

template <int N, class = char[noexcept( adl_flag(flag<N>()) ) ? +1 : -1]>
int constexpr binary_search_flag(int,   depth<0>, flag<N>) {
    return N + 1;
}

template <int N>
int constexpr binary_search_flag(float, depth<0>, flag<N>) {
    return N;
}

// The actual expression to call for increasing the count.
template<int next_flag = binary_search_flag(0, depth<MAX_DEPTH-1>(),
        flag<(1 << (MAX_DEPTH-1))>())>
int constexpr counter_id(int value = mark<next_flag>::value) {
    return value;
}

static constexpr int a = counter_id();
static constexpr int b = counter_id();
static constexpr int c = counter_id();

#include <iostream>

int main () {
    std::cout << \"Value a: \" << a << std::endl;
    std::cout << \"Value b: \" << b << std::endl;
    std::cout << \"Value c: \" << c << std::endl;
}


回答7:

Unfortunately, template metaprogramming is essentially a functional language, and as such lacks global variables or modifiable state which would implement such a counter.

Or is it?

C++ allows compile time counters (i.e. without __COUNTER__, __LINE__ or other approaches proposed here earlier) as well as allocating and defining inner int unique ID for each template instance. See v1 solution for the counter implemented with template metaprograming using chaining allocated IDs and v2 for the second use case. Both solutions are answers for \"How can I generate dense unique type IDs at compile time?\". But the task has an important requirement about the only ID allocator.