CODEWITHSUNDEEP
c++algorithmmemorystd
Moose
Moose

Reputation: 77

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

I'm working on building a range minimum query program in C++ but I'm having a hard time working with dynamically sized vectors that are used throughout the program. Right now I am using a size_t** to make a 2d array of indexes to an array of elements, but it's not very nice to work with. I would much rather leverage existing c++ data structures like vectors, but I'm not sure how to make a member variable that is a pointer to a vector or some other data structure that can be manipulated in this way and access from anywhere in the class.

When I tried using a vector I could populate it and manipulate it in PrecomputedRMQ(), but when I tried to query in rmq() the memory was inaccessible and I would segfault.

In essence, how do I replace this use of size_t** with a vector<vector<size_t>>, and more generally, how do I initialize and allocate pointers to member variables of builtin data structures?

In Header:

private:
size_t** table;

In my cpp: Here is how I'm constructing my table right now

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];
}

Upvotes: 0

Views: 163

Answers (2)

Surt
Surt

Reputation: 16129

You could try something like this

(only slightly tested)

#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 can be sized on creation from some input, FixBoard requires compile time knowledge of the size.

Usage example

#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);
}

Missing headers, more constexpr, const and test.

Upvotes: 0

Some programmer dude
Some programmer dude

Reputation: 409482

The key to replacing your current explicit memory handling with std::vector, you don't need the allocation loop.

All you need is e.g.

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

That will create a vector of vectors, with all sizes already set and all elements allocated and zero-initialized (which differs from your current code which leaves the majority of elements uninitialized!).

After this your initialization loop and the use in rmq should work as is. Iff the indexes low and high are in range of course.

Upvotes: 3

Related Questions