How to use a 2d vector of pointers

Question

What is the correct way to implement an efficient 2d vector? I need to store a set of Item objects in a 2d collection, that is fast to iterate (most important) and also fast to find elements.

I have a 2d vector of pointers declared as follows:

std::vector<std::vector<Item*>> * items;

In the constructor, I instantiate it as follows:

items = new std::vector<std::vector<Item*>>();
items->resize(10, std::vector<Item*>(10, new Item()));

I how do I (correctly) implement methods for accessing items? Eg:

items[3][4] = new Item();

AddItem(Item *& item, int x, int y)
{
     items[x][y] = item;
}

My reasoning for using pointers is for better performance, so that I can pass things around by reference.

If there is a better way to go about this, please explain, however I would still be interested in how to correctly use the vector.

Edit: For clarification, this is part of a class that is for inventory management in a simple game. The set 10x10 vector represents the inventory grid which is a set size. The Item class contains the item type, a pointer to an image in the resource manager, stack size etc.

My pointer usage was in an attempt to improve performance, since this class is iterated and used to render the whole inventory every frame, using the image pointer.

Answer 1

It seems that you know the size of the matrix beforehand, and that this matrix is squared. Though vector<> is fine, you can also use native vectors in that case.

Item **m = new Item*[ n * n ];

If you want to access position r,c, then you only have to multiply r by n, and then add c:

pos = ( r * n ) + c;

So, if you want to access position 1, 2, and n = 5, then:

pos = ( 1 * 5 ) + 2;
Item * it =  m[ pos ];

Also, instead of using plain pointers, you can use smart pointers, such as auto_ptr (obsolete) and unique_ptr, which are more or less similar: once they are destroyed, they destroy the object they are pointing to.

auto_ptr<Item> m = new auto_ptr<Item>[ n * n ];

The only drawback is that now you need to call get() in order to obtain the pointer.

pos = ( 1 * 5 ) + 2;
Item * it =  m[ pos ].get();

Here you have a class that summarizes all of this:

class ItemsSquaredMatrix {
public:
    ItemsSquaredMatrix(unsigned int i): size( i )
        { m = new std::auto_ptr<Item>[ size * size ]; }
    ~ItemsSquaredMatrix()
        { delete[] m; }

    Item * get(unsigned int row, unsigned int col)
        { return m[ translate( row, col ) ].get(); }
    const Item * get(unsigned int row, unsigned int col) const
        { return m[ translate( row, col ) ].get(); }

    void set(unsigned int row, unsigned int col, Item * it)
        { m[ translate( row, col ) ].reset( it ); }

    unsigned int translate(unsigned int row, unsigned int col) const
        { return ( ( row * size ) + col ); }

private:
    unsigned int size;
    std::auto_ptr<Item> * m;
};

Now you only have to create the class Item. But if you created a specific class, then you'd have to duplicate ItemsSquaredMatrix for each new piece of data. In C++ there is a specific solution for this, involving the transformation of the class above in a template (hint: vector<> is a template). Since you are a beginner, it will be simpler to have Item as an abstract class:

class Item {
public:
    // more things...
    virtual std::string toString() const = 0;
};

And derive all the data classes you will create from them. Remember to do a cast, though...

As you can see, there are a lot of open questions, and more questions will raise as you keep unveliling things. Enjoy!

Hope this helps.

Answer 2

The first question is why the pointers. There's almost never any reason to have a pointer to an std::vector, and it's not that often that you'd have a vector of pointers. You're definition should probably be:

std::vector<std::vector<Item> > items;

, or at the very least (supposing that e.g. Item is the base of a polymorphic hierarchy):

std::vector<std::vector<Item*> > items;

As for your problem, the best solution is to wrap your data in some sort of a Vector2D class, which contains an std::vector<Item> as member, and does the index calculations to access the desired element:

class Vector2D
{
    int my_rows;
    int my_columns;
    std::vector<Item> my_data;
public:
    Vector2D( int rows, int columns )
        : my_rows( rows )
        , my_columns( columns )
    {
    }

    Item& get( int row, int column )
    {
        assert( row >= 0 && row < my_rows
                && column >= 0 && column < my_columns );
        return my_data[row * my_columns + column];
    }

    class RowProxy
    {
        Vector2D* my_owner;
        int my_row;
    public;
        RowProxy(Vector2D& owner, int row)
            : my_owner( &owner )
            , my_row( row )
        {
        }
        Item& operator[]( int column ) const
        {
            return my_owner->get( my_row, column );
        }
    };
    RowProxy operator[]( int row )
    {
        return RowProxy( this, row );
    }

    //  OR...
    Item& operator()( int row, int column )
    {
        return get( row, column );
    }
};

If you forgo bounds checking (but I wouldn't recommend it), the RowProxy can be a simple Item*.

And of course, you should duplicate the above for const.

Answer 3

For numerical work, you want to store your data as locally as possible in memory. For example, if you were making an n by m matrix, you might be tempted to define it as

vector<vector<double>> mat(n, vector<double>(m));

There are severe disadvantages to this approach. Firstly, it will not work with any proper matrix libraries, such as BLAS and LAPACK, which expect the data to be contiguous in memory. Secondly, even if it did, it would lead to lots of random access and pointer indirection in memory, which would kill the performance of your matrix operations. Instead, you need a contiguous block of memory n*m items in size.

vector<double> mat(n*m);

But you wouldn't really want to use a vector for this, as you would then need to translate from 1d to 2d indices manually. There are some libraries that do this for you in C++. One of them is Blitz++, but that seems to not be much developed now. Other alternatives are Armadillo and Eigen. See this previous answer for more details.

Using Eigen, for example, the matrix declaration would look like this:

MatrixXd mat(n,m);

and you would be able to access elements as mat[i][j], and multiply matrices as mat1*mat2, and so on.