CODEWITHSUNDEEP
c++c++11vectormaxmin
Humam Helfawi
Humam Helfawi

Reputation: 20294

Find max/min of vector of vectors

What is the most efficient and standard (C++11/14) way to find the max/min item of vector of vectors?

std::vector<std::vector<double>> some_values{{5,0,8},{3,1,9}};

the wanted max element is 9

the wanted min element is 0

Upvotes: 16

Views: 19738

Answers (11)

manlio
manlio

Reputation: 18952

Using the accumulate function you could write:

#include <iostream>
#include <numeric>
#include <vector>

int main()
{
  std::vector<std::vector<double>> m{ {5, 0, 8}, {3, 1, 9} };

  double x = std::accumulate(m.begin(), m.end(), m[0][0],
                             [](double max, const std::vector<double> &v)
                             {
                               return std::max(max,
                                               *std::max_element(v.begin(),
                                                                 v.end()));
                             });

  std::cout << x << '\n';
  return 0;
}

but I'd prefer the good, old for-loop.

The example can be extended to find both the min and max values:

std::accumulate(m.begin(), m.end(),
                std::make_pair(m[0][0], m[0][0]),
                [](std::pair<double, double> minmax, const std::vector<double> &v)
                {
                  auto tmp(std::minmax_element(v.begin(), v.end()));

                  return std::make_pair(
                    std::min(minmax.first, *tmp.first),
                    std::max(minmax.second, *tmp.second));
                });

(in real code you have to handle the empty-vector case)

Unfortunately a vector of vector isn't stored contiguously in memory, so you haven't a single block containing all the values (this is one of the reasons why a vector of vector isn't a good model for a matrix).

You can take advantage of a vector of vector if it contains a lot of elements.

Since each sub-vector is autonomous, you could use std::async to fill asynchronously a vector of futures containing the max value of each sub-vector.

Upvotes: 5

BadCatss
BadCatss

Reputation: 101

vector<vector<int>> vv = { vector<int>{10,12,43,58}, vector<int>{10,14,23,18}, vector<int>{28,47,12,90} };
vector<vector<int>> vv1 = { vector<int>{22,24,43,58}, vector<int>{56,17,23,18}, vector<int>{11,12,12,90} };
int matrix1_elem_sum=0;
int matrix2_elem_sum = 0;
for (size_t i = 0; i < vv.size(); i++)
{
    matrix1_elem_sum += std::accumulate(vv[i].begin(), vv[i].end(), 0);
    matrix2_elem_sum += std::accumulate(vv1[i].begin(), vv1[i].end(), 0);

}
cout << matrix1_elem_sum <<endl;
cout << matrix2_elem_sum << endl;
int summ = matrix1_elem_sum + matrix2_elem_sum;
cout << summ << endl;

or optimazed variant:

vector<vector<int>> vv = { vector<int>{10,12,43,58}, vector<int>{10,14,23,18}, vector<int>{28,47,12,90} };
vector<vector<int>> vv1 = { vector<int>{22,24,43,58}, vector<int>{56,17,23,18}, vector<int>{11,12,12,90} };
int summ=0;
int matrix2_elem_sum = 0;
for (size_t i = 0; i < vv.size(); i++)
{
    summ += std::accumulate(vv[i].begin(), vv[i].end(), 0)+ std::accumulate(vv1[i].begin(), vv1[i].end(), 0);


}
cout << summ << endl;
 }

Upvotes: 0

oya163
oya163

Reputation: 1529

Lets say we have a vector named some_values, as shown below

7 4 2 0 
4 8 10 8 
3 6 7 6 
3 9 19* 14

define a one-dimensional vector as shown below

vector<int> oneDimVector;
for(int i = 0; i < 4; i++){
    for(int j = 0; j < 4; j++){
        oneDimVector.push_back(some_values[i][j]);
    }
}

Then find out a maximum/minimum element in that one-dimensional vector as shown below

vector<int>::iterator maxElement = max_element(oneDimVector.begin(),oneDimVector.end());
vector<int>::iterator minElement = min_element(oneDimVector.begin(),oneDimVector.end());

Now you get the max/min elements as below

