迭代器中的代理对象

Question

我有属于某个 class 的项目的大向量。

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

同一个class_id可以在vector中出现多次，构造一次vector再按class_id排序。所以相同 class 的所有元素在向量中彼此相邻。

我稍后必须根据 class 处理项目，即。我更新了相同 class 的所有项目，但我没有修改不同 class 的任何项目。由于我必须对所有项目执行此操作，并且代码可以简单地并行化，因此我想将 Microsoft PPL 与 Concurrency::parallel_for_each() 一起使用。因此我需要一个迭代器并想出了一个前向迭代器，它 returns 以某个 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> { /* ... */ };

现在我可以遍历所有 classes 并像这样更新项目。

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++);
}

它使用后增量（因此返回一个临时迭代器），取消引用该临时迭代器并获取取消引用项的地址。这仅在通过取消引用临时对象返回的项目存在时才有效，即。基本上如果它直接指向容器。所以解决这个问题很容易，尽管每个 class 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

对于你的直接问题，不，迭代器不一定是与任何类型的容器相关的东西。 About only requirements for an iterator 是：

可复制构造、可复制分配和可破坏
支持equality/inequality
可取消引用

迭代器不一定必须绑定到特定容器（参见 generators），因此不能说 "it has to has same type as container" - 因为一般情况下没有容器。

看来，hover，拥有一个自定义迭代器 class 对你的情况来说可能实际上是一种矫枉过正。原因如下：

在 C++ 中，array/vector 结束迭代器是指向最后一项末尾后面的迭代器。

给定 "classes"（在您的定义中）A、B、C 等对象的向量，填充如下：

AAAAAAABBBBBBBBBBBBCCCCCCCD.......

您可以只使用常规向量迭代器作为范围的开始和结束：

AAAAAAABBBBBBBBBBBBCCCCCCCD......Z
^      ^           ^      ^       ^
i1     i2          i3     i4      iN

对于您在此处看到的 4 个迭代器，以下是正确的：

i1 是 begin class A
i2 是 class A 的 end 迭代器和 class B

begin

i3 是 class B 的 end 迭代器和 class C 的 begin 迭代器等

因此，对于每个 class，您可以有一对迭代器，它们分别是 class 范围的开始和结束。

因此，您的处理非常简单：

for(auto it = i1; i!= i2; i++) processA(*it);
for(auto it = i2; i!= i3; i++) processB(*it);
for(auto it = i3; i!= i4; i++) processC(*it);

每个循环都是可并行化的。

parallel_for_each (i1; i2; processA);
parallel_for_each (i2; i3; processB);
parallel_for_each (i3; i4; processC);

要使用基于范围的 for，您可以引入替代范围 class:

class vector_range<T> {
    public:
        vector<T>::const_iterator begin() {return _begin;};
        vector<T>::const_iterator end() {return _end;};
    // Trivial constructor filling _begin and _end fields
}

也就是说，您实际上不需要代理迭代器来并行化循环 - C++ 迭代器的完成方式已经完美地涵盖了您的情况。

Answer 2

当您编写代理迭代器时，reference 类型应该是 class 类型，正是因为它可以比派生它的迭代器更有效。因此，对于代理迭代器，在实例化 std::iterator 基类时应将 Reference 模板参数指定为 class 类型，通常与值类型相同：

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::operator&:[=25= 来利用它]

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

迭代器中的代理对象

Proxy objects in iterators

c++

iterator

language-lawyer

ppl

可编译示例：