迭代器中的代理对象

Question

我有一个属于某个类的大项目向量.

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 */);
});

当用Concurrency :: parallel_for_each替换std :: for_each时,代码崩溃了.调试后,我发现问题是ppl.h中第2772行的_Parallel_for_each_helper中的以下代码.

// 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;
}

Answer 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存储了一个pointers数组，并希望以后能够间接地调用它们：

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 . . .