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

Question

我正在尝试学习一些现代C++实践，例如模板，我决定创建一个天真而简单的命令行参数解析器，大部分工作都在编译时完成，但是我已经遇到了关于constexpr的问题，本质上我想要做的就是在编译时检查重复条目（在运行时进行操作是微不足道的）。

首先，我有一个结构体来保存单个配置：

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

现在假设我想创建一个函数（或最终是对象的构造函数），它返回一个固定大小的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等方式，但似乎没有一种方法可以在编译时实现。即使（我知道这很丑陋，但你懂我的意思）：

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

这个要实现起来有多难？这是一个糟糕的设计吗？如果有指导意见，那就太好了。

- Tom Lulz

---

请问您能否澄清一些问题？首先，Arg_Opt_Tuple代表什么？什么是“配置”？checked_arr的作用是什么？从checked_arr返回的数组代表什么？ - Anonymous1847

Answer 1

在运行时处理重复或错误值很容易，你只需要循环比较或使用std::find等方法，但是这些方法在编译时都不起作用。

普通的循环确实可以工作：

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，需要将数组作为模板参数传递进去：

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::array：

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

- HolyBlackCat

---

谢谢，放错了 static_assert 是我的问题的根源。 - Tom Lulz

@TomLulz 的确如此。这是因为函数参数在函数内部永远不会被视为 constexpr。 - HolyBlackCat

没有预先条件检查，如果大小为0或数组为nullptr，则会导致严重故障。 - Shivendra Agarwal

模板 <typename T> constexpr bool has_duplicates(const T* array, std::size_t size) { if (array == nullptr || size <= 1) return false; for (std::size_t i = 0; i < size-1; i++) for (std::size_t j = i+1; j < size; j++) if (array[i] == array[j]) return true; return false; } - Shivendra Agarwal

有没有什么想法可以改进，以便在静态断言发生时指示哪个元素是重复的？我想知道是否可以通过constexpr使循环展开并直接在重复检查上进行断言，如果编译器可以提供任何有关检查失败位置的信息。 - Crog

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

- max66