Does C++ support compile-time counters?

Question

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 does 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"
}

Ahrens

can you give a short example to demo what is the exact question ? – Sievert

is it not possible to use X<__LINE__> ? that will provide a unique number (may not be serial number) always in the given file. – Sievert

@iammilind: That doesn't work across several headers, and won't return the same result repeatedly when uniqueness isn't desired. The template solution is more powerful. See the answer. – Ahrens

Related: C++ construct that behaves like the COUNTER macro. – Sievert

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

Ahrens

Link to your first code running online seems invalidated. – Missie

@Missie Thanks, I'll notify IDEone. The result is just the same as the second code, anyway. – Ahrens

cn<N> can be padded at the compiler's discretion. So sizeof( cn<N> ) can be any value >= N. Needs to use sizeof( cn<N>::data ). – Personalism

Also worth noting that (1) approaches like this are doomed to failure with separate compilation, and (2) that they are somewhat dangerous wrt. to use of ids for external storage, e.g. serialization, because the ids can depend on header inclusion order. – Personalism

@Cheersandhth.-Alf The use of separate IDs (as opposed to a single global __COUNTER__) alleviates the inclusion order issue. If numbering the header files is the goal, then the user should be aware of consistency across TUs. – Ahrens

@Cheersandhth.-Alf That does appear to be a bug in the C++98 version. Thanks, fixed! (The fix is slightly different because there's no decltype keyword.) – Ahrens

The solution involving counter_read() and counter_inc need some explanation, especially usage of cn<>, seen and the bitwise operation (x+1) & ~x ,etc. all of them look so cryptic! – Privity

For another C++11 (and beyond) solution on compile-time counting you might also check out the solution provided by the Copperspice project. The videos are on YouTube either here or here – Detour

"The declarations should be put inside a namespace": at definition site or call site? – Allianora

@Louis-JacobLebel It's been a while, but re-reading this code, I just meant to encapsulate constant_index and counter_crumb in a private namespace. It's just a straightforward library, but with a preprocessor macro interface. (I really should just make a Git repo with a header containing this snippet.) – Ahrens

@Ahrens Okay, thanks for the fast answer. If you end up making a repository, I'd appreciate to have the URL: this code is currently inlined in a header in my current project, and I would be more comfortable by rendering it as a git submodule. – Allianora

Answer 2

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

Halves

You should check the kinds of beauty that lead to words like duodecilliotonically, if I'm getting my prefixes right... :P – Pumping

This is the most common solution, but 1. isn't standard; 2. is not reusable - there is only one counter per translation unit; 3. cannot be read without being modified. – Ahrens

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

Sievert

Very nice! However, this incurs a level of template nesting for each source line, so for large files it likely won't compile. – Ahrens

Also, it will get confused if used it two different header files. (But namespaces can be used to contain the damage.) – Ahrens

1 << 9 is only 512 ;v) . See ideone.com/dOXTG . As you can see from the error message, 512 is exactly the highest value that is guaranteed to work with this version of this compiler. – Ahrens

@Potatoswatter, I stumbled upon this Q again and was just wondering that what was the context. Last time you told that the limit is only 512, however when I checked in G++, it works fine for larger number as well. See demo. May be I missed something. If you don't mind, can you point out the problems with this solution? – Sievert

@Sievert It instantiates O(N) templates where N is the length of the source file. That's suboptimal although it may work. The maximum template depth tends to increase over time on any given platform. – Ahrens

@Potatoswatter, by mistake I have upvoted your above comment :). Actually Have checked for 100000 lines in a file which compiles fine with g++-5 in 4 seconds. May be this is not the best way to get an estimate, but it surely gives an idea. The simplicity of this solution is worth for the practical purposes. Probably with newer and smarter compilers this solution is more and more feasible. – Sievert

Answer 4

With C++20, it's possible to use lambdas in unevaluated contexts, which allows for a rather elegant solution while taking advantage of the infamous friend-injection technique. The live example can be found here, tested with Clang 17.0.1, GCC 13.2, and MSVC 19.38.

template<auto Id>
struct counter {
    using tag = counter;

    struct generator {
        friend consteval auto is_defined(tag)
        { return true; }
    };
    friend consteval auto is_defined(tag);

    template<typename Tag = tag, auto = is_defined(Tag{})>
    static consteval auto exists(auto)
    { return true; }

    static consteval auto exists(...)
    { return generator(), false; }
};

template<auto Id = int{}, typename = decltype([]{})>
consteval auto unique_id() {
    if constexpr (not counter<Id>::exists(Id)) return Id;
    else return unique_id<Id + 1>();
}

static_assert(unique_id() == 0);
static_assert(unique_id() == 1);
static_assert(unique_id() == 2);
static_assert(unique_id() == 3);

The lambda of the defaulted template argument is necessary to ensure the compiler will re-evaluate the compile time conditional statement for each implicit instantiation of the templated function. Even when using a non-type template argument defaulted with the result of the conditional statement, the compiler doesn't seem to re-evaluate it fully but rather caches the result.

Koontz

Answer 5

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;
}

Tremain

You're right. I just tested it with vc++, gcc and clang. The former two work but clang doesn't. The reason for this is, the expression used for checking if a adl_flag has been defined does not work for clang. (This one: class = char[noexcept( adl_flag(flag<N>()) ) ? +1 : -1]) If you can find one that correctly returns a type, only if adl_flag(flag<N>) has already been defined, this will work. – Tremain

Try looking here at the bottom for the clang fix. It's probably a bit more work to incorporate it into the code, but should be doable. – Tremain

Only answer that doesn't use macros – Eluvium

Note to the reader: the CWG has expressed a desire to eliminate the friend loophole that allows this to work. It may not be future-proof (and doesn't always work on all compilers). See here for more: b.atch.se/posts/constexpr-meta-container/#conclusion-wg21 – Cheshvan

Doesn't work for gcc as well. coliru.stacked-crooked.com/a/e7603c4b9e134175 – Dunnite

Answer 6

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

Screak

Unfortunately equally to COUNTER, this counter lacks the same support issues to be used in a translation units comprehensive global context.. – Vase

Answer 7

Here's another alternative implementation. https://mcmap.net/q/20768/-does-c-support-compile-time-counters 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);

Cassation

Note that the limit applies to the number of times the counter may be evaluated, not its maximum value. Sorry, I should probably have explained the math I used. And in general how my implementation works… it's rather involved. But mine is O(log limit value) to read and write, whereas this appears to be O(limit accesses). – Ahrens

Note that you can use __VA_ARGS__ and variadic macros to pass , as a macro argument, obviating COMMA. – Ahrens

Thanks for __VA_ARGS__ tip! I didn't mean to criticize your answer; even if you explained it I'm not sure I have the requisite mental faculties. If you did add some more explanation, though, I'd read it carefully. – Cassation

As for the complexity, I thought it was O(limit value)... If I understand my code correctly (lol) it does CounterLimit recursions in GetCount and 3 * CounterLimit in GetLCount. __COUNTER__ was only supposed to change function visibility and force template reinstantiation. I just checked though and CounterLimit can be 250 with no issues, so I think I originally misjudged the recursion thing. – Cassation

I tried a file with IncrementLCount 32000 times and clang was killed by the kernel (out of memory) after about 20 minutes (4GB RAM, +2GB swap). – Cassation

I didn't make it through the two-level version. But __COUNTER__ is incremented with each access, so if I'm reading correctly, you will run out of instantiations just by accessing it. I haven't tested it. More critically, this may run afoul of the ODR because two different translation units with same headers using GetCount differently will have technically different definitions, even if each use returns the same value in each TU. I think it's possible to use it legally with judicious assignment to constexpr variables, but following the letter of the ODR could be tricky. – Ahrens

I don't mean to criticize your efforts; this is not an easy problem! Kudos for getting it to work at all. I will write-up my solution sometime, either here or in my blog. – Ahrens

Answer 8

I've gone through this whole thing myself and eventually have come up with a solution that seems to be standard-compliant (at the time I'm writing this) and works with gcc, clang, msvc and icc, in all their recent versions and in most of the old ones.

I've talked about the whole process into another post on here: C++ compile time counters, revisited.

I've then packaged the solution into a fameta::counter class that solves a few remaining quirks.

You can find it on github.

Pieplant

Answer 9

With C++20 onward.

You have source_location which can generate indices from C++ function with no macros at all.

Sample code

#include <source_location> // merged in C++20

constexpr auto Generate(const std::source_location& location =
                            std::source_location::current()) {
  return location.line();
}

now you can use it as a counter through one source file or add compile time hash function for source location with file name to get unique index.

Dysuria

Was possible pre-C++20 with a non-standard __builtin_LINE() as the default argument. – Ci

With multiple files, line numbers aren't monotonic or even unique. – Ahrens

Answer 10

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.

Glyconeogenesis

Answer 11

From C++ 17, this simple solution worked pretty fine for me. And the overhead is minimum. Looks almost like compile-time counter.

struct counter
{
    private:
        static inline uint32 count = 0;

    public:
        static inline auto next() { return ++count; }
};

Trichosis

Except it isn't a compile time counter and won't be usable in constexpr expressions. – Nonagon