时间戳

首页 > 解决方案 > 使数组结构看起来像结构数组的 std::vector 包装器

c++ - 使数组结构看起来像结构数组的 std::vector 包装器

问题描述

我有一个包含 8 个不同字段（整数和指针）的结构向量，用作我的程序的数据库。通常只有少数这些字段被实际使用（通常只有一个）。本来很好，但现在存储数十亿个元素时内存不足。我想稀疏地存储这些数据，而每个对象中未使用的字段都没有零/空条目。但是，这在代码库中到处都在使用，并且很难更改。

我决定将各个字段存储为单独的向量，并创建一个包装这些向量的类，使 SoA 对调用者显示为 AoS。在创建数据库期间，使用的字段集在运行时是已知的。它需要有大量的 std::vector 成员函数。我能想到的最好的方法是一些宏和大量复制粘贴代码行来处理各个字段向量：

#define SELECT_FIELD_VECT(FUNC) (use_uv() ? uv.FUNC : (use_dv() ? dv.FUNC : (use_sv() ? sv.FUNC : rv.FUNC)))
#define APPLY_FIELD_VECT(FUNC) { if(use_uv()) {uv.FUNC;} if(use_dv()) {dv.FUNC;} if(use_sv()) {sv.FUNC;} if(use_rv()) {rv.FUNC;} }

class md_tracker_t {
  vector< match_track_data_uints_t > uv;
  vector< delta_pair  const * > dv;
  vector< std::string const * > sv, rv;
public:
  bool  empty( void ) const { return SELECT_FIELD_VECT(empty()); }
  size_t size( void ) const { return SELECT_FIELD_VECT(size ()); }
  size_t capacity( void ) const { return SELECT_FIELD_VECT(capacity()); }
  void  clear( void ) { uv.clear(); dv.clear(); sv.clear(); rv.clear(); }
  void shrink_to_fit( void ) { APPLY_FIELD_VECT(shrink_to_fit()); }
  void reserve( size_t const sz ) { APPLY_FIELD_VECT(reserve(sz)); }
  void resize ( size_t const sz ) { APPLY_FIELD_VECT(resize(sz)); }
  void swap( md_tracker_t &mt ) { uv.swap( mt.uv ); dv.swap( mt.dv ); sv.swap( mt.sv ); rv.swap( mt.rv ); }
  void push_back( match_track_data_t const &md ) {
    if( use_uv() ) { uv.push_back( md.uints ); }
    if( use_dv() ) { dv.push_back( md.deltas ); }
    if( use_sv() ) { sv.push_back( md.signature ); }
    if( use_rv() ) { rv.push_back( md.rulename ); }
  }
  void copy_from( size_t const from_ix, size_t const to_ix ) {
    if( use_uv() ) { uv[to_ix] = uv[from_ix]; }
    if( use_dv() ) { dv[to_ix] = dv[from_ix]; }
    if( use_sv() ) { sv[to_ix] = sv[from_ix]; }
    if( use_rv() ) { rv[to_ix] = rv[from_ix]; }
  }
  void add_from( md_tracker_t const &mt, size_t const ix ) {
    if( use_uv() ) { uv.push_back( mt.uv[ix] ); }
    if( use_dv() ) { dv.push_back( mt.dv[ix] ); }
    if( use_sv() ) { sv.push_back( mt.sv[ix] ); }
    if( use_rv() ) { rv.push_back( mt.rv[ix] ); }
  }
  match_track_data_t get_mtd( size_t const ix ) const {
    assert( ix < size() );
    return match_track_data_t( ( use_uv() ? uv[ix] : match_track_data_uints_t() ),
                   ( use_dv() ? dv[ix] : 0 ),
                   ( use_sv() ? sv[ix] : 0 ),
                   ( use_rv() ? rv[ix] : 0 ) );
  }
  ...
};

这有效，但它很混乱。它也只使用了 8 个字段中的 4 个。我想稍后添加更多字段，而不必为每个字段更改数十行代码。有没有更紧凑/干净的方法来做到这一点？宏、模板、C++11 等有什么魔力？谢谢你。

标签： c++stdvector

解决方案

好吧，您拥有的小启用位（use_uv()等）很有趣，我很确定没有类似功能的通用版本，所以我试了一下。

为了使数据通用，您必须用通用结构的索引替换“结构”部分和那些可爱的字段名称std::tuple。std::tuple您可以通过扩展添加访问器来弥补它

struct match_track_data_t : std::tuple<match_track_data_uints_t, delta_pair, std::string, std::string> {
  using std::tuple<match_track_data_uints_t, delta_pair, std::string, std::string>::tuple;
  match_track_data_uints_t& uv() { return std::get<0>(*this); }
  match_track_data_uints_t& uv() const { return std::get<0>(*this); }
  delta_pair& dv() { return std::get<1>(*this); }
  delta_pair& dv() const { return std::get<1>(*this); }
  /* etc... */
};

对于向量，数据是向量的元组。use_*标志成为谓词数组：

