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

o2g1uqev  于 9个月前  发布在  其他
关注(0)|答案(3)|浏览(96)

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

constexpr auto make_vector() { 
  // complex calculation here
  return std::vector{1, 2, 3}; 
}

constexpr auto make_array() {
  const auto vec = make_vector();
  std::array<int, make_vector().size()> result{};

  std::copy(vec.cbegin(), vec.cend(), result.begin());
  return result;
}

int main() {
  constexpr auto result = make_array(); // std::array<int, 3>{1, 2, 3}
}

字符串
我理解为什么不能用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,你可以这样做转换:

template<typename N, N ...ns>
consteval auto seq2array(std::integer_sequence<N, ns...>) {
      return std::array{ns...};
}
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

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


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

template<typename N, N ...ns, N ...ms>
consteval auto cat(std::integer_sequence<N, ns...>, std::integer_sequence<N, ms...>) {
    return std::integer_sequence<N, ns..., ms...>{};
}
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>>);
static_assert(std::is_same_v<decltype(cat(std::index_sequence<1, 2>{}, std::index_sequence<>{})), std::index_sequence<1, 2>>);
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>>);


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

template<typename Seq, typename Pred>
struct Filter {};

template<typename N, N n, N ... ns, typename Pred>
struct Filter<std::integer_sequence<N, n, ns...>, Pred> {
    using head = std::integer_sequence<N, n>;
    using tail = typename Filter<std::integer_sequence<N, ns...>, Pred>::type;
    using type = std::conditional_t<Pred{}(n), decltype(cat(head{}, tail{})), tail>;
};

template<typename N, typename Pred>
struct Filter<std::integer_sequence<N>, Pred> {
    using head = std::integer_sequence<N>;
    using type = head;
};

template<typename N, N ...ns, typename Pred>
consteval auto filter(std::integer_sequence<N, ns...>, Pred) {
    return typename details::Filter<std::integer_sequence<N, ns...>, Pred>::type{};
}
static_assert(std::is_same_v<decltype(filter(std::index_sequence<>{}, f)), std::index_sequence<>>);
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)可以这样写

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


像这样使用

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


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

wd2eg0qa

wd2eg0qa3#

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

template <int N>
constexpr std::size_t upper_bound_for_make_vector(); //Should be cheap to calculate

template <int N>
constexpr std::vector<int> make_vector();

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

template <int N>
constexpr auto make_array_size_pair() {
  const auto vec = make_vector();
  std::array<int, upper_bound_for_make_vector<N>()> result{};

  std::copy_n(vec.cbegin(), vec.size(), result.begin());
  return std::pair{result, vec.size()};
}


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

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


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

template <int N>
constexpr auto make_array(){
  return trim_array<make_array_size_pair<N>()>();
}


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

相关问题