Почему при сортировке слиянием я получаю векторный индекс вне допустимого диапазона? - PullRequest
Новая
       5

Почему при сортировке слиянием я получаю векторный индекс вне допустимого диапазона?

0 голосов
/ 25 августа 2010 
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);
}

Может кто-нибудь помочь мне в чем проблема с этим кодом?Я получаю векторную ошибку вне диапазона.

Ответы [ 3 ]

3 голосов
/ 25 августа 2010

Если sz == 2, &a[(sz/2)+1] попытается взять адрес [2], что даст вам эту ошибку.

2 голосов
/ 25 августа 2010

Ваши субвекторы заданы неверно.
Помните, что итераторы задают начало до конца после конца.

Так что при этом будет пропущен средний элемент и последний элемент в векторе.
Итакже не определено для действительно коротких векторов длины 2 

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

Представьте себе, если a является вектором {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}

Или попробуйте больший вектор: {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)

Или попробуйте меньший вектор: {A, B} 

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

Должно быть:

    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

Векторы переданы в слияние ().Параметр dst должен передаваться по ссылке, поскольку он является выходным параметром.Но также обратите внимание, что первый и второй параметры являются константными, поэтому мы можем передавать по константной ссылке (чтобы избежать шага копирования). 

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

Также функция слияния:

Вставляет значение вДСТ.Но dst уже заполнен данными, которые поступили. Поэтому, прежде чем мы сделаем слияние, пункт назначения должен быть очищен. 

    mergeSort(first);
    mergeSort(second);

    // Must clear a before we start pushing stuff into.
    a.clear();   // Add this line.
    merge(a,first,second);
0 голосов
/ 25 августа 2010

Мартин прав, проблема в том, что конструктор вспомогательных векторов:

Исходный вектор: 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

И, говоря о сортировке слиянием и других алгоритмах сортировки, я нашел очень полезную сеть:

http://www.sorting -algorithms.com / слияния-сортировки

...