在编译时查找数组中的重复项

Question

我正在尝试学习一些更现代的 C++ 实践，例如模板，我决定创建一个天真简单的命令行参数解析器，它主要在编译时运行，我已经运行遇到了问题使用 constexpr，基本上我想做的就是在编译时检查重复条目（在运行时检查是微不足道的）。

首先，我有一个包含单一配置的结构：

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

现在假设我想创建一个 returns 固定大小 std::array 的函数（或最终是一个对象的构造函数），但还要在编译时检查重复项或空项价值观，我的目标是以类似于这样的方式调用它：

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

我的第一次尝试是使用 std::initializer_list 但运行解决了一些问题，在进行了一些谷歌搜索后得出的结论是，在这里与 constexpr 结合使用是不正确的。我目前的尝试涉及可变参数模板：

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

这可行，但对于初始化数组来说完全多余，我真的希望它能进行一些编译时检查。对于运行时的重复值或错误值很容易，您可以循环并比较或执行 std::find 或其他操作，但是 none 似乎在编译时有效，即（我知道这很难看，但你明白了）：

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

那么实现起来有多难呢？这是糟糕的设计吗？任何指针都会很可爱。

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

普通循环确实有效：

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

如果你想要 static_assert inside 函数，你需要将数组作为模板参数传递：

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

或者，如果您更喜欢 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

不完全是你问的，但是...如果你检查 checked_arr() 中的重复项，如果你找到一个，你会抛出一个异常，当你执行 checked_arr() 运行时和编译时，你有一个异常编译时执行时出错。

我的意思是...你可以写

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

（题外话：观察 N0 和 N 的技巧：所以只有在大于 sizeof...(Ts) 时才必须显式 N0）

如果你打电话

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

你得到一个编译错误；在 g++

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

以下是完整的C++17编译示例（如果在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}
    );
 }

但我建议简单地将数组初始化为 constexpr 变量

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

并检查它在 static_assert()

中调用 constexpr 函数

static_assert( checkOpts(opts) );

其中 checOpts() 是

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

在编译时查找数组中的重复项

Finding duplicates in array at compile time

c++

variadic-templates

constexpr

c++11