在某些元素上提供带迭代器的整数矩阵(Providing an integer matrix with an iterator over certain elements)

在某些元素上提供带迭代器的整数矩阵(Providing an integer matrix with an iterator over certain elements)

我正在尝试找到以下问题的解决方案：

假设我们已经实现了抽象数据类型“整数矩阵”（假设整数存储在行中）。 我们需要定义一个迭代器来迭代遍历矩阵，而不是遍历矩阵的偶数元素。

执行folling代码：

Matrix M; ... Matrix::iterator it; for(it = M.begin(); it != M.end();++it) cout << *it

在矩阵上：

5 4 3 2 1 2 9 0 2 8 9 1

应该产生2 8 4 0 2 2

我要面对几个问题。 首先，我想避免为class iterator提供有关它迭代的矩阵的大量信息。 提供矩阵的行数和列数是不可避免的吗？ 其次，解决方案很大程度上取决于矩阵的内部表示，所以我要说我应该实现一个基本的迭代器来逐行迭代......

您认为这个问题的最佳解决方案是什么？ 我只需要关于矩阵和迭代器的表示以及函数begin，end，operator *，operator ++和operator ==的建议

I'm trying to find a solution for the following problem:

Suppose we have implemented an abstract data type "integer matrix" (assume that integers are stored in rows). We need to define an iterator to iterate over the matrix by columns and only over the even elements of the matrix.

Executing the folling code:

Matrix M; ... Matrix::iterator it; for(it = M.begin(); it != M.end();++it) cout << *it

on the matrix:

5 4 3 2 1 2 9 0 2 8 9 1

should produce 2 8 4 0 2 2

I face several problems to do it. First, I would like to avoid providing the class iterator with much information about the matrix it is iterating over. Is it inevitable to provide the number of rows and columns of the matrix? Second, the solution depends a lot on the internal representation of the matrix so I'd say I should implement a basic iterator to iterate row by row...

What do you think is the best solution to this problem? I would just need advice about the representation of the matrix and the iterator and the functions begin,end,operator*,operator++ and operator ==

最满意答案

如果不猜测您未指定哪些操作需要特别有效，则看起来元素的扁平线性存储将是最佳的。 通过调用Matrix :: iterator（并使用你所示的begin（）和end（））你暗示这是用于这个Matrix类的普通迭代器（不是一些奇怪的额外迭代器）。 所以在矩阵中有一些额外的内容值可以保持迭代器的轻量级。 您可以使迭代器的数据内容只是一个指针，因此在优化的编译中，迭代器本身只是一个指针。 它不需要知道行数或列数或限制。

要做到这一点，你需要在矩阵数据的极限处分配和初始化一个保护位置，它必须保持一个偶数，而end（）必须是一个指针（包含在迭代器类中）。 然后begin（）可以简单地找到第一个偶数，而迭代器的++可以简单地找到下一个偶数。

为了支持我们认为必须存在的其他操作（但您没有询问过），Matrix本身必须知道列数。 对于end（）和其他操作，Matrix必须知道总大小（表示为行数或元素数或限制地址是否可以轻松转换为限制地址）。 但是，额外的信息最好保存在Matrix中，而不是复制到迭代器中。

Without guessing at which of the operations that you haven't specified need to be especially efficient, it appears a flat linear storage of the elements would be best. By calling it Matrix::iterator (and using begin() and end() as you have shown) you have implied this is the ordinary iterator used for this Matrix class (not some weird extra iterator). So it is worth a little extra content in the matrix to keep the iterator light weight. You can make the iterator's data content be only a pointer, so in an optimized compile the iterator itself is only a pointer. It doesn't need to know row count or column count or limit.

To do that, you need to allocate and initialize a guard position at the limit of the matrix data and it must hold an even number and end() must be a pointer to it (wrapped in the iterator class). Then begin() can simply find the first even number and the iterator's ++ can simply find the next even number.

To support other operations that we assume must exist (but you haven't asked about) the Matrix itself must know number of columns. For end() and other operations, the Matrix must know the total size (represented as number of rows or number of elements or limit address are anything else easily translated to limit address). But that extra info is better kept in the Matrix and not duplicated into the iterator.