Несколько итераторов в сложный диапазон

Question

Я пытаюсь получить несколько итераторов для более сложного диапазона (используя библиотеку range-v3) - вручную реализуем декартово произведение, используя filter, for_each а также yield, Тем не менее, когда я пытался удерживать несколько итераторов в таком диапазоне, они имели общее значение. Например:

#include <vector>
#include <iostream>
#include <range/v3/view/for_each.hpp>
#include <range/v3/view/filter.hpp>

int main() {
    std::vector<int> data1{1,5,2,7,6};
    std::vector<int> data2{1,5,2,7,6};
    auto range =
            data1
            | ranges::v3::view::filter([](int v) { return v%2; })
            | ranges::v3::view::for_each([&data2](int v) {
                return data2 | ranges::v3::view::for_each([v](int v2) {
                    return ranges::v3::yield(std::make_pair(v,v2));
                });
            });
    auto it1 = range.begin();
    for (auto it2 = range.begin(); it2 != range.end(); ++it2) {
        std::cout << "[" << it1->first << "," << it1->second << "] [" << it2->first << "," << it2->second << "]\n";
    }
    return 0;
}

Я ожидал итератор it1 продолжать указывать на начало диапазона, в то время как итератор it2 проходит через всю последовательность К моему удивлению, it1 также увеличивается! Я получаю следующий вывод:

[1,1] [1,1]
[1,5] [1,5]
[1,2] [1,2]
[1,7] [1,7]
[1,6] [1,6]
[5,1] [5,1]
[5,5] [5,5]
[5,2] [5,2]
[5,7] [5,7]
[5,6] [5,6]
[7,1] [7,1]
[7,5] [7,5]
[7,2] [7,2]
[7,7] [7,7]
[7,6] [7,6]

• Это почему?
• Как я могу избежать этого?
• Как я могу сохранить несколько независимых итераторов, указывающих в разных местах диапазона?
• Должен ли я реализовывать декартово произведение по-другому? (это мой предыдущий вопрос)

---

Хотя это не отражено в MCVE выше, рассмотрим вариант использования, когда кто-то пытается реализовать нечто подобное std::max_element - попытка вернуть итератор для пары с самым высоким значением в перекрестном произведении. При поиске наибольшего значения вам нужно сохранить итератор для текущего лучшего кандидата. Он не может измениться во время поиска, и будет неудобно управлять итераторами, если вам нужна копия диапазона (как предлагается в одном из ответов).

Материализация всего перекрестного продукта тоже не вариант, так как требует много памяти. В конце концов, весь смысл использования диапазонов с фильтрами и других оперативных преобразований состоит в том, чтобы избежать такой материализации.

Answer 1

Что здесь происходит?

Вся проблема здесь заключается в том, что std::max_element требует, чтобы его аргументы были LecacyForwardIterators, а диапазоны, созданные ranges::v3::yield очевидно (очевидно?) предоставляют только LecacyInputIterators. К сожалению, в документах range-v3 явно не упоминаются категории итераторов, которых можно ожидать (по крайней мере, я не обнаружил, что они упоминались). Это действительно было бы огромным улучшением, поскольку все стандартные библиотечные алгоритмы явно указывают, какие категории итераторов им требуются.

В частном случае std::max_element Вы не первый, кто наткнулся на это нелогичное требование ForwardIterator а не просто InputIterator см. Почему для std::max_element требуется ForwardIterator? например. Таким образом, это имеет смысл, потому что std::max_element не (несмотря на название, предлагающее это) не возвращает элемент max, но итератор для элемента max. Следовательно, именно многопроходная гарантия отсутствует на InputIterator чтобы сделать std::max_element работать с этим.

По этой причине многие другие стандартные библиотечные функции не работают с std::max_element либо, например, std:: istreambuf_iterator, что очень жаль: вы просто не можете получить элемент max из файла с существующей стандартной библиотекой! Вы либо должны сначала загрузить весь файл в память, либо использовать свой собственный алгоритм max.

В стандартной библиотеке просто отсутствует алгоритм, который действительно возвращает элемент max, а не итератор, указывающий на элемент max. Такой алгоритм может работать с InputIterator также. Конечно, это может быть очень легко реализовано вручную, но все же было бы удобно иметь это в стандартной библиотеке. Я могу только догадываться, почему этого не существует. Может быть, одна из причин заключается в том, что это потребует value_type быть копируемым, потому что InputIterator не требуется возвращать ссылки на элементы, и это может быть в свою очередь нелогичным для алгоритма max, чтобы сделать копию...

---

Итак, теперь относительно ваших актуальных вопросов:

Почему это? (т.е. почему ваш диапазон только возвращает InputIterator s?)

Очевидно, что yield создает ценности на лету. Это сделано специально, это одна из причин, по которой нужно использовать yield: не нужно создавать (и, следовательно, хранить) диапазон заранее. Следовательно, я не вижу, как yield может быть реализован таким образом, чтобы он соответствовал многопроходной гарантии, особенно вторая пуля вызывает у меня головную боль:

• Если a и b сравниваются равными (a == b контекстуально преобразуется в true), то либо они не являются разыменованными, либо * a и * b являются ссылками, связанными с одним и тем же объектом

