C++ sortuj wektor używając obiektu funkcji

Question

Próbuję posortować wektor v1 za pomocą innego wektora v2. I nie można zawijać moja głowa wokół tego błędu:

terminate called after throwing an instance of 'std::out_of_range'
what(): vector::_M_range_check
Abort trap

podczas uruchamiania tego kodu:

#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std; 

class Comp 
{ 
    public: 
     Comp(vector<double>& inVec): _V(inVec) {} 
     bool operator()(int i, int j) {return (_V.at(i)<_V.at(j));} 
    private: 
     vector<double> _V; 
}; 

int main(int argc, char** argv) 
{ 
    double x1[] = {90.0, 100.0, 80.0}; 
    double x2[] = {9.0, 3.0, 1.0}; 
    vector<double> v1(x1,x1+3); 
    vector<double> v2(x2,x2+3); 

    sort(v1.begin(), v1.end(), Comp(v2)); // sort v1 according to v2 

    for(unsigned int i=0; i<v1.size(); i++) 
    { 
     cout << v1.at(i) << " " << v2.at(i) << endl; 
    } 

    return 0; 
} 

v1 i v2 są tej samej wielkości. Dlaczego błąd out_of_range?

Z góry dziękuję za wszelkie wskazówki.

Answer 1

Wierzę, że problem jest w tym wierszu:

bool operator()(int i, int j) {return (_V.at(i)<_V.at(j));} 

Problem polega na tym, że gdy Algorytm std::sort używa niestandardowego zwrotnego, przechodzi w rzeczywistych wartościach zapisanych w vector w poszczególnych miejscach, a nie indeksy tych lokalizacji w ramach vector. W rezultacie, gdy dzwonisz

sort(v1.begin(), v1.end(), Comp(v2)); // sort v1 according to v2 

Comp komparatora napisałeś będzie coraz przekazywane jako parametry wartości przechowywanych w v1 wektora a następnie spróbuj indeksowanie w tych pozycjach karne v2 wektorze. Ponieważ wartości w v1 są większe niż rozmiar v2, wywołanie _V.at(i) spowoduje zgłoszenie wyjątku out_of_range.

Jeśli chcesz posortować dwa zakresy względem siebie, musisz zastosować inne podejście. Nie jestem świadomy prostego sposobu robienia tego, ale dam ci znać, jeśli o tym myślę.

Answer 2

Rozmiar v1 to tylko 3, ale używasz każdej wartości v2 jako indeksu v1. I jak v2 ma jedną wartość 9, który jest większy niż rozmiar v1, że to, co daje std::out_of_range błąd tu:

bool operator()(int i, int j) {return (_V.at(i)<_V.at(j));} 

std::vector::at funkcja daje std::out_of_range wyjątkiem wskaźnika przekazanego do niej jako argument jest większy niż rozmiar wektora. Oznacza to, że indeks musi być mniejszy niż vector::size().

Answer 3

Podobnie jak w innych odpowiedziach, problemem jest to, że algorytm sortowania przekazuje rzeczywiste wartości do porównania zamiast indeksów.

Oto w jaki sposób można go rozwiązać:

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

using namespace std; 

typedef pair<double, double> Zipped; // Represent an element of two lists 
            // "zipped" together 

// Compare the second values of two pairs 
bool compareSeconds (Zipped i, Zipped j) 
{ 
    return i.second < j.second; 
} 

int main (int argc, char **argv) 
{ 
    double x1[] = { 90, 100, 80 }; 
    double x2[] = { 9, 3, 1 }; 

    vector<double> v1(x1, x1 + 3); 
    vector<double> v2(x2, x2 + 3); 

    vector<Zipped> zipped(v1.size()); // This will be the zipped form of v1 
             // and v2 

    for (int i = 0; i < zipped.size(); ++i) 
    { 
     zipped[i] = Zipped(v1[i], v2[i]); 
    } 

    sort(zipped.begin(), zipped.end(), &compareSeconds); 

    for (int i = 0; i < zipped.size(); ++i) 
    { 
     cout << zipped[i].first << " " << zipped[i].second << endl; 
    } 

    for (int i = 0; i < v1.size(); ++i) 
    { 
     v1[i] = zipped[i].first; 
    } 

    // At this point, v1 is sorted according to v2 

    return 0; 
} 

Answer 4

Ok, teraz jesteś zapewne świadom faktu, że i i j są rzeczywiste wartości przechowywane w vector zamiast indeksów. Jest ku temu dobry powód: sortowanie polega na wartościach, a nie indeksach. Zauważ, że przekazujesz iteratory do metody sort, więc nie ma możliwości, aby wyodrębnić indeks dla ciebie. Oczywiście można uzyskać indeks względem pierwszego iteratora, ale nie ma powodu, aby to robić.

Jednak bądźmy obłąkani przez chwilę i wyobraźmy sobie, że otrzymasz wskaźniki zamiast wartości w swoim komparatorze.Załóżmy, że Twój kod robi to, co chcesz i pomyślmy o następującym scenariuszu:

v1 = {20,10}; v2 = {2,1}

potajemnie zakładać chcesz następujący wynik:

v1 = {10, 20}

prawo? Teraz wyobraź sobie, mam funkcję sortowania dzwonisz i zrobić następujące kroki:

• v2[0] < v2[1] jest fałszywa, tak swap(&v1[0], &v1[1])

To sortowane, prawda? Ale czekaj, jestem szalona funkcja sortowania, więc chcę, aby upewnić się, że sortowane, więc należy wykonać następujące czynności:

• v2[0] < v2[1] jest fałszywa, swap(&v1[0], &v1[1])

I jeszcze:

• v2[0] < v2[1] jest fałszywa, swap(&v1[0], &v1[1])

i znowu, znowu, znowu ...

Czy widzisz problem? Funkcja sortowania ma pewne wymagania i na pewno łamiesz podstawową.

Podejrzewam, trzeba zupełnie innego pojemnika (może std::map z kluczy z vec1 i wartości z vec2) lub przynajmniej coś podobnego vector< pair<double, double> >, dzięki czemu można łatwo sortować albo przez pierwszą lub drugą wartość. Jeśli nie, rozważ utworzenie vector z wartościami z zakresu [0, v2.size()), posortuj je za pomocą komparatora (wartości są równe indeksom, więc wszystko będzie w porządku), a następnie wydrukuj prawidłowe wartości z v1. Ten kod działa poprawnie:

vector<size_t> indices; 
for(size_t i =0; i < v1.size(); ++i) 
{ 
    indices.push_back(i); 
} 

// yes, it works using your original comparator 
sort(indices.begin(), indices.end(), Comp(v2)); 

for(size_t i =0; i < indices.size(); ++i) 
{ 
    cout << v1.at(indices[i]) << " " << v2.at(indices[i]) << endl; 
}