C++标准模板库函数sort的那些事儿

STL里面有个sort函数，可以直接对数组排序，复杂度为n*log2(n)。sort()定义在在头文件<algorithm>中。sort函数是标准模板库的函数，已知开始和结束的地址即可进行排序，可以用于比较任何容器（必须满足随机迭代器），任何元素，任何条件，执行速度一般比qsort要快。另外，sort()是类属函数，可以用于比较任何容器，任何元素，任何条件。

具体事例如下：
char ch[20]="sdasdacsdasdas";
cout<<ch<<endl;
sort(ch,ch+14);
cout<<ch<<endl;
注意：缺省是升序排序。sort中一个改变排序顺序的例子如下（降序）：

#include<iostream>
#include<algorithm>
using namespace std;
bool cmp (const int a, const int b)
{
    return a > b;
}
int main()
{
    int data[5];
    for(int i = 0; i < 5; i++)
        cin >> data[i];
    sort(data, data + 5, cmp);
    return 0;
}
这个函数可以传两个参数或三个参数。第一个参数是要排序的区间首地址，第二个参数是区间尾地址的下一地址。也就是说，排序的区间是[a,b)。简单来说，有一个数组int a[100]，要对从a[0]到a[99]的元素进行排序，只要写sort(a,a+100)就行了，默认的排序方式是升序。如需要对数组t的第0到len-1的元素排序，就写sort(t,t+len);对向量v排序也差不多，sort(v.begin(),v.end());排序的数据类型不局限于整数，只要是定义了小于运算的类型都可以，比如字符串类string。

如果是没有定义小于运算的数据类型，或者想改变排序的顺序，就要用到第三参数——比较函数。比较函数是一个自己定义的函数，返回值是bool型，它规定了什么样的关系才是“小于”。想把刚才的整数数组按降序排列，可以先定义一个比较函数cmp:

bool cmp(int a,int b)
{
    return a>b;
}排序的时候就写sort(a,a+100,cmp);

假设自己定义了一个结构体node:

struct node{
    int a;
    int b;
    double c;
};
有一个node类型的数组node arr[100]，想对它进行排序：先按a值升序排列，如果a值相同，再按b值降序排列，如果b还相同，就按c降序排列。就可以写这样一个比较函数：

以下是代码片段：
bool cmp(node x,node y)
{
     if(x.a!=y.a)  return x.a
     if(x.b!=y.b)  return x.b>y.b;
     return  return x.c>y.c;
}
排序时写sort(arr,a+100,cmp);
最后看一个完整的实例，一道题目“文件名排序 ”。

以下是代码片段：


代码如下:

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
//定义一个结构体来表示文件，a代表文件名，b代表文件类型（要么"File"要么"Dir"）
struct node{
   string a,b;
};
//ASCII码中，所有大写字母排在所有小写字母前面，'A'<'Z'<'a'<'z'
//而这题要求忽略大小写，所以不能直接用字符串的比较。自定义了一个lt函数，就是less than的意思
//先把两个字符串全部转化为小写，再比较大小（字典序）
bool lt(string x,string y)
{
   int i;
   for(i=0;i<x.length();i++)
      if(x[i]>='A'&&x[i]<='Z')
         x[i]='a'+(x[i]-'A');
   for(i=0;i<y.length();i++)
      if(y[i]>='A'&&y[i]<='Z')
         y[i]='a'+(y[i]-'A');
   return x<y;
}
//自定义的比较函数，先按b值升序排列（也就是"Dir"排在"File"前面）
//如果b值相同，再按a升序排列，用的是刚才定义的lt函数
bool comp(node x,node y)
{
   if(x.b!=y.b) return x.b<y.b;
   return lt(x.a,y.a);
}
int main()
{
   node arr[10001];
   int size=0;
   while(cin>>arr[size].a>>arr[size].b)
      size++;
   sort(arr,arr+size,comp);
   for(int i=0;i<size;i++)
      cout<<arr[i].a<<" "<<arr[i].b<<endl;
   return 0;
}

