Trouver max/min de vecteur de vecteurs

Tout moyen efficace pour calculer le maximum d'élément dans un tableau 2d(ou un vecteur dans votre cas) implique une complexité de O(n^2) indépendamment de ce que vous faites, comme le calcul implique une comparaison entre n*n éléments.Meilleure façon en termes de facilité d'utilisation est l'utilisation de std::max_element sur le vecteur de vecteurs.Je ne vais pas entrer dans les détails.Voici la de référence.

Si vous avez utilisé un boost::multi_array<double, 2> au lieu d'un std::vector<std::vector<double>> il serait aussi simple que:

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

Démonstration en direct.

Si vous créer un itérateur pour parcourir tous double de votre vector de vector, une simple std::minmax_element faire le travail

itérateur est quelque chose comme:

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

Et l'utilisation peut être

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

À l'aide de la s'accumuler fonction, vous pouvez écrire:

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

mais je préfère la bonne, vieille de boucle.

L'exemple peut être étendu à trouver à la fois les valeurs min et max:

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

Malheureusement un vecteur de vecteur n'est pas stockés de manière contiguë en mémoire, de sorte que vous n'avez pas un seul bloc contenant toutes les valeurs (c'est une des raisons pour lesquelles un vecteur de vecteur n'est pas un bon modèle pour une matrice).

Vous pouvez profiter d'un vecteur de vecteur si elle contient beaucoup d'éléments.

Puisque chaque sous-vecteur est autonome, vous pouvez utiliser std::async à remplir de manière asynchrone un vecteur de contrats à terme contenant la valeur max de chaque sous-vecteur.

La méthode la plus simple serait d'abord une fonction pour déterminer la valeur max/min des éléments d'un vecteur, dire une fonction appelée:

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

Le passage par référence (lecture seulement) dans ce cas, ils seront beaucoup plus de temps et plus efficace de l'espace (vous ne voulez pas que votre fonction copier l'intégralité d'un vecteur). Ainsi, dans votre fonction pour déterminer le max/min élément d'un vecteur de vecteurs, vous auriez une boucle imbriquée, tels que:

    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

Le problème avec la solution ci-dessus est son inefficacité. De ma connaissance, cet algorithme est généralement exécuté sur O(n^2log(n)) l'efficacité, ce qui est assez exceptionnel. Mais bien sûr, il est toujours une solution. Bien qu'il pourrait y avoir des algorithmes standard qui peut trouver le max/min de un vecteur pour vous, c'est toujours plus de l'accomplissement de l'écriture de vos propres, et à l'aide de la donner, l'habitude de ne rien en termes d'amélioration de l'efficacité, car l'algorithme sera généralement le même (pour les petites fonctions qui déterminent max/min). En fait, théoriquement, fonctions standard irait un peu moins rapide puisque ces fonctions sont des modèles qui ont à déterminer le type il s'agit, au moment de l'exécution.

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;

ou optimazed variante:

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