Объекты прокси в итераторах

У меня есть большой вектор элементов, принадлежащих определенному классу.

struct item {
    int class_id;
    //some other data...
};

Тот же class_id может появляться несколько раз в векторе, и вектор строится один раз, а затем сортируется по классу_id. Таким образом, все элементы одного класса находятся рядом друг с другом в векторе.

Позже мне приходится обрабатывать элементы в классе, т.е. Я обновляю все элементы одного класса, но я не изменяю ни один элемент другого класса. Поскольку я должен делать это для всех элементов, и код тривиально параллелизуем, я хотел использовать Microsoft PPL с Concurrency:: parallel_for_each(). Поэтому мне нужен итератор и придумал передовой итератор, который возвращает диапазон всех элементов с определенным классом_id как прокси-объект. Прокси - это просто std:: pair, а прокси - тип значения итератора.

using item_iterator = std::vector<item>::iterator;
using class_range = std::pair<item_iterator, item_iterator>;

//iterator definition
class per_class_iterator : public std::iterator<std::forward_iterator_tag, class_range> { /* ... */ };

К настоящему моменту мне удалось перебрать все мои классы и обновить такие элементы.

std::vector<item> items;
//per_class_* returns a per_class_iterator
std::for_each(items.per_class_begin(), items.per_class_end(),
[](class_range r) 
{ 
    //do something for all items in r 
    std::for_each(r.first, r.second, /* some work */);
});

При замене std:: for_each Concurrency:: parallel_for_each код разбился. После отладки я обнаружил, что проблема заключается в следующем коде в _Parallel_for_each_helper в ppl.h в строке 2772 ff.

// Add a batch of work items to this functor array
for (unsigned int _Index=0; (_Index < _Size) && (_First != _Last); _Index++)
{
    _M_element[_M_len++] = &(*_First++);
}

Он использует postincrement (поэтому возвращается временный итератор), разыгрывает временный итератор и берет адрес разыменованного элемента. Это работает только в том случае, если элемент, возвращаемый путем разыменования временного объекта, сохраняется, т.е. в основном, если он указывает прямо в контейнер. Поэтому исправление этого легко, хотя рабочий цикл std:: for_each в классе должен быть заменен на цикл.

//it := iterator somewhere into the vector of items (item_iterator)
for(const auto cur_class = it->class_id; cur_class == it->class_id; ++it)
{
    /* some work */
}

Мой вопрос заключается в том, что если возвращать объекты-прокси, то, как я это сделал, является нарушением стандарта или предположением о том, что все итераторские разложения в постоянные данные были сделаны Microsoft для их библиотеки, но не документированы. По крайней мере, я не смог найти документацию по требованиям итератора для parallel_for_each(), за исключением того, что ожидается случайный доступ или прямой итератор. Я видел вопрос о форвардных итераторах и векторе, но поскольку мой ссылочный тип iterator - const value_type & Я все еще думаю, что мой итератор в порядке по стандарту. Итак, форвардный итератор, возвращающий прокси-объект, все еще действительный итератор вперёд? Или по-другому, нормально ли для итератора иметь тип значения, отличный от типа, который фактически хранится где-то в контейнере?

Компилируемый пример:

#include <vector>
#include <utility>
#include <cassert>
#include <iterator>
#include <memory>
#include <algorithm>
#include <iostream>

#include <ppl.h>


using identifier = int;
struct item
{
    identifier class_id;
    // other data members
    // ...

    bool operator<(const item &rhs) const
    {
        return class_id < rhs.class_id;
    }

    bool operator==(const item &rhs) const
    {
        return class_id == rhs.class_id;
    }

    //inverse operators omitted
};
using container = std::vector<item>;
using item_iterator = typename container::iterator;
using class_range = std::pair<item_iterator, item_iterator>;

class per_class_iterator : public std::iterator<std::forward_iterator_tag, class_range>
{
public:
    per_class_iterator() = default;
    per_class_iterator(const per_class_iterator&) = default;
    per_class_iterator& operator=(const per_class_iterator&) = default;

    explicit per_class_iterator(container &data) :
        data_(std::addressof(data)),
        class_(equal_range(data_->front())), //this would crash for an empty container. assume it not.
        next_(class_.second)
    {
        assert(!data_->empty()); //a little late here
        assert(std::is_sorted(std::cbegin(*data_), std::cend(*data_)));
    }

    reference operator*()
    {
        //if data_ is unset the iterator is an end iterator. dereferencing end iterators is bad.
        assert(data_ != nullptr);
        return class_;
    }

    per_class_iterator& operator++()
    {
        assert(data_ != nullptr);

        //if we are at the end of our data
        if(next_ == data_->end())
        {
            //reset the data pointer, ie. make iterator an end iterator
            data_ = nullptr;
        }
        else
        {
            //set to the class of the next element
            class_ = equal_range(*next_);
            //and update the next_ iterator
            next_ = class_.second;
        }

        return *this;
    }

    per_class_iterator operator++(int)
    {
        per_class_iterator tmp{*this};
        ++(*this);
        return tmp;
    }

    bool operator!=(const per_class_iterator &rhs) const noexcept
    {
        return (data_ != rhs.data_) ||
            (data_ != nullptr && rhs.data_ != nullptr && next_ != rhs.next_);
    }

    bool operator==(const per_class_iterator &rhs) const noexcept
    {
        return !(*this != rhs);
    }

private:
    class_range equal_range(const item &i) const
    {
        return std::equal_range(data_->begin(), data_->end(), i);
    }

