У меня есть большой вектор элементов, принадлежащих определенному классу.
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;
}
