c++ - 如何在不复制的情况下从 N 维容器中获取可迭代范围？

Question

假设我有一个嵌套结构，比如说一些包含其他类的类:

struct Obj
{
  std::vector<T> mVector; // T is large
};

std::vector<Obj> myVector;

我想使用一些现有的函数，我们称它为 std::find_if，以查找符合某些条件的 T 的出现，等等。许多标准库函数 ( std::find_if included) 需要可迭代范围作为输入，因此只需将 myVector 迭代器传递到这些函数中将导致遍历行，而不是元素。

性能也是一个问题，所以我不想重建整个指针 vector ，或者更糟的是，复制对象本身只是为了跨元素运行这些函数。

使用 boost::adaptors 完成各种有用的任务，例如过滤或间接容器而不先重建它们，我想我基本上希望能够做这样的事情:

auto myRange = boost::adaptors::nested(myVector, functor);

其中仿函数是一些 lambda，它从我的矩阵的每一行中提取嵌套范围，如下所示:

auto functor = [](auto& it) { return boost::iterator_range(it.begin(), it.end(); }

当然，boost::adaptors::nested 不存在。那么，如何在不复制 Obj 并且不先创建另一个展平容器的情况下展平这个二维数组呢？答案应该相当高效，同时尽量减少代码和样板文件的数量。

Answer 1

答案确实是写一个适配器。它将需要跟踪外部容器中的迭代器和内部容器中的迭代器。

这是一个示例实现，它只支持 forward_iterator 语义和 const 访问——我会把更完整的实现留给你!

#include <cstddef>
#include <iterator>

template <typename V>
struct flat_view {
    V &v;

    typedef typename V::value_type inner_type;
    typedef typename inner_type::value_type value_type;
    typedef typename inner_type::reference reference;
    typedef typename inner_type::const_reference const_reference;

    struct const_iterator {
        typedef std::forward_iterator_tag iterator_category;
        typedef typename std::iterator_traits<typename inner_type::const_iterator>::value_type value_type;
        typedef typename std::iterator_traits<typename inner_type::const_iterator>::pointer pointer;
        typedef typename std::iterator_traits<typename inner_type::const_iterator>::reference reference;
        typedef ptrdiff_t difference_type;

        typename inner_type::const_iterator i,i_end;
        typename V::const_iterator o,o_end;
        bool at_end;

        const_iterator(): at_end(true) {}
        const_iterator(typename V::const_iterator vb,typename V::const_iterator ve):
            o(vb), o_end(ve), at_end(vb==ve)
        {
            if (!at_end) {
                i=vb->begin();
                i_end=vb->end();
            }
        }

        const_iterator &operator++() {
            if (at_end) return *this;

            if (i!=i_end) ++i;
            while (!at_end && i==i_end) {
                if (++o==o_end)
                    at_end=true;
                else {
                    i=o->begin();
                    i_end=o->end();
                }
            }
            return *this;
        }

        const_iterator &operator++(int) {
            iterator c(*this);
            ++*this;
            return c;
        }

        bool operator==(const const_iterator &x) const {
            return (at_end && x.at_end) || (o==x.o && i==x.i);
        }

        bool operator!=(const const_iterator &x) const { return !(*this==x); }

        reference operator*() const { return *i; }
        pointer operator->() const { return &*i; }
    };

    typedef const_iterator iterator;

    explicit flat_view(V &v_): v(v_) {};

    iterator begin() const { return iterator(v.begin(),v.end()); }
    iterator end() const { return iterator(); }

    const_iterator cbegin() const { return const_iterator(v.begin(),v.end()); }
    const_iterator cend() const { return const_iterator(); }
};

template <typename V>
flat_view<V> make_flat_view(V &v) { return flat_view<V>(v); }

快速演示:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<std::vector<double>> v={
        {1,2,3,4},
        {},
        {10,9,8,7},
        {5,6}
    };

    auto f=make_flat_view(v);

    std::copy(f.begin(),f.end(),std::ostream_iterator<double>(std::cout," "));
    std::cout << "\n";
}

产生:

1 2 3 4 10 9 8 7 5 6