Сортировка вектора слиянием с использованием итераторов

#c #vector #iterator #mergesort

#c #вектор #итератор #сортировка слиянием

Вопрос:

Для назначения класса мне требуется выполнить сортировку вектора слиянием с использованием его итераторов.

Я написал следующее, которое работает с векторами, но не использует итераторы:

 void MergeSort(IntVector amp;vec, int left, int right)
{
     if (left < right)
     { 
          int nMid = ((left   right) / 2);
          MergeSort(vec, left, nMid);
          MergeSort(vec, nMid   1, right);

          //merge(vec, left, nMid, right);
     }
}

Я попытался внести некоторые изменения для размещения итераторов, но это не позволяет мне выполнять такие операции, как < и на итераторах.

 void MergeSort(IntVectorIt left, IntVectorIt right)
{
     if (left < right)
     { 
          intVectorIt nMid = ((left   right) / 2);
          MergeSort(left, mid);
          MergeSort(mid   1, right);

          //merge(vec, left, nMid, right);
     }
}

Как я могу приспособить использование итераторов в моей сортировке слиянием?

К вашему сведению, это определения типов, которые я использую:

 typedef vector<int> IntVector;
typedef IntVector::iterator IntVectorIt;

1. Будьте осторожны при использовании итераторов, некоторые операции над вектором приведут к аннулированию итераторов и вызовут неопределенное поведение. Смотрите здесь: learningcppisfun.blogspot.com/2007/01 /…

2. к сожалению, профессор настаивает на том, чтобы в нашей сортировке слиянием использовалось слияние STL (algorithms.h), и это слияние работает только с векторами и итераторами.

3. как вы это представляете, я не вижу никаких проблем — вы не можете вставлять / удалять в / из вектора, потому что у вас есть доступ только к двум итераторам, но я просто подумал, что должен вас предупредить.

Ответ №1:

Вы хотите сравнить, совпадают ли итераторы (возможно только условие ошибки при нормальном вводе):

  if (left!=right)

Что касается ваших проблем с добавлением, вы думаете об этом неправильно. Семантически добавление left и right не имеет смысла, поскольку оно проходит мимо конца вашего массива, не говоря уже о том, что оно переполнится. Все, что вы хотите, это добавить половину расстояния между ними к left :

 IntVectorIt nMid=left (right-left)/2;

Ответ №2:

Вместо left<right вы должны использовать *left<*right .

1. но разве *left не будет приравниваться к значению в векторе, на которое указывает left? Я не хочу проверять значения, но я хочу проверить, находится ли левый итератор слева от правого итератора?

2. @xbonez: Ах, извините, я неправильно истолковал ваш вопрос. В этом случае left!=right было бы более уместно.