使用范围与 lambda 内联初始化的向量初始化
Vector initialisation using ranges vs lambda inline initialisation
我想通过转换另一个向量来初始化一个向量。我用两种内联初始化方式进行了测试,一种是转换后的 std::vector
.
一个使用 lambda 内联初始化(std::transform
):
std::vector<int> foo(100,42);
const auto fooTimesTwo = [&]{
std::vector<int> tmp(foo.size());
std::transform(foo.begin(), foo.end(), tmp.begin(), convert);
return tmp;
}();
另一个 - 使用 std::ranges::views::transform
:
std::vector<int> foo(100,42);
auto transform_range = (foo | std::ranges::views::transform(convert));
std::vector<int> fooTimesTwo {
transform_range.begin(),
transform_range.end()
};
我预计这两种向量初始化方式应该具有相似的性能,但出于某种原因,传统 std::transform
解决方案的基准比第二种方式快得多(快 9.7 倍 -> https://quick-bench.com/q/3PSDRO9UbMNunUpdWGNShF49WlQ).
我的问题是:
- 我使用
std::ranges::views::transform
不正确吗?
- 为什么它运行得这么慢?
旁注 - 可以使用 boost::make_transform_iterator
完成,但我无法在 quick-bench 上检查它,因为它们不支持提升。所以我不确定这种解决方案的效率。
Why does it work so much slower?
您 运行 遇到的问题是 C++98/C++17 迭代器模型与 C++20 迭代器模型之间的差异之一。 X
成为前向迭代器的旧要求之一 was:
if X
is a mutable iterator, reference
is a reference to T
; if X
is a constant iterator, reference
is a reference to const T
,
也就是说,迭代器的 reference
类型 必须 是一个真正的引用。它不能是代理引用或纯右值。 reference
为纯右值的任何 迭代器自动仅作为输入迭代器。
C++20 中没有这样的要求。
因此,如果您查看 foo | std::ranges::views::transform(convert)
,这是一个纯右值范围 int
。在 C++20 迭代器模型中,这是一个随机访问范围。但在 C++17 中,因为我们处理的是纯右值,所以这只是一个 输入范围 .
vector
的iterator-pair构造函数不是基于C++20迭代器模型,而是基于C++98/C++17迭代器模型。它使用的是对迭代器类别的旧理解,而不是新理解。 C++20 范围适配器非常努力地确保它们对旧的迭代器模型做“正确的事情”。当检查为 C++20 时,我们的适应范围确实将自己正确地宣传为随机访问,而当检查为 C++17 时,它确实将自己宣传为随机访问:
void f(std::vector<int> v) {
auto r = v | std::views::transform(convert);
using R = decltype(r);
static_assert(std::ranges::random_access_range<R>);
static_assert(std::same_as<std::input_iterator_tag,
std::iterator_traits<std::ranges::iterator_t<R>>::iterator_category>);
}
那么当您将两个输入迭代器传递给 vector
的迭代器对构造函数时会发生什么?好吧,它不能预先分配一个巨大的块(我们不能在这里做 last - first
因为它是一个输入迭代器,具有“大小的哨兵”可能独立于遍历类别的概念也是一个新的C++20迭代器模型中的东西)...相反,它基本上是这样做的:
for (; first != last; ++first) {
push_back(*first);
}
没有比输入迭代器更好的了。但这是非常低效的,因为我们最终做了八次分配,而不是一次。
在range-v3中,你可以这样做:
auto result = foo | ranges::views::transform(convert)
| ranges::to<std::vector>();
to
算法理解C++20迭代器模型,在这里提前预留做正确的事情。然而,to
的局限性很大,因为它是一个外部库,我们不能只修改标准库类型来选择加入它。我们希望在 C++23 中有一个 std::ranges::to
来改进标准库容器,以更好地做到这一点。在这一点上,这个解决方案将比你原来的解决方案更好,因为 std::vector<int> foo(tmp.size())
本身就很浪费,因为必须对一块内存进行零初始化,然后立即覆盖它。
与此同时,我确实想知道保留此 reference
必须参考要求的一般价值(很少有人知道,可能更少人依赖:最大的价值是可能只是知道 operator->()
可以 return &operator*()
?).
例如,std::vector<bool>
已经对此撒了谎,并宣传自己是随机访问 C++17 范围。
标准库实现应该能够更好地处理这种情况。他们应该能够安全地检查 C++20 迭代器概念,并因此做出一些智能的事情。在这种情况下,我们有 C++20 随机访问迭代器,因此 vector
应该 能够在这种情况下有效地构造自身。已提交 100070.
我想通过转换另一个向量来初始化一个向量。我用两种内联初始化方式进行了测试,一种是转换后的 std::vector
.
一个使用 lambda 内联初始化(std::transform
):
std::vector<int> foo(100,42);
const auto fooTimesTwo = [&]{
std::vector<int> tmp(foo.size());
std::transform(foo.begin(), foo.end(), tmp.begin(), convert);
return tmp;
}();
另一个 - 使用 std::ranges::views::transform
:
std::vector<int> foo(100,42);
auto transform_range = (foo | std::ranges::views::transform(convert));
std::vector<int> fooTimesTwo {
transform_range.begin(),
transform_range.end()
};
我预计这两种向量初始化方式应该具有相似的性能,但出于某种原因,传统 std::transform
解决方案的基准比第二种方式快得多(快 9.7 倍 -> https://quick-bench.com/q/3PSDRO9UbMNunUpdWGNShF49WlQ).
我的问题是:
- 我使用
std::ranges::views::transform
不正确吗? - 为什么它运行得这么慢?
旁注 - 可以使用 boost::make_transform_iterator
完成,但我无法在 quick-bench 上检查它,因为它们不支持提升。所以我不确定这种解决方案的效率。
Why does it work so much slower?
您 运行 遇到的问题是 C++98/C++17 迭代器模型与 C++20 迭代器模型之间的差异之一。 X
成为前向迭代器的旧要求之一 was:
if
X
is a mutable iterator,reference
is a reference toT
; ifX
is a constant iterator,reference
is a reference toconst T
,
也就是说,迭代器的 reference
类型 必须 是一个真正的引用。它不能是代理引用或纯右值。 reference
为纯右值的任何 迭代器自动仅作为输入迭代器。
C++20 中没有这样的要求。
因此,如果您查看 foo | std::ranges::views::transform(convert)
,这是一个纯右值范围 int
。在 C++20 迭代器模型中,这是一个随机访问范围。但在 C++17 中,因为我们处理的是纯右值,所以这只是一个 输入范围 .
vector
的iterator-pair构造函数不是基于C++20迭代器模型,而是基于C++98/C++17迭代器模型。它使用的是对迭代器类别的旧理解,而不是新理解。 C++20 范围适配器非常努力地确保它们对旧的迭代器模型做“正确的事情”。当检查为 C++20 时,我们的适应范围确实将自己正确地宣传为随机访问,而当检查为 C++17 时,它确实将自己宣传为随机访问:
void f(std::vector<int> v) {
auto r = v | std::views::transform(convert);
using R = decltype(r);
static_assert(std::ranges::random_access_range<R>);
static_assert(std::same_as<std::input_iterator_tag,
std::iterator_traits<std::ranges::iterator_t<R>>::iterator_category>);
}
那么当您将两个输入迭代器传递给 vector
的迭代器对构造函数时会发生什么?好吧,它不能预先分配一个巨大的块(我们不能在这里做 last - first
因为它是一个输入迭代器,具有“大小的哨兵”可能独立于遍历类别的概念也是一个新的C++20迭代器模型中的东西)...相反,它基本上是这样做的:
for (; first != last; ++first) {
push_back(*first);
}
没有比输入迭代器更好的了。但这是非常低效的,因为我们最终做了八次分配,而不是一次。
在range-v3中,你可以这样做:
auto result = foo | ranges::views::transform(convert)
| ranges::to<std::vector>();
to
算法理解C++20迭代器模型,在这里提前预留做正确的事情。然而,to
的局限性很大,因为它是一个外部库,我们不能只修改标准库类型来选择加入它。我们希望在 C++23 中有一个 std::ranges::to
来改进标准库容器,以更好地做到这一点。在这一点上,这个解决方案将比你原来的解决方案更好,因为 std::vector<int> foo(tmp.size())
本身就很浪费,因为必须对一块内存进行零初始化,然后立即覆盖它。
与此同时,我确实想知道保留此 reference
必须参考要求的一般价值(很少有人知道,可能更少人依赖:最大的价值是可能只是知道 operator->()
可以 return &operator*()
?).
std::vector<bool>
已经对此撒了谎,并宣传自己是随机访问 C++17 范围。
标准库实现应该能够更好地处理这种情况。他们应该能够安全地检查 C++20 迭代器概念,并因此做出一些智能的事情。在这种情况下,我们有 C++20 随机访问迭代器,因此 vector
应该 能够在这种情况下有效地构造自身。已提交 100070.