c++ - 迭代器中的代理对象

Question

我有属于某个类别的大量项目 vector 。

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

相同的class_id可以在vector中出现多次，vector构造一次后按class_id排序。因此同一类的所有元素在 vector 中彼此相邻。

我稍后必须处理每个类的项目，即。我更新了同一类的所有项目，但没有修改不同类的任何项目。由于我必须对所有项目执行此操作，并且代码可以简单地并行化，因此我想将 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 时，代码崩溃了。调试后发现问题出在_Parallel_for_each_helper in ppl.h at line 2772 ff.

// 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() 的迭代器要求的文档，除了需要随机访问或前向迭代器。我看过the question about forward iterators and vector但由于我的迭代器的引用类型是 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 存储了一个 pointer 数组，并希望以后能够间接指向它们:

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

由于 PPL 不检查 pointer 实际上是一个指针，我们可以通过提供一个带有 operator* 的代理指针并重载 class_range 来利用它: :运算符&:

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