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

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

0 голосов
/ 05 января 2019

Я пытаюсь создать несколько итераторов для более сложного диапазона (используя библиотеку 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 - пытаясь вернуть итератор для пары с наивысшим значением в перекрестном произведении. При поиске наибольшего значения вам нужно сохранить итератор для текущего лучшего кандидата. Он не может измениться во время поиска, и было бы неудобно управлять итераторами, если вам нужна копия диапазона (как предложено в одном из ответов).

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

Ответы [ 3 ]

0 голосов
/ 08 января 2019

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

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; 
}
0 голосов
/ 25 января 2019

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

Вся проблема здесь заключается в том, что 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 s. Конечно, это может быть очень легко реализовано вручную, но все же было бы удобно иметь это в стандартной библиотеке. Я могу только догадываться, почему этого не существует. Возможно, одна из причин заключается в том, что value_type требует возможности создания копии, поскольку InputIterator не требуется для возврата ссылок на элементы, и это может, в свою очередь, быть нелогичным, если алгоритм max создает копию ...

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

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

Очевидно, 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 с
  • требуется меньше O(n²) памяти

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

Резюме

Вы говорите

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

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

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

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

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

0 голосов
/ 05 января 2019

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

...