cout << "Max element is " << *maxElement << endl;
cout << "Min element is " << *minElement << endl;

Upvotes: 0

Chen OT
Chen OT

Reputation: 3614

The plain for loop way:

T max_e = std::numeric_limits<T>::min();
for(const auto& v: vv) {
    for(const auto& e: v) {   
        max_e = std::max(max_e, e);
    }
}

Upvotes: 7

Daniel
Daniel

Reputation: 8441

Here's a multi-threaded solution that returns an iterator (or throws) to the maximum for general type T (assuming operator< is defined for T). Note the most important optimisation is to perform the inner max operations on the 'columns' to exploit C++'s column-major ordering.

#include <vector>
#include <algorithm>

template <typename T>
typename std::vector<T>::const_iterator max_element(const std::vector<std::vector<T>>& values)
{
    if (values.empty()) throw std::runtime_error {"values cannot be empty"};

    std::vector<std::pair<typename std::vector<T>::const_iterator, bool>> maxes(values.size());

    threaded_transform(values.cbegin(), values.cend(), maxes.begin(),
                       [] (const auto& v) {
                           return std::make_pair(std::max_element(v.cbegin(), v.cend()), v.empty());
                       });

    auto it = std::remove_if(maxes.begin(), maxes.end(), [] (auto p) { return p.second; });

    if (it == maxes.begin()) throw std::runtime_error {"values cannot be empty"};

    return std::max_element(maxes.begin(), it,
                            [] (auto lhs, auto rhs) {
                                return *lhs.first < *rhs.first;
                            })->first;
}

threaded_transform is not part of the standard library (yet), but here's an implementation you could use.

#include <vector>
#include <thread>
#include <algorithm>
#include <cstddef>

template <typename InputIterator, typename OutputIterator, typename UnaryOperation>
OutputIterator threaded_transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op, unsigned num_threads)
{
    std::size_t num_values_per_threads = std::distance(first, last) / num_threads;

    std::vector<std::thread> threads;
    threads.reserve(num_threads);

    for (int i = 1; i <= num_threads; ++i) {
        if (i == num_threads) {
            threads.push_back(std::thread(std::transform<InputIterator,
                                      OutputIterator, UnaryOperation>,
                                      first, last, result, op));
        } else {
            threads.push_back(std::thread(std::transform<InputIterator,
                                      OutputIterator, UnaryOperation>,
                                      first, first + num_values_per_threads,
                                      result, op));
        }
        first  += num_values_per_threads;
        result += num_values_per_threads;
    }

    for (auto& thread : threads) thread.join();

    return result;
}

template <typename InputIterator, typename OutputIterator, typename UnaryOperation>
OutputIterator threaded_transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op)
{
    return threaded_transform<InputIterator, OutputIterator, UnaryOperation>(first, last, result, op, std::thread::hardware_concurrency());
}

Upvotes: 8

edflanders
edflanders

Reputation: 223

You can do it pretty easily with Eric Niebler's range-v3 library (which obviously isn't standard yet, but hopefully will be in the not-too-distant future):

vector<vector<double>> some_values{{5,0,8},{3,1,9}};

auto joined = some_values | ranges::view::join;
auto p = std::minmax_element(joined.begin(), joined.end());

p.first is an iterator to the min element; p.second to the max.

