如何使用内存中持久存在的动态大小的数据结构

Question

我正在使用 C++ 构建范围最小查询程序，但我很难处理整个程序中使用的动态大小的向量。现在我正在使用 size_t** 为元素数组制作一个二维索引数组，但使用起来不是很好。我更愿意利用现有的 c++ 数据结构，如向量，但我不确定如何创建一个成员变量，该变量是指向向量的指针或可以以这种方式操作并从 class.

当我尝试使用 vector 时，我可以在 PrecomputedRMQ() 中填充和操作它，但是当我尝试在 rmq() 中查询时，内存无法访问，我会出现段错误。

本质上，如何用 vector<vector<size_t>> 替换 size_t** 的这种用法，更一般地说，如何初始化和分配指向内置数据结构成员变量的指针？

在页眉中：

private:
size_t** table;

在我的 cpp 中：这是我现在构建 table 的方式

PrecomputedRMQ::PrecomputedRMQ(const RMQEntry* elems, size_t numElems) {
  numElems = numElems;
  table = new size_t*[numElems];
  for (size_t i = 0; i < numElems; i++) {
    table[i] = new size_t[numElems];
  }
  for (size_t i = 0; i < numElems; i++) {
    table[i][i] = i;
  }
  // then I go on to populate the table using DP
}

size_t PrecomputedRMQ::rmq(size_t low, size_t high) const {
  return table[low][high];
}

Answer 1

用 std::vector 替换当前显式内存处理的关键是，您不需要分配循环。

您只需要例如

table = std::vector<std::vector<size_t>>(numElems, std::vector<size_t>(numElems));

这将创建一个向量的向量，所有大小都已经设置好，所有元素都已分配并初始化为零（这与您当前的代码不同，后者让大部分元素未初始化！）。

在此之后，您的初始化循环和 rmq 中的使用应该按原样工作。如果索引 low 和 high 当然在范围内。

Answer 2

你可以试试这个

（仅略微测试）

#include <memory>

template<typename DataType>
class Board {
  std::unique_ptr<DataType[]> board;
public:
  const int rows = 8;
  const int cols = 8;

  Board(int row, int col, const DataType& filler = {}) :
    rows(row),
    cols(col),
    board(std::make_unique<DataType[]>(row*col)) {
      std::fill_n(board.get(), rows*cols, filler);
    }

  DataType *operator[](int row) { return board.get()+row*cols; }
  const DataType *operator[](int row) const { return board.get()+row*cols; }
};

template<typename DataType, int crows = 8, int ccols = 8>
class FixBoard {
  std::array<DataType, crows*ccols> board;

public:
  const int rows = crows;
  const int cols = ccols;

  FixBoard(const DataType& filler = {}) {
    board.fill(filler);
  }

  DataType *operator[](int row) { return board.data()+row*cols; }
  const DataType *operator[](int row) const { return board.data()+row*cols; }
};

Board 可以根据一些输入在创建时调整大小，FixBoard 需要编译时知道大小。

使用示例

#include <iostream>
constexpr char BlockChar { '\xB2' }; // 178
constexpr char EmptyChar { '.' };
constexpr char BlankChar { ' ' };

template <typename BoardType>
void Display(const BoardType& board) {
  for (int i = 0; i < board.rows; ++i ) {
    for (int j = 0; j < board.cols; ++j ) {
      //std::cout << this->operator[](i)[j];
      std::cout << board[i][j];
    }
    std::cout << '\n';
  }
}

void Test() {
  constexpr int sx = 6, sy = 10;
  Board<char> board(sx, sy, BlankChar);
  board[3][5] = BlockChar;
  Display(board);

  FixBoard<char, sx, sy> fixBoard(BlockChar);
  fixBoard[3][5] = BlankChar;
  Display(fixBoard);
}

缺少 headers，更多的 constexpr、const 和 test。

如何使用内存中持久存在的动态大小的数据结构

How do I use dynamically sized data structures that are persistent in memory

c++

memory

algorithm

std