c++ 可以在编译时将std::vector转换为std::array而不需要两次生成vector吗?

o2g1uqev  于 2024-01-09  发布在  其他
关注(0)|答案(3)|浏览(128)

我正在使用std::vector在编译时计算一些数据,并希望将结果作为数组返回,以便在运行时进一步使用。
下面是一个我到目前为止所做的简化示例。代码按预期编译和工作。

  1. constexpr auto make_vector() {
  2. // complex calculation here
  3. return std::vector{1, 2, 3};
  4. }
  5. constexpr auto make_array() {
  6. const auto vec = make_vector();
  7. std::array<int, make_vector().size()> result{};
  8. std::copy(vec.cbegin(), vec.cend(), result.begin());
  9. return result;
  10. }
  11. int main() {
  12. constexpr auto result = make_array(); // std::array<int, 3>{1, 2, 3}
  13. }

字符串
我理解为什么不能用vec.size()来表示数组大小,也理解为什么make_vector().size()会产生一个编译时常量,只是这样做似乎不是正确的方法。
有没有办法避免调用make_vector两次?我在这里错过了一个基本概念?

643ylb08

643ylb081#

有没有办法避免调用make_vector两次?我在这里错过了一个基本概念?
基本问题是std::vector不是一个文字类型,所以你不能简单地将它存储在一个constexpr变量中,在这个变量中,它的大小和内容可以任意使用。一个std::vector只能在一个常量表达式中临时存在(1)。
在第一个常量表达式中,.size()不是一个常量表达式,并且没有办法“提升它到那个状态”。因此,你不知道你正在创建的数组的大小,并且向量内容在第一次被浪费了(2)。
这个问题也是P0784: More constexpr containers(3)的动机:
除此之外,缺少可变大小的[constexpr]容器迫使它们在实现中使用原始的固定大小的数据结构,并对输入的JSON字符串进行两次解析;一次是确定数据结构的大小,另一次是将JSON解析为这些结构。
您不是第一个遇到这个问题的人,您必须耐心等待C委员会和编译器开发人员解决这个问题。
解决这个问题的最新论文是P1974: Non-transient constexpr allocation。关键问题是任何在编译时分配并存储在constexpr变量中的T*这个恒定性问题意味着constexpr std::vector<std::string>将包含可变/不可变指针的混合(类似于char ** const),这打破了我们可以完全省略delete并保留静态内存的假设。
(1)原因是即使std::vector可以在常量表达式中使用new,所有内存必须在常量表达式结束之前释放。这被称为“ transient 分配”。
(2)正如评论者@HolyBlackCat所指出的,编译器可能会记住对make_vector()的调用,这样即使您调用了两次,函数也不需要计算两次。
(3)这篇论文已经被C
20接受,但还没有解决浪费容器创建的问题。

b91juud3

b91juud32#

输出大小不能与实际计算分开计算。
很好,但是因为它是在编译时,所以你可以用std::integer_sequence(或者std::index_sequence,如果元素的类型是std::size_t)和一些元编程来完成所有这些。
然后,如果你真的需要一个std::array,你可以这样做转换:

  1. template<typename N, N ...ns>
  2. consteval auto seq2array(std::integer_sequence<N, ns...>) {
  3. return std::array{ns...};
  4. }
  5. static_assert(seq2array(std::index_sequence<1, 2, 3>{}) == std::array<std::size_t, 3>{1, 2, 3});

字符串
现在,如何生成std::index_sequence取决于“复杂计算”是什么。
Weijun Zhou在评论中提出了一个玩具的例子:
make_vector(int n)可以是一个函数,它返回一个包含所有不大于n的非负数k的向量,这些非负数满足 predicate f(k),其中f是一个非常昂贵的函数。
要怎么做呢?
好吧,这只是意味着用 predicate f过滤从0n的数字序列。
让我们发明一个 predicate

  1. constexpr auto f = [](auto k) {
  2. // expensive compuptation
  3. return k % 2 == 0;
  4. };