    container* data_ = nullptr;
    class_range class_;
    item_iterator next_;
};

per_class_iterator per_class_begin(container &c)
{
    return per_class_iterator{c};
}

per_class_iterator per_class_end()
{
    return per_class_iterator{};
}

int main()
{
    std::vector<item> items;
    items.push_back({1});
    items.push_back({1});
    items.push_back({3});
    items.push_back({3});
    items.push_back({3});
    items.push_back({5});
    //items are already sorted

//#define USE_PPL
#ifdef USE_PPL
    Concurrency::parallel_for_each(per_class_begin(items), per_class_end(),
#else
    std::for_each(per_class_begin(items), per_class_end(),
#endif
        [](class_range r)
        {
            //this loop *cannot* be parallelized trivially
            std::for_each(r.first, r.second,
                [](item &i)
                {
                    //update item (by evaluating all other items of the same class) ...
                    //building big temporary data structure for all items of same class ...
                    //i.processed = true;
                    std::cout << "item: " << i.class_id << '\n';
                });
        });

    return 0;
}

Ответы

Ответ 1

Когда вы пишете итератор прокси-сервера, тип reference должен быть типом класса, именно потому, что он может пережить итератор, из которого он получен. Итак, для прокси-итератора при создании базы std::iterator следует указать параметр шаблона reference как тип класса, как правило, такой же, как тип значения:

class per_class_iterator : public std::iterator<
    std::forward_iterator_tag, class_range, std::ptrdiff_t, class_range*, class_range>
                                                                          ~~~~~~~~~~~

К сожалению, PPL не увлекается прокси-итераторами и разбивает компиляцию:

ppl.h(2775): error C2338: lvalue required for forward iterator operator *
ppl.h(2772): note: while compiling class template member function 'Concurrency::_Parallel_for_each_helper<_Forward_iterator,_Function,1024>::_Parallel_for_each_helper(_Forward_iterator &,const _Forward_iterator &,const _Function &)'
        with
        [
            _Forward_iterator=per_class_iterator,
            _Function=main::<lambda_051d98a8248e9970abb917607d5bafc6>
        ]

На самом деле это static_assert:

    static_assert(std::is_lvalue_reference<decltype(*_First)>::value, "lvalue required for forward iterator operator *");

Это связано с тем, что вложенный class _Parallel_for_each_helper хранит массив pointer и ожидает, что он сможет косвенно их позже:

typename std::iterator_traits<_Forward_iterator>::pointer    _M_element[_Size];

Так как PPL не проверяет, что pointer на самом деле является указателем, мы можем использовать это, указав прокси-указатель на operator* и перегружая class_range::operator&:

struct class_range_ptr;
struct class_range : std::pair<item_iterator, item_iterator> {
    using std::pair<item_iterator, item_iterator>::pair;
    class_range_ptr operator&();
};
struct class_range_ptr {
    class_range range;
    class_range& operator*() { return range; }
    class_range const& operator*() const { return range; }
};
inline class_range_ptr class_range::operator&() { return{*this}; }

class per_class_iterator : public std::iterator<
    std::forward_iterator_tag, class_range, std::ptrdiff_t, class_range_ptr, class_range&>
{
    // ...

Это отлично работает:

item: item: 5
1
item: 3item: 1

item: 3
item: 3
Press any key to continue . . .

Ответ 2

Для вашего прямого вопроса нет, итератор не должен быть чем-то, что связано с любым контейнером. О требованиях только для итератора должны быть:

  • быть готовым к копированию, копировать и разрушать
  • поддержка равенства/неравенства
  • быть разыменованным

Итератор необязательно должен быть привязан к определенному контейнеру (см. generators), и поэтому нельзя сказать, что "это должен иметь тот же тип, что и контейнер" - поскольку в общем случае нет контейнера.

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

В С++ конечный итератор массива/вектора - это итератор, указывающий сразу за концом последнего элемента.

Для вектора объектов "классов" (в вашем определении) A, B, C и т.д., заполненных следующим образом:

AAAAAAABBBBBBBBBBBBCCCCCCCD.......

Вы можете просто использовать регулярные векторные итераторы, которые будут действовать, когда ваш диапазон начинается и заканчивается:

AAAAAAABBBBBBBBBBBBCCCCCCCD......Z
^      ^           ^      ^       ^
i1     i2          i3     i4      iN

Для 4 итераторов, которые вы видите здесь, верно следующее:

  • i1 - это тег begin для класса A
  • i2 является end итератором для класса A и begin итератором для класса B
  • i3 - итератор end для классов B и begin для класса C и т.д.

Следовательно, для каждого класса вы можете иметь пару итераторов, которые являются началом и концом соответствующего класса.

Следовательно, ваша обработка так же тривиальна, как:

for(auto it = i1; i!= i2; i++) processA(*it);
for(auto it = i2; i!= i3; i++) processB(*it);
for(auto it = i3; i!= i4; i++) processC(*it);

Каждая петля тривиально параллелизуема.

parallel_for_each (i1; i2; processA);
parallel_for_each (i2; i3; processB);
parallel_for_each (i3; i4; processC);

Чтобы использовать диапазон for на основе диапазона, вы можете ввести класс замещающего диапазона:

class vector_range<T> {
    public:
        vector<T>::const_iterator begin() {return _begin;};
        vector<T>::const_iterator end() {return _end;};
    // Trivial constructor filling _begin and _end fields
}

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