Finding duplicates in array at compile time

Question

I am trying to learn some more modern C++ practices such as templates, and I decided to create a naive and simple command line argument parser that mostly works at compile time and I am already running into issues with constexpr, essentially all I want to do is check for duplicate entries at compile time (doing it at run time is trivial).

First, I have a structure that holds a single configuration:

struct Arg_Opt_Tuple {
  std::string_view mc{}; // multichar ie "help" 
  char sc{}; // singlechar ie 'h' 
  bool is_flag{}; 
};

Now let's say I wanted to create a function (or eventually a constructor to an object) that returns a fixed size std::array, but also does some checking at compile time for duplicates or empty values, my goal is to have it called in some fashion similar to this:

constexpr auto ARG_COUNT = 4U;
constexpr auto opts = checked_arr<ARG_COUNT>(
  Arg_Opt_Tuple{"hello", 'h', false},
  Arg_Opt_Tuple{"world", 'g', true},
  Arg_Opt_Tuple{"goodbye", 'h', false}, // <- static_assert('h' == 'h')
  Arg_Opt_Tuple{"hello", 'r', false} // <- static_assert(sv.compare("hello") == 0)
);

My first attempt was to use a std::initializer_list but ran into some issues and after doing some googling came to the conclusion it's not the correct thing to do here in conjunction with constexpr. My current attempt involves a variadic template:

template <std::size_t N, typename... T>
constexpr std::array<Arg_Opt_Tuple, N> checked_arr(T... list) {
  static_assert(N == sizeof...(T));
  return {list...};
}

This works but is completely superfluous to just initalizing an array, I really want this to be doing some compile time checking. For duplicates or erroneous values at run time is easy, you can just loop through and compare or do std::find or what not, however none of this seems to work at compile time, ie (I know it's ugly but you get the point):

for (std::size_t src_i = 0; src_i < ARG_COUNT; ++src_i) {
  for (std::size_t check_i = 0; check_i < ARG_COUNT; ++check_i) {
    // skip checking self
    if (check_i == src_i) {
      continue;
    }
    // doesnt work obviously
    static_assert(opts[src_i].sc != opts[check_i].sc);
  }
}

So how difficult would this be to achieve? Is this bad design? Any pointers would be lovely.

Answer 1

For duplicates or erroneous values at run time is easy, you can just loop through and compare or do std::find or what not, however none of this seems to work at compile time

Plain loops do work:

template <typename T> constexpr bool has_duplicates(const T *array, std::size_t size)
{
    for (std::size_t i = 1; i < size; i++)
        for (std::size_t j = 0; j < i; j++)
            if (array[i] == array[j])
                return 1;
    return 0;
}

constexpr int foo[] = {1, 2, 3, 4};
static_assert(!has_duplicates(foo, 4));

If you want to have static_assert inside of a function, you need to pass the array as a template parameter instead:

template <auto &array> constexpr void assert_has_no_duplicates()
{
    constexpr std::size_t size = std::extent_v<std::remove_reference_t<decltype(array)>>;
    static_assert(!has_duplicates(array, size));
}

constexpr int foo[] = {1, 2, 3, 4};

int main()
{
    assert_has_no_duplicates<foo>();
}

Or, if you prefer std::arrays:

template <auto &array> constexpr void assert_has_no_duplicates()
{
    static_assert(!has_duplicates(array.data(), array.size()));
}

constexpr std::array<int,4> foo = {1, 2, 3, 4};

int main()
{
    assert_has_no_duplicates<foo>();
}

Answer 2

Not exactly what you asked but... if you check duplicates inside checked_arr() and you throw an exception if you find one, you have an exception when you execute checked_arr() runtime and a compilation error when you execute it compile-time.

I mean... you can write

template <std::size_t N0 = 0u, typename ... Ts,
          std::size_t N = (N0 > sizeof...(Ts)) ? N0 : sizeof...(Ts)>
constexpr auto checked_arr (Ts ... args)
 {
   std::array<Arg_Opt_Tuple, N> arr {args...};

   for ( auto i = 0u ; i < sizeof...(Ts) ; ++i )
      for ( auto j = 0u; j < sizeof...(Ts) ; ++j )
         if ( (i != j) && (arr[i].sc == arr[j].sc) )
             throw std::runtime_error("equal sc");

   return arr;
 }

(off topic: observe the trick with N0 and N: so you have to explicit N0 only when greater as sizeof...(Ts))

If you call

constexpr auto opts = checked_arr(
   Arg_Opt_Tuple{"hello", 'h', false},
   Arg_Opt_Tuple{"world", 'g', true},
   Arg_Opt_Tuple{"goodbye", 'h', false},
   Arg_Opt_Tuple{"hello", 'r', false}
);

you get a compilation error; in g++

prog.cc:26:42: error: expression '<throw-expression>' is not a constant expression
   26 |       throw std::runtime_error("equal sc");
      |                                          ^

The following is a full compiling C++17 example (not compiling if you place a collision in opts)

#include <array>
#include <string>
#include <exception>

struct Arg_Opt_Tuple {
  std::string_view mc{}; // multichar ie "help" 
  char sc{}; // singlechar ie 'h' 
  bool is_flag{}; 
};

template <std::size_t N0 = 0u, typename ... Ts,
          std::size_t N = (N0 > sizeof...(Ts)) ? N0 : sizeof...(Ts)>
constexpr auto checked_arr (Ts ... args)
 {
   std::array<Arg_Opt_Tuple, N> arr {args...};

   for ( auto i = 0u ; i < sizeof...(Ts) ; ++i )
      for ( auto j = 0u; j < sizeof...(Ts) ; ++j )
         if ( (i != j) && (arr[i].sc == arr[j].sc) )
             throw std::runtime_error("equal sc");

   return arr;
 }

int main ()
 {
    constexpr auto opts = checked_arr(
       Arg_Opt_Tuple{"hello", 'h', false},
       Arg_Opt_Tuple{"world", 'g', true},
       Arg_Opt_Tuple{"goodbye", 'i', false},
       Arg_Opt_Tuple{"hello", 'r', false}
    );
 }

But I suggest to simply initialize the array as constexpr variable

constexpr std::array opts {
    Arg_Opt_Tuple{"hello", 'h', false},
    Arg_Opt_Tuple{"world", 'g', true},
    Arg_Opt_Tuple{"goodbye", 'i', false},
    Arg_Opt_Tuple{"hello", 'r', false}
};

and check it calling a constexpr function inside a static_assert()

static_assert( checkOpts(opts) );

where checOpts() is something as

template <std::size_t N>
constexpr bool checkOpts (std::array<Arg_Opt_Tuple, N> const & arr)
 {
   for ( auto i = 0u ; i < N ; ++i )
      for ( auto j = 0u; j < N ; ++j )
         if ( (i != j) && (arr[i].sc == arr[j].sc) )
             return false;

   return true;
 }