template <typename... Ts>
class md_tracker_t {
  std::tuple<std::vector<Ts>...> data;
  std::array<bool(*)(), sizeof...(Ts)> use_ix;

public:
  md_tracker_t(std::array<bool(*)(), sizeof...(Ts)> use_ix) : use_ix(use_ix) { }

现在，我尝试将您类中的每个方法分类为一些通用操作：

  • select- 对第一个启用的向量执行某些操作并返回值
  • apply- 对每个启用的向量（或所有向量）做一些事情
  • apply_join- 用其他元组压缩元组，并对每个启用的对执行一些操作
  • get_mtd- 这个功能我不能混入其他类型

这些apply*函数应该有一个版本，仅适用于启用的数组或所有数组。

如果将整个公共接口映射到这些通用函数：

  bool empty() const { return select([](auto& v) { return v.empty(); }); }
  bool size() const { return select([](auto& v) { return v.size(); }); }
  bool capacity() const { return select([](auto& v) { return v.capacity(); }); }
  void clear() { apply<false>([](auto& v) { v.clear(); }); }
  void shrink_to_fit() { apply([](auto& v) { v.shrink_to_fit(); }); }
  void reserve( size_t const sz ) { return apply([&sz](auto& v) { v.reserve(sz); }); }
  void resize ( size_t const sz ) { return apply([&sz](auto& v) { v.resize(sz); }); }
  void swap( md_tracker_t &mt ) { apply_join<false>(mt, [](auto& v, auto& w) { v.swap(w); }); }
  void push_back( std::tuple<Ts...> const &md ) { apply_join(md, [](auto& v, auto& e) { v.push_back(e); }); }
  void copy_from( size_t const from_ix, size_t const to_ix ) { apply([&from_ix, &to_ix](auto& v) { v[to_ix] = v[from_ix]; }); }
  void add_from( md_tracker_t const &mt, size_t const ix ) { apply_join(mt, [&ix](auto& v, auto& w) { v.push_back(w[ix]); }); }
  std::tuple<Ts...> get_mtd( size_t const ix ) const { return get_mtd_impl(ix, std::index_sequence_for<Ts...>{}); }

您所要做的就是实施它们！（我在这里使用 C++14 通用 lambda 跳过了很多样板文件）。

要实现select，您不能只编写一个循环，因为std::tuple只能使用编译时参数进行索引。因此，您必须改为递归：从零开始，如果启用 [0]，则将 lambda 应用于该向量或重复下一个索引：

  template <typename Functor, size_t Index = 0, typename std::enable_if<Index != sizeof...(Ts)>::type* = nullptr>
  decltype(auto) select(Functor&& functor) const {
    return use_ix[Index]() 
      ? functor(std::get<Index>(data))
      : select<Functor, Index + 1>(std::forward<Functor>(functor));
  }

  template <typename Functor, size_t Index, typename std::enable_if<Index == sizeof...(Ts)>::type* = nullptr>
  decltype(auto) select(Functor&& functor) const  { return decltype(functor(std::get<0>(data))){}; }

apply稍微简单一些，因为您可以将整个元组扩展std::index_sequence为std::get一次性布尔数组。逗号运算符（总是返回右侧）是一种将 void 函数转换为表达式的作弊码：

  template <bool conditional = true, typename Functor, size_t... Is>
  void apply(Functor&& functor, std::index_sequence<Is...>) {
    std::initializer_list<bool> { (!conditional || use_ix[Is]() ? (functor(std::get<Is>(data)), false) : false)... };
  }

  template <bool conditional, typename Functor>
  void apply(Functor&& functor) {
    return apply(std::forward<Functor>(functor), std::index_sequence_for<Ts...>{});
  }

布尔conditional模板参数基本上是一个覆盖。如果false，无论谓词返回什么，它都会应用 lambda。

很多功能，比如push_back获取swap一个切片或另一个 SoA 并交叉加入它。对于那些，我们有，除了它处理额外的参数之外apply_join几乎相同：apply

  template <bool conditional = true, typename Functor, typename Arg, size_t... Is>
  void apply_join(Functor&& functor, Arg& arg, std::index_sequence<Is...>) {
    std::initializer_list<bool> { (!conditional || use_ix[Is]() ? (functor(std::get<Is>(data), std::get<Is>(arg)), false) : false)... };
  }

  template <bool conditional = true, typename Functor, typename Arg>
  void apply_join(Functor&& functor, Arg& arg) {
    return apply_join(std::forward<Functor>(functor), arg, std::index_sequence_for<Ts...>{});
  }

最后，get_mtd只需扩展元组，将索引运算符应用于每个元组，然后将其传递给std::tuple：

  template <size_t... Is>
  std::tuple<Ts...> get_mtd_impl( size_t const ix, std::index_sequence<Is...>) const {
    assert(ix < sizeof...(Ts));
    return std::tuple<Ts...>(std::get<Is>(data)[ix]...);
  }

就是这样！

};

可能比您手动编写的代码更多，但您可以整天添加字段而无需不必要的样板。

用法：

using md_tracker = md_tracker_t<match_track_data_uints_t, delta_pair, std::string, std::string>;

演示：https ://godbolt.org/z/p5t6wu

推荐阅读