Finden Sie max/min der Vektor von Vektoren

Einer effizienten Art und Weise zur Berechnung der maximalen element in einem 2-D-array(oder vector in deinem Fall) mit einer Komplexität von O(n^2) unabhängig von dem, was Sie tun, wie die Berechnung mit einem Vergleich zwischen n*n Elemente.Beste Weg, in Bezug auf Benutzerfreundlichkeit ist die Verwendung std::max_element auf den Vektor von Vektoren.Ich werde nicht tiefer in details einzusteigen.Hier ist die Referenz.

Wenn Sie ein boost::multi_array<double, 2> statt einer std::vector<std::vector<double>> es wäre so einfach wie:

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

Live-demo.

Wenn Sie erstellen Sie eine benutzerdefinierte iterator zum Durchlaufen aller double Ihrer vector von vector eine einfache std::minmax_element den job

iterator ist so etwas wie:

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

Und-Nutzung

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

Mithilfe der sammeln Funktion, die Sie schreiben konnte:

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

aber ich würde lieber die gute alte for-Schleife.

Das Beispiel kann erweitert werden, um sowohl der min-und max-Werte:

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

Leider ein Vektor, der Vektor ist nicht im Speicher zusammenhängend gespeichert, so dass Sie noch nicht einen einzigen block, welches alle Werte (dies ist einer der Gründe, warum ein Vektor, der Vektor ist nicht ein gutes Modell für eine matrix).

Können Sie die Vorteile der Vektor der Vektor enthält eine Menge von Elementen.

Da jeder sub-Vektor ist autonom, Sie könnte verwenden std::async zu füllen asynchron Vektor der futures mit der max-Wert der einzelnen sub-Vektor.

Die einfachste Methode wäre zunächst eine Funktion, um zu bestimmen, die min/max-Elemente in einem Vektor, sagen wir, eine Funktion, die aufgerufen wird:

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

Durch Verweis übergeben wird (lesend) in diesem Fall viel mehr Zeit und Platz sparend (Sie nicht möchten, dass Ihre Funktion das kopieren einer kompletten Vektor). Damit in Ihrer Funktion zu bestimmen, min - /max-element ein Vektor von Vektoren, hätten Sie eine verschachtelte Schleife, wie:

    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

Das problem mit der oben genannten Lösung ist seine Ineffizienz. Von meinem wissen, ist dieser Algorithmus wird im Allgemeinen eine Laufzeit auf O(n^2log(n)) Effizienz, die ist Recht unscheinbar. Aber natürlich ist es immer noch eine Lösung. Obwohl möglicherweise gibt es standard-algorithmen, das finden der min/max eines Vektor für dich, es ist immer mehr vollbringen, ein eigenes zu schreiben, und mit der angegeben wird in der Regel nichts zu tun in Bezug auf die Verbesserung der Effizienz, da der Algorithmus im Allgemeinen der gleiche (für kleine Funktionen, die bestimmen, max/min). In der Tat, theoretisch, standard-Funktionen wäre geringfügig langsamer ausgeführt, da diese Funktionen sind Vorlagen, die für die Bestimmung der Art ist es den Umgang mit run-time.

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;

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