Accessing an object without storing a pointer to it in each instance

Question

I have a situation similar to the following

struct Cell
{
  uint16_t x, y;
  // other fields

  Cell* right();
  Cell* above();
  ...
}

class Container
{
private:
  uint16_t width, height;
  Cell* data;

public:
  Container(uint16_t width, uint16_t height) : 
    width(width), height(height), data(new Cell[width*height]) { }

  Cell* cellAt(uint16_t x, uint16_t y) { &data[x*height + y]; }
};

Container* container;

Cell* Cell::right() { return container->cellAt(x+1, y); }
...

I trimmed down much of code (eg range checks and whatnot) just to show the design.

Basically this allow me everywhere in the code to access neighbour cells without passing by Container object directly (which would produce more verbose code and neighbours are accesses hundreds of times all around the code base). The solution works nicely and Container class is not even need to be known around the code, since Cell is enough.

This approach has a strong limit though: it allows only one instance of Container. Now I find myself in the situation of wanting multiple instances of Container, with independent Cell arrays but I don't want to change the structure of the code.

I'm thinking about a smart way to allow multiple Container, but

• I want to keep the structure as it is
• I absolutely don't want to store a Container* inside each Cell to avoid wasting a lot memory (we're talking about million of cells)
• I want to keep it as much efficient as possible since these neighbour functions are used a lot

I was thinking about allocating width*height + 1 Cell instances and use the first instance to store a Container* in its memory, but the problem is how to compute the address of the first Cell considering that the total width/height are fields of Container itself (and not known by Cell).

So I guess I should store at least one pointer to Container* for each column (they are stored by column as shown by cellAt function for secondary reasons useless to the question). This would waste height*sizeof(Cell) bytes for each Container which could be quite a lot but I guess there's no way with with a single pointer.

So basically I could do something like:

Container** container = reinterpret_cast<Container**>(&data[0]);
*container = this;

And then retrieve the object. Of course this is a dirty hack which could give problems on architecture which doesn't support unaligned accesses if sizeof(Cell) % alignof(void*) != 0.

Are there smarter solutions which I'm missing?

Answer 1

I have 3 solutions for you.

---

Cells know they are in a contiguous 2d buffer.

Finding the first element in the lower dimension is easy. So now you are at (N,0). If N is 0 we are done, we found the start of the 2d array.

The element before that is (N-1,Last), where Last+1 is the size of the lower dimension. Now you can jump to (0,0).

---

Alternatively, drop x and y from the cell, replace with container pointer. Calculate x and y on the fly from address of this and container pointer.

---

If we want to get serious, we drop all redundant information.

Kill x and y. Write a cell view type that stores a Cell* and a Container*. Mediate all interactions with Cell through this view. It calculates x and y and knows container size. It could just do nothing but pass Container* pointers to each method of Cell.

The CellView then replaces Cell* in your codebase. You can even override -> to return this and keep most use unchanged.

CellView cellAt(uint16_t x, uint16_t y) { return {&data[x*height + y], this}; }

struct Cell{
//  uint16_t x, y;
  // other fields

  Cell* right(Container*);
  Cell* above(Container*);
  ...
};

struct CellView{
  // maybe: uint16_t x, y;
  Cell* cell;
  Container* container;


  CellView right()const{ return {cell->right(container), container}; };
  CellView above()const{ return {cell->above(container), container}; };
  ...
};

Basically move state into the "pointer" and out of the cell.

Answer 2

Using an array of global Container and using polymorphism over Cell and over Container to have a template integer parameter where to store the index of the Container...

I don't think it's a good idea (Cell become a pure virtual abstract struct) but, just for fun...

#include <cstdint>
#include <iostream>

struct Cell
 {
   uint16_t x, y;
   // other fields

   virtual Cell* right() = 0;
   //Cell* above();
 };

class Container
 {
   private:
      uint16_t width, height;
      Cell* data;

   public:
      Container(uint16_t w0, uint16_t h0, Cell * d0)
         : width(w0), height(h0), data(d0)
       { }

      Cell* cellAt(uint16_t x, uint16_t y)
       { return &data[x*height + y]; }
 };

Container * containers[10];

template <std::size_t I>
struct CellI : public Cell
 {
   Cell* right()
    { std::cout << I << std::endl; return containers[I]->cellAt(x+1, y); }
 };

template <std::size_t I>
class ContainerI : public Container
 {
   public:
      ContainerI (uint16_t w0, uint16_t h0)
         : Container(w0, h0, new CellI<I>[w0*h0])
       { }
 };


int main()
 {
   containers[0] = new ContainerI<0>(10, 20);
   containers[1] = new ContainerI<1>(20, 40);
   containers[2] = new ContainerI<2>(30, 60);
   // ...

   containers[0]->cellAt(5,5)->right(); // print 0
   containers[1]->cellAt(5,5)->right(); // print 1
   containers[2]->cellAt(5,5)->right(); // print 2
 }

Answer 3

Here are two possible solutions that come to mind, given the limitations you've stated:

1) For all functions which need a Container to accomplish their work, just require the Container as a parameter.

For example:

Cell* Cell::right(Container* container)
{
    return container->cellAt(x+1, y);
}

2) Instead of asking Cells about things which the Container knows, ask the Container about its Cells. In other words move the right, above, and similar functions to the Container.

For example:

Cell* Container::nextRightCell(Cell* from)
{
    return cellAt(from->x+1, from->y);
}