Технически я мог представить, что можно реализовать yield таким образом, что все итераторы, созданные из одного диапазона, совместно используют общее внутреннее хранилище, которое заполняется на лету во время первого обхода. Тогда разные итераторы могут дать вам одинаковые ссылки на базовые объекты. Но потом std::max_element будет молча потреблять O(n²) память (все элементы вашего декартового произведения). Так что, по моему мнению, определенно лучше этого не делать, а вместо этого заставлять пользователей материализовать диапазон самостоятельно, чтобы они знали, что это происходит.

Как я могу избежать этого?

Ну, как уже сказал metalfox, вы можете скопировать ваш вид, что приведет к различным диапазонам и, следовательно, независимым итераторам. Тем не менее, это не сделало бы std::max_element Работа. Итак, учитывая природу yield К сожалению, ответ на этот вопрос: вы просто не можете избежать этого с yield или любой другой метод, который создает ценности на лету.

Как я могу сохранить несколько независимых итераторов, указывающих в разных местах диапазона?

Это связано с предыдущим вопросом. По сути, этот вопрос отвечает сам себе: если вы хотите указать независимые итераторы в разных местах, эти места должны существовать где-то в памяти. Итак, вам нужно материализовать хотя бы те элементы, которые когда-то имели итератор, указывающий на них, что в случае std::max_element означает, что вы должны материализовать их всех.

Должен ли я реализовывать декартово произведение по-другому?

Я могу представить много разных реализаций. Но ни один из них не сможет предоставить оба этих свойства вместе:

• вернуть ForwardIterator s
• требуют меньше, чем O(n²) объем памяти

Технически можно было бы реализовать итератор, специализированный для использования с std::max_element Это означает, что он хранит в памяти только текущий максимальный элемент, чтобы на него можно было сослаться... Но это было бы несколько смешно, не так ли? Мы не можем ожидать, что библиотека общего назначения, такая как range-v3, предложит такие узкоспециализированные категории итераторов.

---

Резюме

Ты говоришь

В конце концов, я не думаю, что мой вариант использования является настолько редким выбросом, и диапазоны планируется добавить в стандарт C++20 - поэтому должен быть какой-то разумный способ достичь этого без ловушек...

Я определенно согласен, что "это не редкий выброс"! Однако это не обязательно означает, что "должен быть какой-то разумный способ достичь этого без ловушек". Рассмотрим, например, NP-сложные проблемы. Это не редкий выброс, чтобы столкнуться с тем. Тем не менее, невозможно (если P=NP) решить их за полиномиальное время. И в вашем случае это просто невозможно использовать std::max_element без ForwardIterator s. И это не возможно реализовать ForwardIterator (как определено в стандартной библиотеке) на декартовом произведении без потребления O(n²) объем памяти.

Для частного случая std::max_element Я бы предложил реализовать собственную версию, которая возвращает элемент max, а не итератор, указывающий на него.

Однако, если я правильно понимаю ваш вопрос, ваше беспокойство носит более общий характер и std::max_element это просто пример. Итак, я должен разочаровать вас. Даже с существующей стандартной библиотекой некоторые тривиальные вещи невозможны из-за несовместимых категорий итераторов (опять же, std::istreambuf_iterator это существующий пример). Итак, если добавится range-v3, таких примеров просто будет больше.

Итак, наконец, моя рекомендация - просто по возможности использовать свои собственные алгоритмы и в противном случае проглотить таблетку материализации представления.

Answer 2

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

int main() {
    std::vector<int> data1{1,5,2,7,6};
    std::vector<int> data2{1,5,2,7,6};
    auto range =
            data1
            | ranges::v3::view::filter([](int v) { return v%2; })
            | ranges::v3::view::for_each([&data2](int v) {
                return data2 | ranges::v3::view::for_each([v](int v2) {
                    return ranges::v3::yield(std::make_pair(v,v2));
                });
            });

    auto range1= range;         // Copy the view adaptor
    auto it1 = range1.begin();

    for (auto it2 = range.begin(); it2 != range.end(); ++it2) {
        std::cout << "[" << it1->first << "," << it1->second << "] [" << it2->first << "," << it2->second << "]\n";
    }

    std::cout << '\n';
    for (; it1 != range1.end(); ++it1) { // Consume the copied view
        std::cout << "[" << it1->first << "," << it1->second << "]\n";
    }
    return 0;
}

Другим вариантом будет материализация представления в контейнер, как упомянуто в комментариях.

---

Принимая во внимание вышеупомянутое ограничение однопроходных представлений, не очень сложно реализовать max_elementфункция, которая возвращает итератор, с важным недостатком, заключающимся в необходимости вычислять последовательность полтора раза.

Вот возможная реализация:

template <typename InputRange,typename BinaryPred = std::greater<>>
auto my_max_element(InputRange &range1,BinaryPred &&pred = {}) -> decltype(range1.begin()) {
    auto range2 = range1;
    auto it1 = range1.begin();
    std::ptrdiff_t pos = 0L;

    for (auto it2 = range2.begin(); it2 != range2.end(); ++it2) {
        if (pred(*it2,*it1)) {
            ranges::advance(it1,pos);   // Computing again the sequence as the iterator advances!
            pos = 0L;
            }
        ++pos;
        }
    return it1; 
}

Answer 3

Итератор - это указатель на элемент в векторе, в этом случае он указывает на начало вектора. И, следовательно, если вы пытаетесь указать итератору одно и то же местоположение вектора, они будут одинаковыми. Однако у вас может быть несколько итераторов, указывающих на разные местоположения вектора. Надеюсь, что это ответ на ваш вопрос.