时间戳

首页 > 解决方案 > 合并函数未正确复制到向量中

c++ - 合并函数未正确复制到向量中

问题描述

应该接受 5 个迭代器，拆分发送的merge(iterator, iterator, iterator2, iterator2, outIterator)向量，然后对 2 个单独的向量进行排序，然后将它们合并为一个排序的向量。我的方法似乎有效，除非range2元素少于range1我的测试失败。

template<typename Iter1, typename Iter2, typename OIter>
OIter merge(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2, OIter out) {
   // TODO
   auto i = first1;
   auto j = first2;
   while (j != last2 && i != last1) {
       if (first2 == last2) {
           return std::copy(first1, last1, out);
       }
       if (*i < *j) {
           *out++ = *i++;  
       } else {
           *out++ = *j++;
       }
   }
   //only one of the ranges has elements copy them over
   if (first2 == last2) {
       return std::copy(first1, last1, out);
   } else {
       return std::copy(first2, last2, out);
   }
}

测试：

REQUIRE( out == copy_out )

扩展：

{ 0, 1, 2, 3, 0, 1, 2, 3, 0, 0, 0, 0, 0, 0 } = actual

==

{ 0, 1, 2, 3, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 } = expected

标签： c++vectormergeiteratormergesort

解决方案

这个逻辑是错误的

//only one of the ranges has elements copy them over
if(first2 == last2)
{
  return std::copy(first1, last1, out);
}else{
  return std::copy(first2, last2, out);
}

它应该是

//only one of the ranges has elements left, copy them over
if(j == last2)
{
  return std::copy(i, last1, out);
}else{
  return std::copy(j, last2, out);
}

还有这种特殊待遇

if(first2 == last2)
{
  return std::copy(first1, last1, out);
}

是不必要的（并且放错了位置）。

推荐阅读