对于后者,我们需要一种递归的方法,将 predicate 应用于序列的第一个元素,以决定是否保留它,分别将其变为单例或空序列,并与过滤后的序列的其余部分连接。
所以我们首先需要的是一种连接序列的方法。它是:

  1. template<typename N, N ...ns, N ...ms>
  2. consteval auto cat(std::integer_sequence<N, ns...>, std::integer_sequence<N, ms...>) {
  3. return std::integer_sequence<N, ns..., ms...>{};
  4. }
  5. static_assert(std::is_same_v<decltype(cat(std::index_sequence<1, 2>{}, std::index_sequence<3, 4>{})), std::index_sequence<1, 2, 3, 4>>);
  6. static_assert(std::is_same_v<decltype(cat(std::index_sequence<1, 2>{}, std::index_sequence<>{})), std::index_sequence<1, 2>>);
  7. static_assert(!std::is_same_v<decltype(cat(std::index_sequence<2, 2>{}, std::index_sequence<3, 4>{})), std::index_sequence<1, 2, 3, 4>>);


最后,我们需要过滤工具。

  1. template<typename Seq, typename Pred>
  2. struct Filter {};
  3. template<typename N, N n, N ... ns, typename Pred>
  4. struct Filter<std::integer_sequence<N, n, ns...>, Pred> {
  5. using head = std::integer_sequence<N, n>;
  6. using tail = typename Filter<std::integer_sequence<N, ns...>, Pred>::type;
  7. using type = std::conditional_t<Pred{}(n), decltype(cat(head{}, tail{})), tail>;
  8. };
  9. template<typename N, typename Pred>
  10. struct Filter<std::integer_sequence<N>, Pred> {
  11. using head = std::integer_sequence<N>;
  12. using type = head;
  13. };
  14. template<typename N, N ...ns, typename Pred>
  15. consteval auto filter(std::integer_sequence<N, ns...>, Pred) {
  16. return typename details::Filter<std::integer_sequence<N, ns...>, Pred>::type{};
  17. }
  18. static_assert(std::is_same_v<decltype(filter(std::index_sequence<>{}, f)), std::index_sequence<>>);
  19. static_assert(std::is_same_v<decltype(filter(std::index_sequence<1, 2, 3, 4>{}, f)), std::index_sequence<2, 4>>);


有了这些,我们的make_vector(我将其重命名为make_array)可以这样写

  1. template<std::size_t n>
  2. consteval auto make_array() {
  3. return seq2array(filter(std::make_integer_sequence<std::size_t, n>{}, f));
  4. }


像这样使用

  1. static_assert(make_array<10>() == std::array<std::size_t, 5>{0, 2, 4, 6, 8});


请注意,上面定义的抽象filtercat非常通用,可以在许多其他情况下使用,因此它们可以是库的一部分。

展开查看全部
wd2eg0qa

wd2eg0qa3#

Jarod's excellent answer已经详细解释了为什么在当前的c++语言标准中,没有额外的辅助函数就不可能将向量转换为数组。然而,如果可以用相对简单的方式计算向量大小的上限,那么仍然可以通过首先构造更大的数组来将向量转换为数组。本质上,这是在构造一个文字类型,它包含了向量的所有信息,并且可以在以后用于构造实际的数组。
假设我们有

  1. template <int N>
  2. constexpr std::size_t upper_bound_for_make_vector(); //Should be cheap to calculate
  3. template <int N>
  4. constexpr std::vector<int> make_vector();

字符串
我们可以通过稍微修改OP代码的实现来构建一个可以用作NTTP的文字类型。

  1. template <int N>
  2. constexpr auto make_array_size_pair() {
  3. const auto vec = make_vector();
  4. std::array<int, upper_bound_for_make_vector<N>()> result{};
  5. std::copy_n(vec.cbegin(), vec.size(), result.begin());
  6. return std::pair{result, vec.size()};
  7. }


然后我们可以使用结果作为NTTP来构造实际的数组,

  1. template <auto arr_pair>
  2. constexpr auto trim_array(){
  3. std::array<int, arr_pair.second> result{};
  4. static_assert(arr_pair.first.size() >= result.size());
  5. std::copy_n(arr_pair.first.cbegin(), result.size(), result.begin());
  6. return result;
  7. }


有了这些helper,我们就可以编写make_array函数了。

  1. template <int N>
  2. constexpr auto make_array(){
  3. return trim_array<make_array_size_pair<N>()>();
  4. }


尽管该解决方案不受模板参数总数的限制(可以低至256),但可能需要使trim_arrayconsteval以防止生成没有其他用途的超长符号名称。

展开查看全部

相关问题