Мне нужно реализовать MergeSort для сортировки вектора целых чисел с использованием векторных итераторов.
Я реализовал это, но я получаю эту ошибку: векторный итератор не разыменовывается.
В качестве параметров для функции слияния я использую (A.begin (), A.end ()) где A — мой вектор, который содержит
n элементов.
#include <iostream>
#include <vector>
using namespace std;
void swap(vector<int>::iterator first,vector<int>::iterator last)
{
int temp;
temp=*first;
*first=*last;
*last=temp;
return;
}void mergesort(vector<int>::iterator first,vector<int>::iterator last)
{
if(first==last) return;
if(first+1==last)
{
if(*last>*first) swap(first,last);
return;
}
vector<int>::iterator middle;
middle=first+(last-first)/2;
mergesort(first,middle);
mergesort(middle+1,last);
int a,b,pa,pb;
vector<int> h;
//the number of elements in a
pa=middle-first+1;
//the number of elements in b
pb=last-middle;
h.resize(pa+pb);
a=0; b=0;
while(a<pa && b<pb)
if(*(first+a)<*(middle+1+b))
{
h[a+b]=*(first+a); a++;
}
else
{
h[a+b]=*(middle+1+b); b++;
}
while(a<pa)
{
h[a+b]=*(first+a); a++;
}
while(b<pb)
{
h[a+b]=*(middle+1+b); b++;
}
for(int i=0;i<((a+b)-1);i++)
*(first+i)=h[i];
return;
}int main(){
vector<int>A;
for(int i=1000;i>0;i--)
{
A.push_back(i);
//vector of integer: 1000,999,998 ... 3,2,1
}
mergesort(A.begin(),A.end());
//sort vector elements from smallest to biggest: 1,2,3...998,999,1000system("pause");
return 0;
}
Диапазоны итераторов должны быть выражены как итератор, ссылающийся на первый элемент, и итератор, ссылающийся на «один за другим». Если они равны, это пустой диапазон. Вы этого не делаете.
Чтобы это исправить, if(first+1==last)
пункт должен просто вернуться. Второй mergesort(middle+1,last)
звонок должен быть mergesort(middle,last)
, pa
должен просто равняться middle-last
, pb
рассчитывается правильно. И я думаю, что -1
в последнем цикле for следует удалить.
Иметь диапазон, определенный итератором для первого и итератором для последнего, — плохая идея.
Ты должен сделать
mergesort(A.begin(),A.end()-1);
На самом деле, end()
итератор указывает на элемент после конец вектора. Это не указывает на прошлой элемент вектора.