0

实现高效二维向量的正确方法是什么？我需要将一组 Item 对象存储在 2d 集合中，这可以快速迭代（最重要）并且也可以快速找到元素。

我有一个 2d 指针向量，声明如下：

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

在构造函数中，我将其实例化如下：

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

我如何（正确）实现访问项目的方法？例如：

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

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

我使用指针的原因是为了获得更好的性能，这样我就可以通过引用传递东西。

如果有更好的方法来解决这个问题，请解释一下，但是我仍然对如何正确使用向量感兴趣。

编辑：为澄清起见，这是一个简单游戏中用于库存管理的类的一部分。设置的 10x10 向量表示作为设置大小的库存网格。Item 类包含项目类型、资源管理器中指向图像的指针、堆栈大小等。

我的指针使用是为了提高性能，因为这个类被迭代并使用图像指针在每一帧渲染整个库存。

4

3 回答 3

3

似乎您事先知道矩阵的大小，并且该矩阵是平方的。虽然vector<>很好，但在这种情况下您也可以使用本机向量。

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

如果要访问位置 r,c，则只需将 r 乘以 n，然后加上 c：

pos = ( r * n ) + c;

因此，如果要访问位置 1、2 和 n = 5，则：

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

此外，除了使用普通指针，您还可以使用智能指针，例如auto_ptr(obsolete) 和unique_ptr，它们或多或少相似：一旦它们被销毁，它们就会销毁它们指向的对象。

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

唯一的缺点是现在您需要调用get()才能获取指针。

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

在这里，您有一个总结了所有这些的课程：

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

现在您只需要创建类Item。但是，如果您创建了一个特定的类，那么您必须ItemsSquaredMatrix为每条新数据进行复制。在 C++ 中对此有一个特定的解决方案，涉及在模板中转换上述类（提示：vector<>是一个模板）。由于您是初学者，因此将其Item作为抽象类会更简单：

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

并派生您将从它们创建的所有数据类。记得做演员，虽然...

如您所见，有很多未解决的问题，并且随着您不断揭开事物的面纱，会提出更多问题。享受！

希望这可以帮助。

于 2012-11-05T18:40:59.400 回答
2

对于数值工作，您希望将数据尽可能本地存储在内存中。例如，如果您正在制作一个nbym矩阵，您可能很想将其定义为

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

这种方法有严重的缺点。首先，它不适用于任何适当的矩阵库，例如BLASand LAPACK，它们期望数据在内存中是连续的。其次，即使这样做，也会导致内存中出现大量随机访问和指针间接，这会降低矩阵运算的性能。相反，您需要一个大小连续的内存n*m项块。

vector<double> mat(n*m);

但是您实际上并不想为此使用 a vector，因为您随后需要手动将 1d 索引转换为 2d 索引。有一些库可以为您执行此操作C++。其中之一是Blitz++，但现在似乎没有太多开发。其他替代品是犰狳和本征。有关更多详细信息，请参阅此先前的答案。

Eigen例如，使用，矩阵声明将如下所示：

矩阵Xd mat(n,m);

并且您将能够以 访问元素mat[i][j]，并将矩阵乘以mat1*mat2，依此类推。

于 2012-11-05T18:16:22.663 回答
1

第一个问题是为什么要指针。几乎没有任何理由拥有指向 an 的指针std::vector，而且你拥有指针向量的情况并不常见。你的定义应该是：

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

，或者至少（假设例如 Item 是多态层次结构的基础）：

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

至于您的问题，最好的解决方案是将您的数据包装在某种类中，Vector2D该类包含一个std::vector<Item>as 成员，并进行索引计算以访问所需的元素：

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

如果您放弃边界检查（但我不建议这样做），则 RowProxy可以是一个简单的Item*.

当然，您应该将上述内容复制到const.

于 2012-11-05T18:18:41.010 回答