赞 (0)

相关推荐

  • C++关键字typename的深入理解

    问题:在下面的 template declarations(模板声明)中 class 和 typename 有什么不同? 复制代码 代码如下: template<class T> class Widget; // uses "class"template<typename T> class Widget; // uses "typename" 答案:没什么不同.在声明一个 template type parameter(模板类型参数)的时候,

  • 浅析C++中模板的那点事

    浅析C++中模板的那点事

    1.什么是模板 假设现在我们完成这样的函数,给定两个数x和y求式子x^2 + y^2 + x * y的值 .考虑到x和y可能是 int , float 或者double类型,那么我们就要完成三个函数: int fun(int x,int y);float fun(float x,float y);double fun(double x,double y); 并且每个fun函数内部所要完成的操作也是极其的相似.如下: 复制代码 代码如下: int fun(int x,int y){    int

  • C++中的类模板详解及示例

    C++中的类模板详解及示例

    C++中的函数模板 对于类的声明来说,也有同样的问题.有时,有两个或多个类,其功能是相同的,仅仅是数据类型不同,如下面语句声明了一个类: 复制代码 代码如下: class Compare_int{ public:  Compare(int a,int b)  {   x=a;   y=b;  }   int max()  {   return (x>y)?x:y;  }  int min()  {   return (x<y)?x:y;  } private:  int x,y;}; 其作用是

  • C++中函数模板的用法详细解析

    定义 我们知道函数的重载可以实现一个函数名多用,将功能相同或者类似函数用同一个名来定义.这样可以简化函数的调用形式,但是程序中,仍然需要分别定义每一个函数. C++提供的函数模板可以更加简化这个过程. 所谓函数模板实际上是建立一个通用函数,其涵涵素类型额形参类型不具体指定,用一个虚拟的类型来代表,这个通用函数就称为函数模板. 凡是函数体相同的函数都可以用这个模板来代替,不必定义多个函数,只需要在模板中定义一次即可.在调用函数时,系统会根据实参的类型来取代模板中的虚拟类型,从而实现了不同函数的功能

  • C++模板特例化应用实例

    模板特例化是C++程序设计中一个非常重要的应用,本文就以实例形式对其进行分析,相信对大家进一步理解C++程序设计能够带来一定的帮助.具体内容如下: 首先,模板是C++中一个很重要的特性,写一份代码能用于多种数据类型(包括用户自定义类型).例如,STL的sort()函数可以用于多种数据类型的排序,类stack可以用作多种数据类型的栈.但是,如果我们想对特定的数据类型执行不同的代码(而不是通用模板)呢?这种情况下就可以使用模板特例化(template specialization). 一.函数模板特

  • C++大数模板(推荐)

    分别使用C++中的运算符重载的方法来实现大数之间的数学运算,包括加法.减法.乘法.除法.n次方.取模.大小比较.赋值以及输入流.输出流的重载..并且使用这个大数模板,顺利AC了HDOJ上的1134这个题目的Catalan数计数问题..http://acm.hdu.edu.cn/showproblem.php?pid=1134大数模板的代码如下: 复制代码 代码如下: #include<iostream> #include<string> #include<iomanip>

  • C++可变参数的函数与模板实例分析

    本文实例展示了C++可变参数的函数与模板的实现方法,有助于大家更好的理解可变参数的函数与模板的应用,具体内容如下: 首先,所谓可变参数指的是函数的参数个数可变,参数类型不定的函数.为了编写能处理不同数量实参的函数,C++提供了两种主要的方法:如果所有的实参类型相同,可以传递一个名为initializer_list的标准库类型:如果实参的类型不同,我们可以编写可变参数模板.另外,C++还有一种特殊的省略符形参,可以用它传递可变数量的实参,不过这种一般只用于与C函数交互的接口程序. 一.可变参数函数

  • C++模板之特化与偏特化详解

    前言 说到C++模板,这个已经不是什么新东西了,自己在实际开发中也用过:对于C++模板特化和偏特化,对于别人来说,已经不是什么新东西了,但是对于我来说,的确是我的盲区,那天在群里讨论这个问题,自己对于这部分确实没有掌握,又联想到在<STL源码剖析>一书中,对于此也是有着介绍.所以,今天就对此进行详细的总结,以备后忘. C++模板 说到C++模板特化与偏特化,就不得不简要的先说说C++中的模板.我们都知道,强类型的程序设计迫使我们为逻辑结构相同而具体数据类型不同的对象编写模式一致的代码,而无法抽

  • C++的template模板中class与typename关键字的区别分析

    在C++模板中,可以使用class或者typename来声明模板参数,那么这两个关键字有什么区别呢? 模板参数声明 对于模板参数声明,这两个参数没有区别,含义是一样的. template class Simple; template class Simple; 上面两行都是声明一个模板类Simple. 表明类型 假如我们有这样一段代码: template void add(const T &acontainer, T &sum) { T::const_iterator iter = con

  • 详解C++的模板中typename关键字的用法

    typename的使用场合 用处1, 用在模板定义里, 标明其后的模板参数是类型参数. 例如 template<typename T, typename Y> T foo(const T& t, const Y& y){//....}; templace<typename T> class CTest { private: T t; public: //... } 其实,这里最常用的是使用关键字class,而且二者功能完全相同,这里的class和定义类时的class

  • C++类模板与模板类深入详解

    1.在c++的Template中很多地方都用到了typename与class这两个关键字,而且有时候二者可以替换,那么是不是这两个关键字完全一样呢? 事实上class用于定义类,在模板引入c++后,最初定义模板的方法为:template<class T>,这里class关键字表明T是一个类型,后来为了避免class在这两个地方的使用可能给人带来混淆,所以引入了typename这个关键字,它的作用同class一样表明后面的符号为一个类型,这样在定义模板的时候就可以使用下面的方式了:      t

  • C++函数模板与类模板实例解析

    本文针对C++函数模板与类模板进行了较为详尽的实例解析,有助于帮助读者加深对C++函数模板与类模板的理解.具体内容如下: 泛型编程(Generic Programming)是一种编程范式,通过将类型参数化来实现在同一份代码上操作多种数据类型,泛型是一般化并可重复使用的意思.泛型编程最初诞生于C++中,目的是为了实现C++的STL(标准模板库). 模板(template)是泛型编程的基础,一个模板就是一个创建类或函数的蓝图或公式.例如,当使用一个vector这样的泛型类型或者find这样的泛型函数

  • c++中typename和class的区别介绍

    相信学习C++的人对class这个关键字都非常明白,class用于定义类.在模板引入c++后,最初定义模板的方法为: template<class T>...... 在这里class关键字表明T是一个类型,后来为了避免class在这两个地方的使用可能给人带来混淆,所以引入了typename这个关键字.它的作用同class一样表明后面的符号为一个类型,这样在定义模板的时候就可以使用下面的方式了: template<typename T>...... 在模板定义语法中关键字class与

  • 深入分析:C++模板究竟会使代码膨胀吗

    今天和同事说到C++模板会使代码膨胀, 可同事觉得不会.同事的依据是: 如果模板会使代码膨胀, 那么ATL和WTL里为什么还要大量使用模板? 同样功能 ,ATL和WTL编译出的可执行文件可比MFC编译的要小的多.我当时一愣 ,事实确实如同事所说,难道模板会使代码膨胀的观点是错误的吗? MFC因为本身代码量和复杂性在那里, 所以它生成比较大的exe无可厚非.我们这里重点关注为什么ATL/WTL使用模板,但是却不会使生成的exe变大. 我们知道使用模板时, 同一模板生成不同的模板实类后会是多份代码

随机推荐