如何为其中包含 N 个向量的 class 实现子集迭代器

Question

如果我有一个 class 可以容纳 N 个大小相同的 vectors。我将如何实现一个标准的迭代器模板，该模板将在 1 到 N 个向量之间迭代。我写了一个小例子来演示这个问题。

#include <bitset>
#include <tuple>
#include <type_traits>
#include <vector>

//Since std::get<>() for types isn't in c++11, I use this meta-function to determine the index
//of a Type in a list of Types, starting from 0. ex: IndexOf<C,  A, B, C>::value = 2
template <typename T, typename... Ts>
struct IndexOf;

template <typename T, typename... Ts>
struct IndexOf<T, T, Ts...> : std::integral_constant<std::size_t, 0> {};

template <typename T, typename U, typename... Ts>
struct IndexOf<T, U, Ts...> : std::integral_constant<std::size_t, 1 + IndexOf<T, Ts...>::value> {};

//Used to determine the slot we're interesting in.
using Handle = const std::size_t;

template<typename... Types>
class DataManager
{
    static constexpr std::size_t TypeCount = sizeof... (Types);
    using Flags = std::bitset<TypeCount>; //BitMask to determine if the handle has a certain piece of data initialized

    std::size_t count, capacity;
    std::tuple<std::vector<Types>..., std::vector<Flags>> vectors; //Tuple of vectors, holding the types and flags.
public:
    DataManager(std::size_t n) : count(0), capacity(n),
    vectors(std::make_tuple(std::vector<Types>(n)..., std::vector<Flags>(n)))
    {}

    template <typename Type, typename... Args>
    void add(Handle handle, Args&&... args) { //Initializes the type in the handle slot of the vector
        Flags& flags = std::get<TypeCount>(vectors)[handle];    //Flag the bit, notify that handle
        flags.set(IndexOf<Type, Types...>::value);              //has that piece of data initialized

        std::get<IndexOf<Type, Types...>::value>(vectors)[handle] = Type{ args... };
    }

    template <typename Type>
    Type& get(Handle handle) { //Returns the Type in handle slot of the vector
        return std::get<IndexOf<Type, Types...>::value>(vectors)[handle];
    }

    template <typename Type>
    bool has(Handle handle) { //Returns true if the Type is initialized, by checking the bitset
        Flags& flags = std::get<TypeCount>(vectors)[handle];
        return flags.test(IndexOf<Type, Types...>::value);
    }

    Handle push_back() {
        return count++;
    }
};

我目前是这样访问数据的：

//Simple Data
struct D0 { int x, y;    };
struct D1 { float  n, m; };
struct D2 { int x, y, z; };

int main()
{
    DataManager<D0, D1, D2> manager(100);
    Handle h0 = manager.push_back();

    std::cout << manager.has<D0>(h0) << std::endl;   //prints false, h0 doesn't have D0 initialized
    manager.add<D0>(h0, 75, 20);                     //initialize D0 for h0

    std::cout << manager.has<D0>(h0) << std::endl;   //prints ture, h0 is now initialzed
    std::cout << manager.get<D0>(h0).x << std::endl; //prints 75
}

如何将迭代器功能添加到 DataManager class，这样只会迭代选定的数据？

 int main() 
 {
     ...
     for (D0 d1, D3 d3 : manager) {
         ... //Iterate over all D0s and D3s between 0 and count
     }
     //or 
     for(DataManager<D0>::iterator it = v.begin(); it != v.end(); ++it {
         ... //Iterate over just D0s between 0 and count - 10
     }
 }

Answer 1

写一个范围视图类型。范围视图有两个迭代器，一个开始和一个结束，并公开 .begin() 和 .end()。返回迭代器的范围视图可让您执行 for(:) 循环而无需复制任何内容。

接下来您需要对所选元素进行迭代。我可以想到两种方法。

首先，一个 zip 迭代器。一个 zip 迭代器有一个迭代器元组，并并行推进它们。当你取消引用时，它 return 是每个迭代器的取消引用的 std::tie。

第二个选项，生成器迭代器。生成器迭代器有一个索引，以及一个从索引映射到某种类型的函数。 ++ 和 == 等只是 advance/compare 索引。 * returns 函数调用的结果。在这种情况下，您将从函数中 return tie。

我通常通过从索引迭代器（存储索引，* returns 它的副本）开始实现生成器迭代器，然后编写转换迭代器（存储迭代器），将 == 和 ++ 等转发给它，存储函数 f，并在 * 上执行 f(*it)，其中 it 是存储的迭代器）。生成器迭代器现在只是一个 transform_iterator<F(index_iterator)>.

由于围绕 ::reference 类型等的规则，这些都有效地限于满足输入迭代器的公理。但是，输入迭代器足以执行 for(:) 循环；更重要的是，for(:) 循环甚至不需要合法的迭代器，因为它是根据代码而非迭代器语义定义的。

generator/transform 迭代器就足够了，两者在其他情况下都很有用，所以我会采用这种方法。

如果需要，您可以选择类型擦除转换（变成 std::function< T(std::size_t) >）。

template<class T>
using any_generator_iterator = transform_iterator< std::function<T(std::size_t)>( indexing_iterator ) >;

现在迭代类型 A B 和 C 我们这样做：

template<class...Ts,
  class R=std::tuple<Ts&...>,
  class It=any_generator_iterator<R>
>
range_view< It >
iterate_over() {
  auto get = [this](std::size_t i)->R {
    return std::tie( this->get<Ts>()... );
  };
  return { {get, 0}, {{}, count} };
}

别处：

for( auto i : foo.iterate_over<A,B,C>() ) {
  auto&& a = std::get<0>(i);
  auto&& b = std::get<1>(i);
  auto&& c = std::get<2>(i);
  // code
}

上面有一堆库代码。

大部分（如果不是全部）已在 boost 中解决。

如何为其中包含 N 个向量的 class 实现子集迭代器

How to implement a subset iterator for a class with N number of vectors in it

c++

template-meta-programming

c++11