(range-v3 does have an implementation of minmax_element, but unfortunately, it requires a ForwardRange and view::join only gives me an InputRange, so I can't use it.)

Upvotes: 5

fahimg23
fahimg23

Reputation: 86

The simplest method would be to first have a function to determine the max/min elements of one vector, say a function called:

    double getMaxInVector(const vector<double>& someVec){}

Passing by reference (for reading purposes only) in this case will be a lot more time and space efficient (you don't want your function copying an entire vector). Thus in your function to determine max/min element of a vector of vectors, you would have a nested loop, such as:

    for(size_t x= 0; x < some_values.size(); x++){
        for(size_t y = 0; y < x.size(); y++){
            // y represents the vectors inside the vector of course
            // current max/min = getMax(y)
            // update max/min after inner loop finishes and x increments
            // by comparing it with previous max/min

The problem with the above solution is its inefficiency. From my knowledge, this algorithm will generally run on O(n^2log(n)) efficiency, which is quite unimpressive. But of course, it is still a solution. Although there might be standard algorithms that can find the max/min of a vector for you, it's always more accomplishing to write your own, and using the given will usually do nothing in terms of improving efficiency because the algorithm will generally be the same (for small functions that determine max/min). In fact, theoretically, standard functions would run marginally slower since those functions are templates which have to determine the type it is dealing with at run-time.

Upvotes: 1

Yola
Yola

Reputation: 19035

You must at least look at every element, so, as Anony-mouse mentioned, complexity will be at least O(n^2).

#include <vector>
#include <limits>
#include <algorithm>

int main() {
    std::vector<std::vector<double>> some_values;
    double max = std::numeric_limits<double>::lowest();
    for (const auto& v : some_values)
    {
        double current_max = *std::max_element(v.cbegin(), v.cend());
        max = max < current_max ? current_max : max; // max = std::max(current_max, max);
    }
}

Upvotes: 5

Chris Drew
Chris Drew

Reputation: 15334

If you used a boost::multi_array<double, 2> instead of a std::vector<std::vector<double>> it would be as simple as:

auto minmax = std::minmax_element(values.data(), values.data() + values.num_elements());

Live demo.

Upvotes: 6

Jarod42
Jarod42

Reputation: 217850

If you create a custom iterator to iterate over all double of your vector of vector, a simple std::minmax_element do the job

iterator is something like:

class MyIterator : public std::iterator<std::random_access_iterator_tag, double>
{
public:
    MyIterator() : container(nullptr), i(0), j(0) {}

    MyIterator(const std::vector<std::vector<double>>& container,
               std::size_t i,
               std::size_t j) : container(&container), i(i), j(j)
    {
        // Skip empty container
        if (i < container.size() && container[i].empty())
        {
            j = 0;
            ++(*this);
        }
    }
    MyIterator(const MyIterator& rhs) = default;
    MyIterator& operator = (const MyIterator& rhs) = default;

    MyIterator& operator ++() {
        if (++j >= (*container)[i].size()) {
            do {++i;} while (i < (*container).size() && (*container)[i].empty());
            j = 0;
        }
        return *this;
    }
    MyIterator operator ++(int) { auto it = *this; ++(*this); return it; }

    MyIterator& operator --() {
        if (j-- == 0) {
            do  { --i; } while (i != 0 && (*container)[i].empty());
            j = (*container)[i].size();
        }
        return *this;
    }
    MyIterator operator --(int) { auto it = *this; --(*this); return it; }

    double operator *() const { return (*container)[i][j]; }


    bool operator == (const MyIterator& rhs) const {
        return container == rhs.container && i == rhs.i && j == rhs.j;
    }
    bool operator != (const MyIterator& rhs) const { return !(*this == rhs); }

private:
    const std::vector<std::vector<double>>* container;
    std::size_t i;
    std::size_t j;
};

And usage may be

// Helper functions for begin/end
MyIterator MyIteratorBegin(const std::vector<std::vector<double>>& container)
{
    return MyIterator(container, 0, 0);
}

MyIterator MyIteratorEnd(const std::vector<std::vector<double>>& container)
{
    return MyIterator(container, container.size(), 0);
}

int main() {
    std::vector<std::vector<double>> values = {{5,0,8}, {}, {3,1,9}};

    auto b = MyIteratorBegin(values);
    auto e = MyIteratorEnd(values);
    auto p = std::minmax_element(b, e);

    if (p.first != e) {
        std::cout << "min is " << *p.first << " and max is " << *p.second << std::endl;
    }
}

Live example

Upvotes: 4

Anony-mouse
Anony-mouse

Reputation: 2151

Any efficient way to calculate the maximum element in a 2-D array(or vector in your case) involves a complexity of O(n^2) irrespective of what you do, as the calculation involves a comparison between n*n elements.Best way in terms of ease of use is to use std::max_element on the vector of vectors.I will not delve into details.Here is the reference.

Upvotes: 4

Related Questions