c++ - 查找 C++ 矩阵中最大元素的索引？

Question

我正在将 python(sage) 程序翻译成 C++ 程序。

我需要编写一个函数来操作矩阵，并且我需要找到矩阵中最大元素的索引。

我想尽可能高效地执行此操作，但到目前为止我想出的唯一方法似乎效率很低。

我的算法的伪代码是，

1. 给定一个矩阵，在每一行中调用 max_element 函数
2. 创建一个 vector 并将从 max_element 返回的迭代器推回
3. 解引用迭代器，再次调用 max_element 函数
4. 找到列的索引
5. 找到行的索引

这将非常困惑和缓慢..有没有人有更好的算法来完成这项任务？谢谢。

Answer 1

可能最简单的方法就是自己编写外循环:

if (matrix.size() == 0 || matrix[0].size() == 0) {
    // matrix is empty, handle special case
    throw std::logic_error("empty");
}
int best = matrix[0][0];
size_t rowidx = 0, colidx = 0;
for (auto it = matrix.begin(); it != matrix.end(); ++it) {
    auto maxit = max_element(it->begin(), it->end());
    if (*maxit > best) {
        best = *maxit;
        rowidx = it - matrix.begin();
        colidx = maxit - it->begin();
    }
}

或者，您可以编写一个遍历整个矩阵的迭代器类:

struct MatrixIterator : std::iterator<std::forward_iterator_tag, int> {
    typedef vector<vector<int> > Matrix;
    Matrix &m;
    size_t rowidx, colidx;
    explicit MatrixIterator(Matrix &m, size_t row = 0, size_t col = 0) : m(m), rowidx(row), colidx(col) {};
    int &operator*() { return m[rowidx][colidx]; }
    MatrixIterator &operator++() {
        ++colidx;
        if (colidx == m[rowidx].size()) {
            colidx = 0;
            ++rowidx;
        }
        return *this;
    }
    MatrixIterator operator++(int) {
        MatrixIterator result = *this;
        ++*this;
        return result;
    }
    bool operator==(const MatrixIterator &rhs) {
        return rowidx == rhs.rowidx && colidx == rhs.colidx;
    }
    bool operator!=(const MatrixIterator &rhs) {
        return ! (*this == rhs);
    }
    static MaxtrixIterator end(Matrix &m) {
        return MatrixIterator(m, m.size() - 1, m.back().size());
    }
};

现在您可以:

MatrixIterator result = std::max_element(MatrixIterator(m), MatrixIterator::end(m));
size_t rowidx = result.rowidx, colidx = result.colidx;