查找矢量矢量的最大/最小值

Question

尋找矢量矢量最大/最小項的最高效和標準（C++ 11/14）方法是什麼？

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

在對需要的最大元件

有用分鐘元件是

Answer 1

任何有效的方式來計算在2 d陣列（在最大元素或載體的的情況下）涉及的複雜度爲O(n^2)，不管你做什麼，因爲計算涉及n*n元素之間的比較。就易用性而言的最佳方式是在矢量的矢量上使用std::max_element。我不會鑽研details.Here是reference.

Answer 2

最簡單的方法是首先有一個函數以確定一個向量的最大/最小元素，說稱爲函數：

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

通過引用傳遞（爲只有閱讀目的）在這種情況下會有更多的時間和空間效率（你不希望你的功能複製整個矢量）。因此，在你的函數來確定最大/向量的向量的元素分鐘，你將有一個嵌套循環，如：

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 

與上述解決方案的問題是它的低效率。據我所知，這個算法一般會運行在O（n^2log（n））效率上，這是非常不起眼的。但當然，這仍然是一個解決方案。儘管可能有標準算法可以爲你找到一個向量的最大值/最小值，但編寫自己的向量總是更加完成，而使用給定通常不會提高效率，因爲算法通常是相同的（對於決定最大/最小值的小函數）。事實上，從理論上講，標準函數的運行速度會稍微慢一些，因爲這些函數是必須確定它在運行時處理的類型的模板。

Answer 3

您必須至少查看每個元素，因此，如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 4

使用accumulate功能你可以寫：

#include <algorithm> 
#include <iostream> 
#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; 
} 

但我更喜歡的好，老for循環。

的例子可以被擴展到發現無論是最小值和最大值：

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

不幸的是矢量的矢量不連續存儲在存儲器中，所以你沒有包含所有值的單個塊（這是矢量向量不是矩陣的好模型的原因之一）。

如果包含很多元素，則可以利用矢量矢量。

由於每個子向量都是自治的，因此您可以使用std::async來異步填充包含每個子向量的最大值的期貨向量。

Answer 5

這是一個多線程解決方案，它爲一般類型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 6

如果您創建一個自定義的迭代器遍歷您vector的vector的所有double，一個簡單的std::minmax_element做的工作

迭代器是一樣的東西：

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

和使用可能

// 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

Answer 7

可以與埃裏克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到最大。

（範圍-V3確實有minmax_element的實現，但不幸的是，它需要一個ForwardRange和視圖::只能加入給我一個InputRange，所以我不能使用它。）如果你使用的

Answer 8

boost::multi_array<double, 2>代替std::vector<std::vector<double>>，這將是簡單：

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

Live demo。

Answer 9

的滑動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 10

假設我們有一個名爲some_values矢量，如下所示

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

限定一維矢量如下所示

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

然後找出最大/最小元素如下圖所示

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

該一維向量現在你得到的最大/最小元素如下

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