Merge sort na vectorach - iterator out of range

Odpowiedz Nowy wątek
2019-01-11 22:50
0

Czemu ten kod wyrzuca błąd wyjścia iteratora poza zakres? (offset out of range)
problem chyba jest w pętli
wywołuje f(dane)

vector <int> merge(vector <int> veca, vector <int> vecb)
{
    vector <int> result;
    vector<int>::iterator it1 = veca.begin();
    vector<int>::iterator it2 = vecb.begin();
    while (it1 < veca.end()-1 && it2 < vecb.end()-1)   /* tu dzieje się coś nie tak */
    {

            if (*it1 < *it2)
            {
                result.push_back(*it1);
                if (it1 < veca.end() - 1)
                {
                    it1 += 1;
                }
            }

            if (*it1 > *it2)
            {
                result.push_back(*it2);
                if (it2 < vecb.end() - 1)
                {
                    it2 += 1;
                }
            }

    }
    return result;

}
vector <int> f (vector <int> vec){
    if(vec.size()==1){
        return vec;
    }
    else{
        int n = vec.size() / 2;
        vector <int> a;
        vector <int> b;
        a.insert(a.begin(), vec.begin(), vec.begin() + n);
        b.insert(b.begin(), vec.begin() + n, vec.end());
        return merge(f(a), f(b));
    }
}
To ma być merge-sort? - lion137 2019-01-12 01:46
a patrzyłeś pod debuggerem? - Miang 2019-01-12 11:00
w debuggerze wyświetla przy drugim obrocie pętli: <nie można odczytać pamięci> ale nie mam pojęcia dlaczego - Suhack 2019-01-12 12:31
Wydawało mi się że w vectorze można było zwiększać iterator i pokazywał on wtedy na następny element, a tu rzuca błędami - Suhack 2019-01-12 12:33
Drugim obrocie pętli? Kiedy on ani razu tam nie wchodzi. - Delor 2019-01-12 19:33

Pozostało 580 znaków

2019-01-12 22:14
0

Dlaczego Delor ? U mnie weszło. Może to zależy o danych, które wylosuje.
Napiszesz dlaczego według ciebie nie wchodzi ? Nie można tak porównywać wskaźników czy co ?

Pozostało 580 znaków

2019-01-12 22:30
1

Funkcja f() rekurencyjnie wywołuje f() z wektorami o coraz mniejszej liczbie elementów. Dopiero jak dojdzie do jednoelementowych to wywoła merge().
Ten warunek:

while (it1 < veca.end()-1 && it2 < vecb.end()-1)

nie spełni się w takim przypadku i funkcja merge() zwróci puste result.
Przy pustym wektorze (ale to już w innym wywołaniu merge()) natrafiasz na to: veca.end()-1.

edytowany 1x, ostatnio: Delor, 2019-01-12 22:30
no ale to się wysypuje już na pierwszym podziale na drugi obrocie pętli i pytam dlaczego jest poza zakresem - Suhack 2019-01-12 22:31
W jakiej kolejności wywołają się funkcje w tej linii: return merge(f(a), f(b));? - Delor 2019-01-12 22:34
czyli powinno być while (it1< veca.end() && it2< vecb.end() ) ? - Suhack 2019-01-12 22:35
to co piszesz ma sens tylko czemu to się wykonuje i wyrzuca, że iterator poza zakresem - Suhack 2019-01-12 22:38
Ostatnie zdanie... veca.end()-1 - Delor 2019-01-12 22:41

Pozostało 580 znaków

2019-01-12 22:39
1

Chcesz zobaczyć czy iterator wskazuje na koniec kontenera? Do tego masz == i !=.
< jest do innych zastosowań.

no tak masz rację jaki powinien być warunek przed inkrementacją ?if (it1 != veca.end() ) bo gdy dam taki to jest błąd not deferencable - Suhack 2019-01-12 22:45
Popraw algorytm. Gdy przestaniesz "bawić się" pustymi wektorami to część błędów zniknie. - Delor 2019-01-12 22:54

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0