一些神奇的STL

wulibra · 2020-08-21 07:36:15 · 个人记录

next_permutation

全排列函数，将数组进行字典序排序

会改变原数组

可利用其生成全排列

如：

int a[4]={1,2,3,4};
    sort(a,a+4);
    do{
        for(int i=0;i<4;i++)        
        cout<<a[i]<<" ";
        cout<<endl;
    }while(next_permutation(a,a+4));

输出结果：

其对字符串也适用，此不举例，可去这里查看

还可输出第n个全排列，如：

    int a[7]={1,2,3,4,5,6,7};
    sort(a,a+7); 
    int n=0;
    do{
        if(n==1654){
            for(int i=0;i<7;i++)
              cout<<a[i];
            cout<<endl;
        break;
        }
        n++;
    }while(next_permutation(a,a+7));

就可以输出第1654个全排列

lower_bound or upper_bound

二分查找函数

lower是从前往后扫

upper是从后往前扫

使用见下

    int num[8]={1,2,4,7,7,7,15,34}; 
    sort(num,num+8);                           //按从小到大排序 
    int pos1=lower_bound(num,num+8,7)-num;    //返回数组中第一个大于或等于被查数的值 
    int pos2=upper_bound(num,num+8,7)-num;    //返回数组中第一个大于被查数的值
    cout<<pos1<<" "<<num[pos1]<<endl;
    cout<<pos2<<" "<<num[pos2]<<endl;
    sort(num,num+8，cmp);                      //按从大到小排序
    int pos3=lower_bound(num,num+8,7,greater<int>())-num;  //返回数组中第一个小于或等于被查数的值 
    int pos4=upper_bound(num,num+8,7,greater<int>())-num;  //返回数组中第一个小于被查数的值 
    cout<<pos3<<" "<<num[pos3]<<endl;
    cout<<pos4<<" "<<num[pos4]<<endl;

运行结果：