【C++实现有序子序列合并算法】-白红宇

C++实现简单的合并算法模板
复制内容到剪贴板
代码:

/**
 * project: merge template
 * author:billhoo
 * date: 2012年3月6日
 */
 #pragma once
 #ifndef _MERGE_H
 #define _MERGE_H

 #include<iterator>  //iterator_trais

 template<class Iterator, class Comp>
 void merge(Iterator beg, Iterator middle, Iterator end){ 
    
   typedef typename std::iterator_traits<Iterator>::value_type val_t;
   typedef typename std::iterator_traits<Iterator>::difference_type iterdiff_t;

   const iterdiff_t leftArrLength = std::distance(beg, middle);
   const iterdiff_t rightArrLength = std::distance(middle, end);
   val_t *leftArr = new val_t[leftArrLength];
   val_t *rightArr = new val_t[rightArrLength];

   //copy left and right subsequence into new array respectively
   std::copy(beg, middle, leftArr);
   std::copy(middle, end, rightArr);
   
   Iterator index = beg;
   iterdiff_t leftArrIdx = 0;
   iterdiff_t rightArrIdx = 0;

   //do merge
   while(leftArrLength > leftArrIdx && rightArrLength > rightArrIdx){ 
    
     if(Comp()(leftArr[leftArrIdx], rightArr[rightArrIdx]))
       *index++ = leftArr[leftArrIdx++];
     else
       *index++ = rightArr[rightArrIdx++];
   }// end of while

   if(leftArrIdx < leftArrLength)
     std::copy(leftArr + leftArrIdx, leftArr + leftArrLength, index);
   else
     std::copy(rightArr + rightArrIdx, rightArr + rightArrLength, index);

   delete [] leftArr;
   delete [] rightArr;
 }// end of merge

 #endif // _MERGE_H

 /**
 * author:billhoo
 * date: 2012年3月6日
 */
 #include<iostream>
 #include<list>

 #include"merge.h"  //merge
 #include"display_array.h"  //displayArr

 using std::cout;
 using std::endl;
 using std::list;

 int main(int argc, char **argv){ 
    
   int intArr[ ] = {1,2,5,8,9,0,3,4,5,7};
   int *intArrEnd = intArr + sizeof(intArr) / sizeof(*intArr);
   
   list<int> intList(intArr, intArrEnd);

   cout<<"ints array merge..."<<endl;
   displayArr<int*>(intArr, intArr + 10);
   merge<int*, std::less<int>>(intArr, intArr + 5, intArrEnd);
   displayArr<int*>(intArr, intArr + 10);

   list<int>::iterator middle = intList.begin();
   std::advance(middle, 5);
   cout<<"\nints list merge..."<<endl;
   displayArr(intList.begin(), intList.end());
   merge<list<int>::iterator, std::less<int>>(intList.begin(), middle, intList.end());
   displayArr(intList.begin(), intList.end());

   return EXIT_SUCCESS;
 }             本文转自Bill_Hoo 51CTO博客，原文链接：http://blog.51cto.com/billhoo/797754，如需转载请自行联系原作者