Warum erhalte ich Vektor Index außerhalb des zulässigen Bereichs Fehler in der Merge Sort?

Question

void merge(vector<int> dst,vector<int> first,vector<int> second)
{
    int i=0,j=0;

    while(i<first.size()&&j<second.size())
    {
        if(first[i]<second[j])
        {
            dst.push_back(first[i]);
            i++;
        }
        else
        {
            dst.push_back(second[j]);
            j++;
        }
    }
    while(i<first.size()
    dst.push_back(first[i++]);

    while(j<second.size())
    dst.push_back(second[j++]);
}

void mergeSort(vector<int> &a)
{   
    size_t sz = a.size();
    cin.get();
    if(sz>1)
    {   
        vector<int> first(&a[0],&a[sz/2]);
        vector<int> second(&a[(sz/2)+1],&a[sz-1]);

        mergeSort(first);
        mergeSort(second);

        merge(a,first,second);  
    }
}

void MergeSort(int* a,size_t size)
{
   vector<int> s(&a[0],&a[size-1]);
   mergeSort(s);
}

Kann jemand helfen mir, was ist das Problem mit diesem Code? Ich erhalte Vektorindex outof Bereichsfehler.

Answer 1

sind Ihre Untervektoren angegeben falsch.
Denken Sie daran, die Iteratoren den Anfang einer nach dem Ende angeben.

So dieser Wille verfehlt das mittlere Element und das letzte Element in dem Vektor.
Und ist auch für die wirklich kurze Vektoren der Länge 2

undefined

    vector<int> first(&a[0],&a[sz/2]);
    vector<int> second(&a[(sz/2)+1],&a[sz-1]);

Stellen, wenn eine der Vektor {A, B, C, D}

    first:  {A,B}   0 -> 2 (where 2 is one past the end so index 0 and 1_
    second: {}      3 -> 3 (Since one past the end equals the start it is empty}

oder versuchen Sie einen größeren Vektor: {A, B, C, D, E, F, G, H, I}

    first:  {A, B, C, D}    0 -> 4 (4 is one past the end so index 0,1,2,3)
    second: {F, G, H}       5 -> 8 (8 is one past the end so index 5,6,7)

oder versuchen Sie einen kleineren Vektor: {A, B}

    first:  {A}    0 -> 1
    second: {BANG} 2 -> 1

Sollte sein:

    int* st = &a[0];
    // Using pointer arithmatic because it was too late at night
    // to work out if &a[sz] is actually legal or not.
    vector<int> first (st,      st+sz/2]); // sz/2 Is one past the end.
    vector<int> second(st+sz/2, st+sz   ); // First element is sz/2  
                                           // one past the end is sz

Die Vektoren in merge () übergeben. Der dst Parameter muss durch Referenz übergeben werden, wie es ein out-Parameter ist. Aber auch zur Kenntnis, dass die erste und die zweite Parameter ist const so können wir durch konstante Referenz übergeben (den Kopierschritt zu vermeiden).

void merge(vector<int>& dst,vector<int> const& first,vector<int> const& second)

Auch die Merge-Funktion:

drückt den Wert in dst. Aber dst ist bereits voll von den Daten, die in. So kamen, bevor wir die Zusammenführung des Ziel tun muß gelöscht werden.

    mergeSort(first);
    mergeSort(second);

    // Must clear a before we start pushing stuff into.
    a.clear();   // Add this line.
    merge(a,first,second);  

Answer 2

Wenn sz == 2, &a[(sz/2)+1] wird versuchen, die Adresse eines nehmen [2], mit dem Sie diesen Fehler geben wird.

Answer 3

Martin Recht ist, das Problem ist der contructor der auxiliar Vektoren:

Original-Vektor: 1 9 7 9 2 7 2 1 9 8

iter1: 2, iter2: 8

   vector<int> v( iter1, iter2 ); //new vector: 2 7 2 1 9

http://www.cppreference.com/wiki/stl/vector/vector_constructors

Und reden über merge-Art und andere Sortieralgorithmen, Ive eine sehr nützliche Web gefunden:

http://www.sorting-algorithms.com/merge-sort