Почему итераторы `std :: views :: смежные итераторы увеличивают все базовые итераторы вместо использования более эффекти ⇐ C++

[Anonymous]

В C ++ 23, std :: views :: Прилегающий предоставляет скользящее окно n элементов в диапазоне. Его итератор обычно хранит n итераторы в базовом диапазоне. При реализации оператора этого итератора ++ я могу придумать два подхода:

[*] увеличение All : текущий подход, используемый основными реализациями (LibStdc ++, MSVC). Оператор ++ просто увеличивает все n хранимых базовых итераторов.// Simplified logic
for (auto & iter : current_window_iterators_) {
++iter;
}


Приращение последнего + shift : потенциально более эффективный подход. Поскольку следующее окно - это просто текущее окно, скользящее на одно, его итераторы (IT_2, IT_3, ..., IT_N, ++ IT_N) . Это может быть реализовано с помощью n-1 перемещения итератора (например, std :: shift_left ) и только one приращение базового итератора. Например, итератор для std :: views :: filter должен найти следующий элемент, который удовлетворяет предикату, который может быть дорогой. В таком трубопроводе, как источник | std :: Views :: Filter (...) | std :: views :: Прилегающий , подход «Приращение All» будет вызовать дорогостоящий приращение Filter 5 раз для каждого шага redcent_view итератор. Подход «Приращение последнего + сдвига» будет вызвать его только один раз. (Если Filter_View прикован в цепочке после Transform_view, я наблюдал, как время вызывания функции преобразования растет в геометрической прогрессии.) < /P>
По моему опыту, движения итератора почти всегда дешевы. Почему текущие стандартные реализации библиотеки используют подход «Приращение все», который кажется менее эффективным? Есть ли требование стандартного соответствия C ++, которые мне не хватает? Или это просто выбор реализации для простоты? < /P>
Benchmark < /h3>
код: < /p>
#include
#include
#include
#include
#include
#include

template
struct IterHelper
{
template
struct IterBase
{
using value_type = std::array;
using reference_type = std::array;
using difference_type = std::ptrdiff_t;
using iterator_category = std::forward_iterator_tag;

std::array current;

IterBase(BaseIter it)
{
for (auto & iter : current)
{
iter = it;
++it;
}
}

auto operator*() const
{
return std::apply([](auto && ... it)
{
return std::array{ *it ...};
}, current);
}

bool operator==(IterBase const &) const = default;

D operator++(int)
{
auto & d = static_cast(*this);
auto temp = d;
++d;
return temp;
}

static auto make_range(BaseIter begin, std::ptrdiff_t len)
{
return std::ranges::subrange(D{ begin }, std::unreachable_sentinel) | std::views::take(len);
};
};

struct IterIncEach
: public IterBase
{
using Base = IterBase;
using Base::Base;

IterIncEach & operator++()
{
for (auto & it : Base::current)
++it;
return *this;
}
using Base::operator++;
};

struct IterShftInc
: public IterBase
{
using Base = IterBase;
using Base::Base;

IterShftInc & operator++()
{
auto & current = Base::current;
if constexpr (N >= 2)
{
for (size_t i = 0; i < N - 2; ++i)
current = std::move(current[i + 1]);
current[N - 2] = current[N - 1];
}
++(current[N - 1]);
return *this;
}
using Base::operator++;
};
};

#include
#include
#include

int main()
{
auto is_prime = [](int n)
{
for (int i = 2; i < n; ++i)
if (n % i == 0)
return false;
return true;
};
auto base_view = std::views::iota(100000) | std::views::filter(is_prime);
using BaseIter = std::ranges::iterator_t;
BaseIter iter0 = base_view.begin();

constexpr size_t Width = 3;
constexpr size_t Length = 100;
using Helper = IterHelper;
auto range_inc_each = Helper::IterIncEach::make_range(iter0, Length);
auto range_shft_inc = Helper::IterShftInc::make_range(iter0, Length);

using Result = std::vector;
Result res_inc_each; res_inc_each.reserve(Length);
Result res_shft_inc; res_shft_inc.reserve(Length);

using Clock = std::chrono::high_resolution_clock;
auto t0 = Clock::now();
for (auto i : range_inc_each)
{
res_inc_each.push_back(i);
}
auto t1 = Clock::now();
for (auto i : range_shft_inc)
{
res_shft_inc.push_back(i);
}
auto t2 = Clock::now();
std::print("IterIncEach: {}\n", t1 - t0);
std::print("IterShftInc: {}\n", t2 - t1);
std::print("equal: {}\n", res_inc_each == res_shft_inc);
}
< /code>
Результат: < /p>
IterIncEach: 73330162ns
IterShftInc: 24381067ns
equal: true


Подробнее здесь: https://stackoverflow.com/questions/797 ... tors-inste