Perché ricevo vettore Indice fuori l'errore gamma nel merge sort?
Domanda
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);
}
Qualcuno può aiutarmi qual è il problema con questo codice? Io sono sempre vettore pedice outof errore di campo.
Soluzione
I tuoi sub vettori sono specificati in modo non corretto.
Ricordate gli iteratori specificare l'inizio ad una oltre la fine.
Quindi questa volontà manca l'elemento centrale e l'ultimo elemento nel vettore.
Ed è anche undefined per davvero brevi vettori di lunghezza 2
vector<int> first(&a[0],&a[sz/2]);
vector<int> second(&a[(sz/2)+1],&a[sz-1]);
Immaginate se a è il vettore {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}
o provare un vettore più grande: {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)
o provare un vettore più piccolo: {A, B}
first: {A} 0 -> 1
second: {BANG} 2 -> 1
Dovrebbe essere:
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
I vettori passò nelle merge (). Il parametro dst deve essere passato per riferimento in quanto è un parametro out. Ma anche nota che il primo e secondo parametri sono const in modo da poter passare da riferimento const (per evitare il passaggio di copia).
void merge(vector<int>& dst,vector<int> const& first,vector<int> const& second)
Anche la funzione di fusione:
sta spingendo il valore in dst. Ma ora legale è già pieno dai dati che è venuto. Quindi prima di fare l'unione la destinazione deve essere cancellata.
mergeSort(first);
mergeSort(second);
// Must clear a before we start pushing stuff into.
a.clear(); // Add this line.
merge(a,first,second);
Altri suggerimenti
Se sz == 2, &a[(sz/2)+1]
cercherà di prendere l'indirizzo di un [2], che vi darà questo errore.
Martin è giusto, il problema è la contructor dei vettori Auxiliar:
vettore originale: 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
E parlando di merge-ordinamento e di altri algoritmi di ordinamento, Ive ha trovato un utilissimo web: