checking uniqueness of characters at compile time

Question

Is it possible in C++11 (not later) to write a function that verifies the uniqueness of characters passed to it at compile time

verify('a');
verify('b');
verify('c');
verify('a');  //should cause compilation error

[Edit by MK to answer some questions]:

The calls are always in the same scope, right one after the other like above.
A macro solution would be acceptable too
Non-type template parameters are acceptable too

How far away form each other can those calls be? Are they always in a same scope? Are you ok with a macro solution? — HolyBlackCat, Jan 30 '18 at 22:29
Is OK if the character are passed as template not-type parameters? I mean: `verify<'a'>(); verify<'b'>(), verify<'c'>(), vefify<'a'>();` — max66, Jan 30 '18 at 22:56
Will this `verify` syntax need to be used at global/namespace scope and/or within a class definition and/or in a function block? — aschepler, Jan 30 '18 at 23:02
@GuillaumeRacicot - never underestimate the power of the dark side of constexpr... I mean... maybe you're right, it's too dangerous. But the real problem is that I can't make it work. — max66, Jan 30 '18 at 23:16
There's probably a way similar to [this](https://stackoverflow.com/q/6166337/3002139). — Baum mit Augen, Jan 30 '18 at 23:37
Nice one. Attempting this without MACRO's is a nifty puzzle. Maybe not do-able. If not, prove it. — Jive Dadson, Jan 31 '18 at 08:48
I don't think this can be done with function calls. The reason is that function calls are expressions. Even if `f` is overloaded, the type of `verify('a')` is the same as `verify('b')`. You can't cause a type error in the calling context. It's the same expression in either case, so not a syntax error either. And since we know that the first `verify('a')` call must succeed, but the second must not, we know that the error can't occur inside the selected overload of `verify( )`. So I basically run out of types of errors. The macro solution works because declarations are not expressions. — MSalters, Jan 31 '18 at 12:08

score 13 · Answer 1 · answered Jan 31 '18 at 00:24

13

Not exactly what you asked for, but given your constraints (same scope and macro solution is acceptable) you can try something like this:

#define verify(x) class _tmp_##x {};

Example:

int main()
{
    verify(a);
    verify(b);
    verify(a);
    return 0;
}

Will fail compilation due to redefinition of local class _tmp_a.

answered Jan 31 '18 at 00:24

Patryk Obara

1,847
14
19

1

Short and sweet. – Jive Dadson Jan 31 '18 at 11:34
This is a thing of beauty – CoffeeTableEspresso May 11 '20 at 08:08

Yakk - Adam Nevraumont · Answer 2 · 2018-01-31T00:48:47.257

template<std::size_t X>
struct line_t { enum{value=X}; constexpr line_t(){} };

template<std::size_t line, char c>
constexpr std::integral_constant<bool, false> use_flag(
  std::integral_constant<char,c>, line_t<line>
) { return {}; }

#define FLAG_USE( C ) \
constexpr std::integral_constant<bool, true> use_flag( \
  std::integral_constant<char,C>, line_t<__LINE__> \
) { return {}; }

template<char c, std::size_t line>
constexpr std::size_t count_uses( line_t<line> from, line_t<1> length ){
  return use_flag( std::integral_constant<char, c>{}, from )();
}
template<char c, std::size_t line>
constexpr std::size_t count_uses( line_t<line> from, line_t<0> length ){
  return 0;
}

template<char c, std::size_t f, std::size_t l>
constexpr std::size_t count_uses(line_t<f> from, line_t<l> length ){
  return count_uses<c>( from, line_t< l/2 >{} )+ count_uses<c>( line_t< f+l/2>{}, line_t<(l+1)/2>{} );
}

#define UNIQUE(C) \
  FLAG_USE(C) \
  static_assert( count_uses<C>( line_t<0>{}, line_t<__LINE__+1>{} )==1, "too many" )

This should work in files of size 2^100s, until your compiler runs out of memory, as counting is log-depth recursion.

The type line_t enables deferred ADL lookup of use_flag until we invoke count_uses. We do a binary tree sum over every overload of use_flag, one per line per character in the file.

Live example.

Nice. You can fold FLAG_USE into UNIQUE, leaving only one MACRO. As a puzzle, can you reduce that to none? — Jive Dadson, Jan 31 '18 at 09:06
@jive you can always just expand them. You do need `__LINE__` for this technique. There are some dangerous stateful metaprogramming techniques that do not need `__LINE__`, but they are fragile and rely on basically standard defects. — Yakk - Adam Nevraumont, Jan 31 '18 at 11:32

checking uniqueness of characters at compile time

2 Answers2