我有一个属于某个类的项目的大向量。
struct item {
int class_id;
//some other data...
};
同样class_id的在向量中可以出现多次，向量构造一次后排序class_id。因此，同一类的所有元素在向量中彼此相邻。
我稍后必须处理每个班级的项目，即。我更新了同一类的所有项目，但我不修改不同类的任何项目。由于我必须对所有项目执行此操作，并且代码可轻松并行化，因此我想将 Microsoft PPL 与Concurrency::parallel_for_each(). 因此，我需要一个迭代器并提出了一个前向迭代器，它返回具有某个class_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 行的以下代码。
// 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++);
}
它使用后增量（因此返回一个临时迭代器），取消引用该临时迭代器并获取取消引用项的地址。这仅在通过取消引用临时对象返回的项目存在时才有效，即。基本上，如果它直接指向容器。所以解决这个问题很容易，尽管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;
}