CODEWITHSUNDEEP
c++algorithmsearchvectormatrix
Eric
Eric

Reputation: 2705

Finding the index of the maximum element in c++ matrix?

I am translating a python(sage) program into a C++ program.

I need to write a function manipulates matrices, and I need to find the index of the largest element in the matrix.

I want to do this as efficiently as possible, but the only thing I came up with so far seems quite inefficient.

The pseudo-code for my algorithm is,

  1. Given a matrix, call max_element function in each row
  2. Create a vector and push_back the iterators returned from max_element
  3. Dereferencing the iterators, call max_element function once more
  4. Find the index of column
  5. Find the index of row

This will be very messy and slow.. Does anyone have a better algorithm to do this task? Thank you.

Upvotes: 0

Views: 2232

Answers (2)

Steve Jessop
Steve Jessop

Reputation: 279255

Probably easiest just to write the outer loop yourself:

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

Alternatively, you could write an iterator class that iterates over the whole matrix:

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

Now you can do:

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

Upvotes: 3

Chemistpp
Chemistpp

Reputation: 2056

I am assuming you are storing your data in a two dimensional vector. 

#include <vector>
#include <algorithm>
vector<vector<int>> Matrix

You should be able to just iterate your matrix like this to obtain the largest element

int MaxValue = 0;
for(int i = 0; i < Matrix.size(); i++) {
    if( *std::max_element(Matrix[i].begin(),Matrix[i].end()) < MaxValue ) continue;
    MaxValue = *std::max_element(Matrix,Matrix+Columns);
}

Upvotes: 0

Related Questions