//多路归并的外排序 //思路如下://1.按各输入文件中下一个读到的元素的大小构造一个输入流最小堆.//2.从堆顶文件里读一个元素并写入输出文件. //3.同时按读的那个文件的下一个元素的值调整堆.//4.若第3步已到达文件结尾.则从堆中删除该输入流//5 如果堆中还有元素. 回到第2步#include<iostream>#include<fstream>#include<vector>#include<algorithm>#include<iterator>#include<functional>using namespace std;
//这个类主要用来管理一个输入流.//它知道流中还有没有元素.//可以查看下一个将读出来的元素的值.//可以读出一个元素.template <class T>class Yudu {private:istream & _istream;T _next;bool _have_next;public:Yudu( istream & x) : _istream(x) {if (_istream >> _next) _have_next = true;else _have_next = false; }inline bool have_next() { return _have_next; }//读出流中下一个元素T read_next() { if (! _have_next) {cout << "读取错误! 退出" << endl;exit(1);}T temp = _next;if (_istream >> _next) _have_next = true;else _have_next = false;return temp;}//看看下一个元素但不读出来inline const T& look_next() const { return _next; } };
//比较两个Yudu对象下一个元素的大小//提供给paixu函数中的堆操作时使用class bijiao {public:template <typename T>bool operator() (const Yudu<T>* a, const Yudu<T>* b) {return a->look_next() > b->look_next() ;}};
//文件排序函数template <typename T>void paixu(vector<Yudu<T>* >& v , ostream& out){//先删除数组中的"没有下一个元素"的Yudu对象.例如一个空的文件构造的Yudu对象.v.erase( remove_if(v.begin(),v.end(), not1(mem_fun(& Yudu<T>::have_next))), v.end() );
make_heap(v.begin(), v.end(), bijiao());
while (! v.empty() ){pop_heap(v.begin(),v.end(), bijiao());out << v.back()->read_next() << " "; // out 以文本方式打开. 如果是其它方式这里要改.if (! v.back()->have_next() ) v.pop_back();else push_heap(v.begin(), v.end(), bijiao());}}
int main() {ifstream in[3];in[0].open("1.txt");in[1].open("2.txt");in[2].open("3.txt");
vector<Yudu<int>* > v;v.push_back(new Yudu<int>(in[0])); //实际使用时要释放new出的对象.或者用boost的智能指针.v.push_back(new Yudu<int>(in[1]));v.push_back(new Yudu<int>(in[2]));
ofstream o("out.txt");
paixu(v, o);
cin.get();return 0;}
/*测试(三个文件中是已经有序的数)1.txt: 1 5 9 12 212.txt: 3 4 5 7 83.txt: 2 3 5 10 11 14 19 25 27
执行归并后out.txt: 1 2 3 3 4 5 5 5 7 8 9 10 11 12 14 19 21 25 27 */
