Find max position in a vector of vector of vector

Question

I have a vector of vector of vector

std::vector<std::vector<std::vector<double>>> mountain_table

and I would like to find the coordinates i, j, k of this vector for which it is the highest. I know that I should use max_element but I don't know how to use it in a 3d vector.

How should I get those coordinates?

Answer 1

I do not think you can use std::max_element for such data. You can use std::accumulate():

using dvect = std::vector<double>;
using ddvect = std::vector<dvect>;
using dddvect = std::vector<ddvect>;
dddvect mx = { { { 1, 2, 3 }, { -1, 3 }, { 8,-2, 3 } },
               { {}, { -1, 25, 3 }, { 7, 3, 3 } },
               { { -1, -2, -3 }, {}, { 33 } } };

struct max_value {
    size_t i = 0;
    size_t j = 0;
    size_t k = 0;

    double value = -std::numeric_limits<double>::infinity();

    max_value() = default;
    max_value( size_t i, size_t j, size_t k, double v ) : i( i ), j( j ), k( k ), value( v ) {}

    max_value operator<<( const max_value &v ) const
    {
        return value > v.value ? *this : v;
    }

};

auto max = std::accumulate( mx.begin(), mx.end(), max_value{}, [&mx]( const max_value &val, const ddvect &ddv ) {
    auto i = std::distance( &*mx.cbegin(), &ddv );
    return std::accumulate( ddv.begin(), ddv.end(), val, [i,&ddv]( const max_value &val, const dvect &dv ) {
        auto j = std::distance( &*ddv.cbegin(), &dv );
        return std::accumulate( dv.begin(), dv.end(), val, [i,j,&dv]( const max_value &val, const double &d ) {
            auto k = std::distance( &*dv.cbegin(), &d );
            return val << max_value( i, j, k, d );
        } );
    } );
} );

live example. Code could be simplified if C++14 or later allowed but I am not sure that it would worse the effort and data reorganization most probably would work better (you would be able to use std::max_element() on singe vector for example). On another side this layout supports jagged matrix as shown on example (different size subarrays)

Answer 2

Here is how I would do it, by looping over the matrix, checking for highest values, and recording its indexes.

size_t highestI = 0;
size_t highestJ = 0;
size_t highestK = 0;

double highestValue = -std::numeric_limits<double>::infinity(); // Default value (Include <limits>)

for (size_t i = 0; i < mountain_table.size(); ++i)
{
    for (size_t j = 0; j < mountain_table[i].size(); ++j)
    {
        for (size_t k = 0; k < mountain_table[i][j].size(); ++k)
        {
            if (mountain_table[i][j][k] > highestValue)
            {
                highestValue = mountain_table[i][j][k]; // Highest 
                // value needed to figure out highest indexes
                // Stores the current highest indexes
                highestI = i; 
                highestJ = j;
                highestK = k;
            }
        }
    }
}

This may not be the most efficient algorithm, but it gets the job done in an understandable way.

Answer 3

Since the max_element function is pretty short and easy to implement, I would suggest to write something similar yourself to fit your exact scenario.

// For types like this I would suggest using a type alias
using Vector3d = std::vector<std::vector<std::vector<double>>>;

std::array<size_t, 3> max_element(const Vector3d& vector) {
    std::std::array<size_t, 3> indexes;
    double biggest = vector[0][0][0];
    for (unsigned i = 0; i < vector.size(); ++i)
        for (unsigned j = 0; j < vector[i].size(); ++j)
            for (unsigned k = 0; k < vector[i][j].size(); ++k)
                if (value > biggest) {
                    biggest =  value;
                    indexes = { i, j, k };
                }
    return indexes;
}

One other suggestion I could give you is to write your custom class Vector3d, with convenient functions like operator()(int x, int y, int z) etc. and save the data internally in simple vector<double> of size width * height * depth.

Answer 4

I'd suggest to linearize your data in order to be able to use standard algorithms. The idea is to provide a couple of functions to get an index from 3D coords and vice et versa:

template<class T>
class Matrix3D // minimal
{
public:
    using value_type = T;
    using iterator   = std::vector<value_type>::iterator;

private:
    std::vector<value_type> _data;
    size_t _sizex, _sizey, _sizez;

    size_t index_from_coords(size_t x, size_t y, size_t z) const
    {
        return x*_sizex*_sizey + y*_sizey + z;
    }
    std::tuple<size_t, size_t, size_t> coords_from_index(size_t index) const
    {
        const size_t x = index / (_sizex * _sizey);
        index = index % x;
        const size_t y = index / _sizey;
        const size_t z = index % _sizey;
        return make_tuple(x, y, z);
    }

public:
    Matrix3D(size_t sizex, sizey, sizez) : _sizex(sizex), ... {}
    T& operator()(size_t x, size_t y, size_t z) // add const version
    {
        return _data[index_from_coords(x, y, z)];
    }
    std::tuple<size_t, size_t, size_t> coords(iterator it)
    {
        size_t index = std::distance(begin(_data), it);
        return coords_from_index(index);
    }
    iterator begin() { return begin(_data); }
    iterator end()   { return end(_data);   }
}

Usage:

Matrix3D<double> m(3, 3, 3);
auto it = std::max_element(m.begin(), m.end()); // or min, or whatever from http://en.cppreference.com/w/cpp/header/algorithm
auto coords = m.coords(it);
std::cout << "x=" << coords.get<0>() << ... << "\n";

This is untested and incomplete code to give you a kickstart into better data design. i'd be happy to answer further questions about this idea in the comment below ;)

Answer 5

std::size_t rv[3] = {0};
std::size_t i = 0;
double max_value = mountain_table[0][0][0];
for (const auto& x : mountain_table) {
  std::size_t j = 0;
  for (const auto& y : x) {
    auto it = std::max_element(y.begin(), y.end());
    if (*it > max_value) {
      rv[0] = i; rv[1] = j; rv[2] = it - y.begin();
      max_value = *it;
    }
    ++j;
  }
  ++i;
}

Answer 6

You should use "for" loop , because you don't have 3d vector.

for (size_t i = 0; i <mountain_table.size(); ++i)
{
  for (size_t j = 0; j < mountain_table[i].size() ++j)
    {
     // find max element index k here and check if it is maximum.
     // If yes save i, j, k and update max val
    }
}