如何以最有效和标准的方式（C++11/14）找到嵌套向量中的最大/最小值？
std::vector<std::vector<double>> some_values{{5,0,8},{3,1,9}};
所需的最大元素为9
所需的最小元素为0
11个回答
8
这是一个多线程解决方案，返回一个迭代器（或抛出异常）来获取通用类型
T的最大值（假设已定义operator<用于T）。请注意，最重要的优化是在“列”上执行内部max操作，以利用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());
}
- Daniel
2
1请注意，如果内部向量为空，则会失败。 - Jarod42
@Jarod42 你说得对，谢谢。现在应该适用于所有情况（或抛出异常）...不再那么漂亮了 :( - Daniel
6
如果使用
boost::multi_array<double, 2> 而不是 std::vector<std::vector<double>>，那么实现起来就非常简单了：auto minmax = std::minmax_element(values.data(), values.data() + values.num_elements());
实时演示。
- Chris Drew
1
如果Boost可用，这是一个有趣的答案。对我来说它是可用的。我会去看看，非常感谢。 - Humam Helfawi
6
使用普通的for循环方法：
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);
}
}
- Chen OT
1
2简洁明了。在我看来，这是最好的答案。有时候简单就是最好的选择。 - pbible
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);
}
}
- Yola
2
9寻找最小值和最大值的复杂度为O(n)，而不是O(n^2)。需要两个循环来完成并不重要，每个元素仅被检查一次。 - Pete Becker
1请注意，如果内部向量为空，则会失败。 - Jarod42
4
任何计算二维数组（或者在你的情况下是向量）中最大元素的高效方式都需要O(n^2)的复杂度，因为计算涉及到n*n个元素之间的比较。从易用性角度来看，最好的方法是在向量的向量上使用std::max_element。我不会深入讨论细节。这里是参考链接。
- Anony-mouse
17
17实际上这只是一个
O(N)的算法，其中N是待比较的元素总数。事实上，这些元素在物理上以K个向量的形式排列，每个向量平均有N/K个子元素，这可能会有点误导性。 - TemplateRex2@TemplateRex 是对的。这是一个线性复杂度问题
O(n)。我不知道为什么有人说是二次方的。 - pbible1@Anony-mouse 标准库的
std::min_element 的复杂度被定义为与总元素数量相关的比较次数。已经解释过多次，在向量中嵌套向量的布局对此没有影响。因此，在修复之前，该问题将被投票下降。 - TemplateRex1@Anony-mouse，我认为嵌套数据结构让你困惑了。如果我有100个元素，无论它们是100个元素的1个列表还是10个10个元素的列表，对于我来说都需要检查所有100个元素。无论如何存储他们，该问题在元素数量方面是线性的问题。 - pbible
2@Anony-mouse，行和列都是无关紧要的。复杂度为
O(n)，其中r和c的任何值都可以满足r*c=n。个人认为，将复杂度报告为O(n^2)是具有误导性的。我明白你的意思，但我认为仅仅因为需要嵌套循环就说它是二次方会让人们感到困惑。 - pbible显示剩余12条评论
4
使用
accumulate函数，您可以编写以下代码：#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;
}
但我更喜欢使用好用的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异步地填充包含每个子向量最大值的future向量。
- manlio
2
2很好。只有两件事情：
accumulate需要#include <numeric>而不是#include <algorithm>。此外，你需要在lambda中添加一个if来处理空向量。 - Martin Morterol@MartinMorterol 你说得对，我已经稍微修正了答案。谢谢。 - manlio
4
如果您创建一个自定义迭代器来遍历您的
迭代器是这样的：
vector of 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;
}
}
- Jarod42
4
您可以使用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，所以我无法使用它。）
- edflanders
1
最简单的方法是首先有一个函数来确定一个向量中的最大/最小元素，假设这个函数叫做：
在这种情况下，仅用于读取目的的引用传递会更加时间和空间有效（您不希望函数复制整个向量）。因此，在确定向量向量的最大/最小元素的函数中，您将具有嵌套循环，例如：
上述解决方案的问题在于效率低下。据我所知，该算法通常的运行效率为O(n^2log(n))，相当不理想。但当然，它仍然是一个解决方案。虽然可能有标准算法可以为您找到向量的最大/最小值，但编写自己的算法总是更有成就感的，而使用给定的算法通常不会对提高效率产生任何影响，因为算法通常是相同的（用于确定最大/最小值的小函数）。实际上，从理论上讲，标准函数的运行速度会稍慢，因为这些函数是模板，必须在运行时确定它正在处理的类型。
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))，相当不理想。但当然，它仍然是一个解决方案。虽然可能有标准算法可以为您找到向量的最大/最小值，但编写自己的算法总是更有成就感的，而使用给定的算法通常不会对提高效率产生任何影响，因为算法通常是相同的（用于确定最大/最小值的小函数）。实际上，从理论上讲，标准函数的运行速度会稍慢，因为这些函数是模板，必须在运行时确定它正在处理的类型。
- fahimg23
0
假设我们有一个名为 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;
- oya163
2
这两个for循环非常低效。正在发生重新分配。 - Humam Helfawi
我知道这并不高效，但是我回答了这个问题，是为了帮助那些正在学习cpp的新手，我的答案侧重于功能而非效率。 - oya163
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
std::minmax_element。 - Jarod42