Find max/min of vector of vectors

Question

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

Answer 1

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