找到向量矢量的最大值/最小值

Question

找到向量向量的最大/最小项目的最有效和标准(C++ 11/14)方法是什么？

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

想要的最大元素是9

想要的min元素是0

Answer 1

这是一个多线程解决方案,它将迭代器(或抛出)返回到一般类型的最大值T(假设operator<已定义T).请注意,最重要的优化是对'列'执行内部最大操作以利用C++的列主要排序.

#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 不是标准库的一部分(但是),但这是您可以使用的实现.

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

Answer 2

如果您使用的是a boost::multi_array<double, 2>而不是a,std::vector<std::vector<double>>那将简单如下:

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

现场演示.

Answer 3

简单的for loop方法：

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

Answer 4

计算二维数组(或你的情况下的向量)中的最大元素的任何有效方法都涉及复杂性而O(n^2)不管你做什么,因为计算涉及n*n元素之间的比较.在易用性方面的最佳方法是std::max_element在矢量矢量上使用.我不会深入研究细节.这里是参考.

Answer 5

您至少必须查看每个元素，因此，正如Anony-mouse所提到的那样，复杂度至少应为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);
    }
}

Answer 6

你可以很容易地使用 Eric Niebler 的range-v3库（这显然不是标准的，但希望在不久的将来会实现）：

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是最小元素的迭代器；p.second到最大。

（range-v3 确实有 minmax_element 的实现，但不幸的是，它需要一个 ForwardRange，而 view::join 只给我一个 InputRange，所以我不能使用它。）