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。与迭代器

回答

相关问题