前100大的元素

//清理硬盘,备份一下以前的程序
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
#include <iterator>
#include <algorithm>
#include <stdlib.h>
using namespace std;
const char* filename="testm.txt";


typedef istream_iterator<int> istream_itr;
typedef ostream_iterator<int> ostream_itr;
typedef back_insert_iterator< vector<int> > back_ins_itr;

template<typename T>
T lexical_cast(const string& arg)
{
  stringstream ss(arg);
  T ret;
  ss >> ret;

  return ret;
}
const unsigned gen_number=1000;
const unsigned max_number=10;

int main(int argc, char *argv[])
{
   
    ofstream output(filename);
    for(int i=0;i!=gen_number;++i)output<<rand()<<'\n';   
    output.close();
   
    ifstream input(filename);

    //使用stl的nth_element求前100大的元素
    //缺点:需要全部加载入内存,空间复杂度为O(n)
vector<int> num;
    copy(istream_itr(input), istream_itr(), back_ins_itr(num));
    nth_element(num.begin(),num.begin()+max_number,num.end(),greater<int>());
    copy(num.begin(), num.begin()+max_number, ostream_itr(cout, "\n"));  

    cout<<"------------------------\n";

    //堆算法
    input.clear();
    input.seekg(0);
    const int max_number_1=max_number+1;
    int num_stack[max_number_1];
    string temp;
   
    for(int i=0;i<max_number_1;++i){
        input>>temp;
        num_stack[i]=lexical_cast<int>(temp);
    };
    make_heap(num_stack,num_stack+max_number_1,greater<int>());
   
    while(input>>temp){
        int t=lexical_cast<int>(temp);
        if(num_stack[0]<t){
            pop_heap(num_stack,num_stack+max_number_1,greater<int>());   
            num_stack[max_number]=t;
            push_heap(num_stack,num_stack+max_number_1,greater<int>());
   
        }
    }
   
    copy(
         num_stack,
         num_stack+max_number_1,
         ostream_itr(cout, "\n")
    );            
    input.close();
    
    system("PAUSE");
    return 0;
}