c++ - 如何访问和管理 block 存储的数据

Question

我想做什么我需要以 block 形式存储单元格数据，即

*cell_member1[cell0] .. cell_member1[cellN] ... cell_memberM[cell0] .. cell_memberM[cellN]*

然后我需要有效地访问这些数据，如果可能的话，使用一个好的语法。如果我可以定义要轻松存储的数据，那就太好了，即通过定义一个具有成员的对象作为我想要存储的数据，并将它传递给一些为我做所有事情的“魔法”。

动机:为什么我需要这样做？缓存垃圾处理。在某些内部循环中，仅访问对象的某些成员。将一半缓存行浪费在未使用的内存上不是我的应用程序的选择。我可以在指向某个顺序内存区域的对象中存储指针。这会浪费内存并迫使我在该区域使用不同的语法。

我目前是如何做的:我有一个容器的形式:

template<class T> struct Container {
  char* data;
  Container(const int n) {
    data = new char[n*T::spaceRequirements()]; //< Data stored "block-wise"
    new(data) typename T::Flags[n]; //< Flags stored "cell-wise"
  }
  /// Destructor ommited for briefness.
};

我在其中存储一些类型 T 的单元格的数据。每个单元格我需要一些标志，现在我正在使用 std::bitset 来存储它们，这意味着我需要以单元格形式存储这个位集:

*cell_member1[cell0] ... cell_memberM[cell0] ... cell_member1[cellN] .. cell_memberM[cellN]*

我在下面的类中描述每个单元格需要存储多少数据，该类还提供对数据的访问:

template<int nd> struct CellAccessor {
  /// Cell flags are stored cell-wise:
  typedef std::bitset<64> Flags;
  enum { DELETE = 0, ///< Cell marked for deletion
         REFINE = 1 ///< Cell marked for refinement
         //...
  }; ///< Enum for the flags.
  static inline Flags& flags(const int cellId) {
    return *reinterpret_cast<Flags*>(data + sizeof(Flags)*cellId); }
  template<int pId> static inline Flags::reference flags(const int cellId) {
    return flags(cellId)[pId]; } //< Cell-wise access to the properties

  /// The rest of the data is stored block-wise:
  static inline int& order(const int cellId) { ///< One int field.
    return *reinterpret_cast<int*>
        (data + maxNoCells*sizeof(Flags) + sizeof(int)*cellId);}

  /// Coordinate vector with nd components:
  static inline double& coordinates(const int cellId, const int i) {
    return *reinterpret_cast<double*>
        (data + maxNoCells*(sizeof(Flags)+sizeof(int))
         + maxNoCells*i*sizeof(double) + sizeof(double)*cellId); }
  template<int i> static inline double& coordinates(const int cellId) {
    return *reinterpret_cast<double*>
        (data +maxNoCells*(sizeof(Flags)+sizeof(int)+i*sizeof(double))
         + sizeof(double)*cellId); }

  /// Total amount of memory to allocate per cell: (used by Container)
  static inline int spaceRequirements() { return
        sizeof(Flags) // Flags
        + sizeof(int) // order
        + nd*sizeof(double) // coordinates
        ;}

  /// Constructor gets pointer to the beginning of the container 
  /// and the offset for the member variables:
  CellAccessor(char* d, int n){data = d; maxNoCells = n;}
 private:
  static char* data;  ///< Pointer to the beginning of the container.
  static int maxNoCells;  ///< Cell offset for the member variables.
};
template<int nd> char* CellAccessor<nd>::data = nullptr;
template<int nd> int CellAccessor<nd>::maxNoCells = 0;

我是这样使用它的:

int main() {
  int maxNoCells = 10000;   ///< Maximum number of cells (=cell offset).
  typedef CellAccessor<2> A;
  Container< A > cellData(maxNoCells);  ///< Allocate cell data.
  A cells(cellData.data,maxNoCells);  ///< Provides access to cell data.

  for(int i = 0; i < maxNoCells; ++i){
    cells.flags<A::DELETE>(i) = i%2==0 ? true : false;
    cells.flags<A::REFINE>(i) = i%2==0 ? false : true;
    cells.coordinates(i,0) = i;
    cells.coordinates<1>(i) = -((double)i);
    cells.order(i) = 2;
  }
}

优点:

• 数据是 block 形式的，这正是我所需要的。

• 语法没问题。

问题:

• 我的类做的太多了:为用户提供对数据的访问，为容器提供需要存储多少数据，为我的数据结构提供数据应该如何移动/复制/交换(哪些是树……)……

• 没有迭代器，我无法使用 STL 算法。我通过让迭代器存储单元格索引并在其中重新实现 CellAccessor 类来实现迭代器(糟糕!干!)。

• Bitset 仍以单元形式存储。我可以为我的 block 级数据结构重新实现 bitset...

• data 和 maxNoCells 是静态变量，但如果需要，我可以将它们设为普通成员变量。

问题:是否有任何有效的方法以 block 形式存储“对象”(或我们从概念上理解的对象)并像存储在 std 容器中一样访问它们，例如 vector ？

Answer 1

你想要的是一种“基于列”的内存访问方式

您可以使用 std::vector 轻松实现它作为您的列类型或使用您自己的底层内存管理创建您自己的“列”类型 - 但是 std::vector应该工作得很好

现在，一旦您有了列类型，您就可以创建“TABLE”类型。

在某种程度上，您的表格 cab 只是 vector 的 vector 。你当然可以把它包装起来以获得更好看的访问器(如果你想先按行(对象)访问，然后按列(属性)访问。

这是我认为最好的通用方法。

即使在您的特定情况下 - 因为您想要使用位长度标志来节省内存，正如 Bart van Ingen Schenau 所提到的，您可以使用 vector<bool>所以一般的做法是成立的