Sortieren einer 2D-Vektor mit bestimmten Kriterien std :: sort

Question

Ich habe eine Codierung Problem gestoßen eine 2D-Vektor (Matrix) in Bezug auf das Sortieren einer gewünschten Kriterien std::sort aus der Bibliothek mit algorithm

Zum Beispiel lassen Sie uns sagen, dass ich ein 2D haben

Vektor

1,8,3 
1,9,1 
1,4,2 
    ^

und ich möchte es von der 3. Spalte sortieren (nach Kriterien Beispiel Wachstum) So nach dem sortieren ich möchte eine Matrix haben:

1,9,1 
1,4,2 
1,8,3 
    ^

Ich weiß, dass die dritte Funktion in std::sort gesendet werden muss, um Sortierkriterien in std::sort anzugeben. Wenn es ein 1D vector wäre, wäre das kein Problem. Ich würde ein Lambda innerhalb std::sort mit 2 Parametern machen, sie vergleichen und wahr/falsch zurückgeben.

Jetzt können Sie das Problem sehen, das ich gegenüberstelle, wie kann ich auf bestimmte Elemente innerhalb einer Matrix, in meinem Fall dritte Spalte Elemente zugreifen und sie mit std::sort vergleichen?

#include <iostream> 
#include <vector> 
#include <algorithm> 

void printMatrix(std::vector<std::vector<int>> m) { 
    for(int i = 0; i < m.size(); i++) { 
     for(int j = 0; j < m[i].size(); j++) { 
      std::cout << m[i][j] << " "; 
     } 
     std::cout << std::endl; 
    } 
} 

int main() { 
    std::vector<std::vector<int>> m{ 
     {1,8,3}, 
     {1,9,1}, 
     {1,4,2} 
    }; 

    std::sort(m.begin(), m.end(), [](int a, int b) { // error 
       // ??? 
    }); 
    printMatrix(m); 

    return 0; 
} 

Ich möchte keine anderen externen Bibliotheken verwenden, um dieses Problem zu lösen.

Jede Hilfe wird sehr geschätzt! :)

Answer 1

std::sort(m.begin(), m.end(), [](int a, int b) { // error 
       // ??? 
    }); 

Die value_type der von m.begin() und m.end() zurück Iteratoren ist ein std::vector<int>. Daher muss Ihr Lambda diesen Typ für beide Parameter übernehmen.

std::sort(m.begin(), m.end(), 
     [](const std::vector<int>& a, const std::vector<int>& b) { 
       return a.at(2) < b.at(2); 
    }); 

Hinweis: Ich bin mit dem at() Member-Funktion hier nicht Operator [] UB zu verhindern, sollten Sie immer versuchen, fälschlicherweise in einem ungültigen Index zu sortieren durch.

Demo

Answer 2

Wenn Sie eine std::vector<std::vector<int>> sortieren möchten, die Elemente des Containers sind vom Typ std::vector<int>, nicht int. Daher können Sie keine lambda mit der Erklärung

[](int a, int b) { ... } 

verwenden einen solchen Behälter zu sortieren. Sie benötigen ein lambda mit der Erklärung

[](std::vector<int> a, std::vector<int> b) { ... } 

oder

[](std::vector<int> const& a, std::vector<int> const& b) { ... } 

verwenden Mit der ersten Version, da sie Kopien von std::vector zum lambda für jeden Anruf werden am Ende teuer ist. Daher wird empfohlen, die zweite Version zu verwenden.

std::sort(m.begin(), m.end(), [](std::vector<int> const& a, 
           std::vector<int> const& b) { 
    return a.back() < b.back(); 
}); 

Answer 3

Obwohl dies nicht die effizienteste Lösung, die einfachste Sache zu tun wäre, Ihren 2D-Vektor zur Umsetzung (auch bekannt als Matrix) jeden Vektor sortieren und dann wieder umsetzen.Hier ist eine erprobte, Arbeitsfunktion, die dies für Sie tun:

template<typename T> 
void sortColumns(vector<vector<T> > &v){ 
    vector<vector<T> > rv(v[0].size(), vector<T>(v.size())); 
    for(int i = 0; i < v.size(); i++){ 
     for(int j = 0; j < v[i].size(); j++){ 
      rv[j][i] = v[i][j]; 
     } 
    } 
    for(int i = 0; i < rv.size(); i++){ 
     sort(rv[i].begin(), rv[i].end()); 
     for(int j = 0; j < rv[i].size(); j++){ 
      v[j][i] = rv[i][j]; 
     } 
    } 
} 

Auch dies ist nicht die effizienteste oder die modernste Art und Weise eine Matrix von Spalten zu sortieren, aber es funktioniert und ist einfach zu verstehen.