MergeSort。與迭代器

我需要實現歸併的算法如下界面實現：MergeSort。與迭代器

template <typename T, typename Comp> 
void mergesort(T begin, T end, Comp comp);

其中開始和年底 - 迭代器類型T的一些容器的元素，補償 - 是比較要素的功能，它們存儲在容器中。和

template <typename T, typename Comp> 
void merge(T beginLeft, T endLeft, T beginRight, T endRight, 
       T beginResult, Comp comp);

是兩個已排序的容器的合併的功能（beginLeft和endLeft - 迭代器的第一容器的，beginRight和endRight - 第二）和結果應當是迭代器開始新合併的容器beginResult。

應該看起來像this。

我已經寫了遞歸函數的歸併排序，這就要求合併的過程。

template <typename T, typename Comp> 
void mergesort(T begin, T end, Comp comp) 
{ 
    if (begin == std::prev(end)) 
    { 
     return; 
    }  

    T middle = begin + std::distance(begin, end)/2; 

    mergesort<T, Comp>(begin, middle, comp); 
    mergesort<T, Comp>(middle, end, comp); 

    merge<T, Comp>(begin, middle, middle, end, begin, comp); 
} 

template <typename T, typename Comp> 
void merge(T beginLeft, T endLeft, T beginRight, T endRight, 
       T beginResult, Comp comp) 
{ 
    while (beginLeft != endLeft && beginRight != endRight) 
    { 
     if (comp(*beginLeft, *beginRight)) 
     { 
      *beginResult = *beginLeft; 
      ++beginResult; 
      ++beginLeft; 
     } 
     else 
     { 
      *beginResult = *beginRight; 
      ++beginResult; 
      ++beginRight; 
     } 
    } 

    while (beginLeft != endLeft) 
    { 
     *beginResult = *beginLeft; 
     ++beginResult; 
     ++beginLeft; 
    } 
    while (beginRight != endRight) 
    { 
     *beginResult = *beginRight; 
     ++beginResult; 
     ++beginRight; 
    } 
}

功能合併正常工作，但我不太明白，怎麼歸併應該工作。我應該通過什麼參數

merge<T, Comp>(begin, middle, middle, end, /?...?/, comp);

如果我通過只是開始那裏，比排序的結果是不正確的。或者我應該通過那裏臨時容器。但是我怎麼能創建它，如果我只有迭代器的類型，並且不知道元素的類型？

我將是你的幫助表示感謝。謝謝！

--ADDED ---

合併的實施例：

vector<int> vec1; 
vector<int> vec2; 
vector<int> vec3(6); 
vec1.push_back(1); 
vec1.push_back(3); 
vec1.push_back(5); 
vec2.push_back(2); 
vec2.push_back(4); 
vec2.push_back(6); 
merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec3.begin(), std::less<int>()); 

for (int i = 0; i < vec3.size(); ++i) 
{ 
    std::cout << vec3[i] << std::endl; 
}

輸出爲：1 2 3 4 5 6

來源

2013-12-23 Ann Orlova

如何知道*合併*如果你甚至不知道如何調用它，它可以正常工作？ –

你需要的是就地合併排序。這是不容易實現，因爲此鏈接指出： http://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm –

可以肯定不能使用begin存儲結果。您仍在閱讀begin並進行合併，因此通過寫入它可能會覆蓋可能仍未讀取的數據。

您需要臨時存儲寫結果，然後再複製回了原來的。內存可以是任何類型的，只要你可以獲得一個迭代器。說一個std::vector。

雖然有一個基本問題。你有merge爲T所有五個迭代器的類型，但至少beginResult類型應該是一個可能不同的迭代器。否則，就像你所觀察到的那樣，你無法知道要使用哪個臨時容器。

如您所鏈接的那樣，std::merge的模板對迭代器left，right和result有不同的迭代器類型。

注：分配臨時內存，你需要知道的元素類型T是一個迭代器。這只是由T::value_type完成。請參閱here。

來源

2013-12-23 10:34:07 Shahbaz

沒有，甚至近，解決實際問題。 –

像這樣的東西應該工作：

template<class BiDirIt, class Compare = std::less<typename std::iterator_traits<BiDirIt>::value_type>> 
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare()) 
{ 
     auto const N = std::distance(first, last); 
     if (N < 2) return; 
     auto middle = first + N/2; 
     merge_sort(first, middle, cmp); 
     merge_sort(middle, last, cmp); 
     std::inplace_merge(first, middle, last, cmp); 
}

來源

2013-12-26 13:54:20 TemplateRex

您可以創建矢量這樣：

std::vector<std::iterator_traits<T>::value_type> result;

在一個輔助函數，然後打電話給你的排序過程：

merge_sort(first, last, result.begin());

然後，一旦您的函數返回結果，您可以將結果複製到由用戶提供的iter表示的向量中ators。

來源

2015-04-27 07:18:07

MergeSort。與迭代器

回答

相關問題