2

事项

我有一个矩阵类，它连续存储一个对称矩阵。由于这些矩阵具有轴对称的良好特性（相对于对角线的镜像），因此可以将存储优化为上三角矩阵或下三角矩阵。

以下方案表示存储为上三角矩阵的 6x6 对称矩阵的存储方案。

r \ c 0 1 2 3 4 5
   -------------------------------------
 0 | 0 | 1 | 2 | 3 | 4 | 5 |
   -------------------------------------
 1 | | 6 | 7 | 8 | 9 | 10 |
   -------------------------------------
 2 | | | 11 | 12 | 13 | 14 |
   -------------------------------------
 3 | | | | 15 | 16 | 17 |
   -------------------------------------
 4 | | | | | 18 | 19 |
   -------------------------------------
 5 | | | | | | 20 |
   -------------------------------------

现在我想为该矩阵的行和列设计一个迭代器。我不想迭代实际的行和列，而是迭代几乎完整的对称矩阵的行和列。

示例：

for (the_iterator i=matrix.row(2).begin(); i!=matrix.row(2).end(); ++i)
{
    cout << *i << " ";
}

这应该打印元素的内容

2 7 11 12 13 14

（如果矩阵是一个 6x6 三角矩阵，如上所示）。

幸运的是，在对称矩阵的情况下，行的序列i等于列的序列，所以我只需要一种迭代器类型。i

矩阵类提供了一种根据行和列索引访问元素的方法

reference operator() (size_type const r, size_type const c) { /*...*/ }

关于如何设计迭代器，我有两个想法。将数学从一个点切换到另一个点。

1. 使用矩阵引用轻松推进迭代器

一方面，我可以存储对矩阵的引用、所需行/列的数量以及该行/列中的当前元素。

matrix_type & m;
size_type fixed;
size_type free;

这将允许使用operator()我的矩阵类进行解引用以及轻松的迭代器改进。

class the_iterator
  // ...
{
  // ...
  reference operator* () const _NOEXCEPT 
  { 
    return *m(fixed, free);
  }
  // ...
  this_type & operator++ (void) _NOEXCEPT
  { // increment then return
    ++free;
    return *this; 
  }
  // ...
};

这有一个明显的缺点：每次调用都operator()需要使用行和列索引来计算底层内存中的连续索引。

2. 使用指向元素的指针轻松取消引用

另一方面，可以有一个指针p（矩阵 value_type 元素指针）和一些控制值来控制迭代器的推进。在垂直部分 (2 -> 7 -> 11; 参考上面的例子) 指针需要前进 5+4 并且在水平部分 (11 -> 12 -> 13 -> 14)pointer需要改变 1 +1+1。这不是微不足道的，但也不是很困难，可以不用迭代以代数方式解决。

取消引用/元素访问不再与任何计算相关联，因为*p可以使用。这就是我目前的做法。

问题：

我应该在哪里进行“计算工作”，你会走哪条路（为什么）？

我可以有

  • 简单快速的迭代器推进，但要求元素访问或
  • 要求进步但简单快速的元素访问。

我倾向于第二个，因为迭代器很可能每个周期只前进一次（在一个循环中），而它可能会被多次取消引用。

4

1 回答 1

0

除非您真的非常需要像示例中那样排列数据，否则我首先会利用三角形数组的基本特征来加快索引速度。这将使您的第一选择更好：存储对矩阵的引用、固定的行/列和当前的空闲索引值，并依靠快速索引来提高性能。

我所知道的关于单位三角矩阵索引的最简单映射是：

int unitriangular_index(int row, int col)
{
    assert(row >= 0);
    assert(col >= row);

    int base = (col * (col + 1)) / 2;

    return (base + row);
}

如果您可以以这种方式排列值，则访问矩阵的一部分将如下所示：

int reflected_index(int row, int col)
{
    assert(row >= 0);
    assert(col >= 0);

    if (col < row)
    {
        return (unitriangular_index(col, row));
    }
    else
    {
        return (unitriangular_index(row, col));
    }
}
于 2013-06-27T14:13:33.553 回答