Как `partial_sum` диапазона-v3 не противоречит семантике ссылок, не являющихся владельцами?

Рассмотрите Как мне написать конвейер диапазона, который использует временные контейнеры?. Вопрос в том, как построить представление, преобразующее каждый элемент T с помощью некоторой заданной функции.

std::vector<T> f(T t);

соблюдая ограничение (заимствование из верхнего ответа), которое

Представление — это облегченная оболочка, которая представляет представление базовой последовательности элементов каким-то настраиваемым образом, не видоизменяя и не копируя его. Представления недороги в создании и копировании и имеют семантику ссылок без владения.

В принципе, все ответы, похоже, согласны с тем, что из-за этого ограничения это невозможно сделать через представление.


Я не понимаю, как это согласуется с библиотекой, поддерживающей partial_sum.

Рассмотрим следующее прославленное целое число:

#include <vector>
#include <iostream>
#include <memory>
#include <range/v3/all.hpp>

using namespace ranges;

struct glorified_int {
    explicit glorified_int(int i) : m_i{std::make_shared<int>(i)} {}
    operator int() const { return *m_i; }
    std::shared_ptr<int> m_i;
};

glorified_int operator+(const glorified_int &lhs, const glorified_int &rhs) {
    glorified_int ret{(int)lhs + (int)rhs};
    return ret;
}

По сути, он просто оборачивает int в класс, хранящий его в std::shared_ptr, что позволяет инициализировать, извлекать и добавлять. В.р.т. семантика невладения ссылкой, я не вижу принципиальной разницы между ней и контейнером, таким как std::vector.

У Range, похоже, нет проблем с применением partial_sum к этому:

int main() {
    std::vector<glorified_int> vi{ glorified_int{1}, glorified_int{2} };
    for(const auto &ps: vi | view::partial_sum())
        std::cout << ps << std::endl;

Распечатывает

$ ./a.out
1 
3

Разве (прославленное целое число) 3 здесь не временно? Это, конечно, не часть оригинальной последовательности. Кроме того, частичная сумма, очевидно, является преобразованием с сохранением состояния, так как диапазон может гарантировать, что

Представления недороги в создании и копировании и имеют семантику ссылок без владения.

Копировать представление так же дорого, как и объект накопления.

Обратите внимание, что также нет проблем с дальнейшим связыванием этого (т. Е. Это не действие):

    vi | view::partial_sum() | view::take(10);

Какая тогда разница?


Полный код

#include <vector>
#include <iostream>
#include <memory>
#include <range/v3/all.hpp>

using namespace ranges;

struct glorified_int {
    explicit glorified_int(int i) : m_i{std::make_shared<int>(i)} {}
    operator int() const { return *m_i; }
    std::shared_ptr<int> m_i;
};

glorified_int operator+(const glorified_int &lhs, const glorified_int &rhs) {
    glorified_int ret{(int)lhs + (int)rhs};
    return ret;
}

int main() {
    std::vector<glorified_int> vi{ glorified_int{1}, glorified_int{2} };
    for(const auto &ps: vi | view::partial_sum())
        std::cout << ps << std::endl;
    vi | view::partial_sum() | view::take(10);
}

person Ami Tavory    schedule 01.10.2016    source источник


Ответы (1)


Что делает представление представлением, так это то, что оно не принимает и не требует владения, копирования или изменения каких-либо элементов входного диапазона. Но представление не обязательно должно иметь какое-либо состояние. Даже take() или filter() имеют некоторое состояние (счетчик и предикат соответственно).

В этом конкретном случае partial_sum не обязательно должен владеть какими-либо элементами входного диапазона. Это работа входного диапазона. Их также не нужно копировать или изменять. Ему просто нужно отслеживать свое собственное состояние — текущую сумму (optional<glorified_int>) и двоичную функцию, выполняющую суммирование (plus). Он владеет одним из своих собственных объектов, но этот объект полностью находится за пределами входного диапазона. Это по-прежнему делает его представлением, просто с состоянием.

Ты пишешь:

Копировать представление так же дорого, как и объект накопления.

Это верно. Но это также верно для многих взглядов. transform() копировать так же дорого, как и функцию, которую мы используем для преобразования представления, может быть, у вас есть огромное чудовище с состоянием, дорогое, выделяющее память.

Когда Эрик пишет о дешевом создании и копировании, я полагаю, что он имеет в виду создание и копирование всего входного диапазона для создания нового диапазона. В то время как partial_sum() необходимо сохранить текущую сумму, что в вашем случае недешево, поскольку этот элемент требует выделения, это все же намного дешевле, чем написание основанного на действии partial_sum:

// cheap version
for(const auto &ps: vi | view::partial_sum()) { ... }

// expensive version
std::vector<glorified_int> partial_sums;
if (!vi.empty()) {
    auto it = vi.begin();
    partial_sums.emplace_back(*it++);
    for (; it != vi.end(); ++it) {
        partial_sums.emplace_back(*it + partial_sums.back());
    }
}
for (const auto &ps : partial_sums) { ... }

Очевидно, что нам не нужен весь вектор partial_sums, чтобы делать то, что мы хотим (если он нам и нужен, ну, никак иначе). Представление предлагает нам дешевый способ просмотра частичных сумм.

person Barry    schedule 01.10.2016
comment
Спасибо за ответ! Однако, по той же аналогии, почему состояние в вышеупомянутом вопросе не может быть вектором, сформированным путем применения функции к разыменованному итератору? Другими словами, почему накопление не считается временно принадлежащим, а результат применения функции к разыменованному итератору считается наоборот? - person Ami Tavory; 01.10.2016
comment
@AmiTavory Потому что гипотетический view::join() должен был бы взять на себя ответственность за весь диапазон ввода, чтобы правильно передать его вперед. - person Barry; 01.10.2016
comment
Спасибо еще раз. Я начинаю смутно понимать, что вы имеете в виду. Будет читать источник соединения (который я пропустил) и это. - person Ami Tavory; 01.10.2016
comment
Отличный ответ. Чтобы уточнить, дешевый в контексте просмотров означает O (1) по отношению к длине просматриваемого диапазона. - person Casey; 01.10.2016
comment
несколько связано: github/range-v3/issues/92: текущий single_view должен быть действием не представление, ответ Эрика: реальное различие заключается в том, что копирование и присвоение диапазонов должно быть O (1); то есть их сложность не должна зависеть от количества элементов в диапазоне - person tamas.kenez; 03.10.2016
comment
Если состояние частичной суммы представляет собой одно число (sum_ в реализация), это подразумевает O(N) развертки от начала до требуемой позиции (канал к view::reverse будет O(N^2) и т. д.). Как это выражается в понятиях диапазона? Что-то вроде partial_sum является итерируемым вперед? Можно ли использовать std::vector<T> или std::shared_ptr<std::vector<T>> (и, таким образом, получить произвольный доступ за счет дополнительных усилий при создании) без нарушения требований к диапазону? - person davidhigh; 29.08.2017