特定のクラスに属するアイテムの大きなベクトルがあります。
struct item {
int class_id;
//some other data...
};
同じものclass_idがベクトルに複数回出現する可能性があり、ベクトルは一度構築されてから でソートされclass_idます。したがって、同じクラスのすべての要素は、ベクトル内で隣り合っています。
後でクラスごとにアイテムを処理する必要があります。同じクラスのすべてのアイテムを更新しますが、別のクラスのアイテムは変更しません。すべてのアイテムに対してこれを行う必要があり、コードは簡単に並列化できるため、Microsoft PPL を で使用したいと考えましたConcurrency::parallel_for_each()。class_idしたがって、イテレータが必要であり、特定のas プロキシ オブジェクトを持つすべてのアイテムの範囲を返すフォワード イテレータを考え出しました。プロキシは単なる astd::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 行目以降にある次のコードに問題があることがわかりました。
// Add a batch of work items to this functor's array
for (unsigned int _Index=0; (_Index < _Size) && (_First != _Last); _Index++)
{
_M_element[_M_len++] = &(*_First++);
}
postincrement を使用し (一時イテレータが返されるため)、その一時イテレータを逆参照し、逆参照されたアイテムのアドレスを取得します。これは、一時オブジェクトの逆参照によって返されたアイテムが存続する場合にのみ機能します。基本的に、コンテナを直接指している場合。したがって、クラスごとのstd::for_each作業ループを for ループに置き換える必要がありますが、これを修正するのは簡単です。
//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()少なくとも、ランダム アクセスまたはフォワード イテレータのいずれかが期待されることを除いて、イテレータ要件に関するドキュメントは見つかりませんでした。前方イテレータとベクトルに関する質問を見てきましたが、イテレータの参照型が であるため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's 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;
}