/**
* 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;
* 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，如需转载请自行联系原作者
