排序最速传说——sort

我们都学过一些排序的写法，比如冒泡排序，快速排序之类的东西，举个例子来说吧，这是快速排序的代码：

#include<iostream>
using namespace std;
int a[100001];
void quicksort(int l,int r)
{
  int i=l,j=r;
  int mid=a[(l+r)/2];
  do
  {
    while(a[i]<mid) i++;
    while(a[j]>mid) j--;
    if(i<=j)
    {
      swap(a[i],a[j]);
      i++;j--;
    }
  }while(i<=j);
  if(l<j) quicksort(l,j);
  if(r>i) quicksort(i,r);
}
int main()
{
  int arr=0;
  int n;
  cin>>n;
  for(int i=1;i<=n;++i)
    cin>>a[i];
  quicksort(1,n);
  for(int i=1;i<=n;++i)
    {
      arr++;
      if(arr==1) cout<<a[i];
      else cout<<" "<<a[i];
    }
  return 0;
}

而这个操作，sort只要一行

sort(a+1,a+1+n);

a是要排序的数组的名称，+1的意思是从下标为1的开始，+n+1的含义是从1到n。然后a数组中1-n的元素都被排序好了。
sort默认是从小到大排序，但是如果你想让他从大到小排序的话也可以，只需要这样做

int bool cmp(int a,int b)
{
	return a>b;
}
sort(a+1,a+n+1,cmp);

同理你也可以在cmp中进行其他的修改，让他可以对结构体进行排序。

“超级数组”map

map可以对两个元素形成映射关系，先来看他的定义、

map<int,int>mp;

map后面的尖括号里面的两个分别表示下标和存储数据的类型（如果当一个数组来用的话），也就是说，用这个当数组，甚至可以用字符串当下标，当然只有这一点是不足以让他成为超级数组的，正常情况下，开1e9的数组是肯定会爆的，但是，我们的map他没存储东西的数组是不占空间的，所以能完成下面的操作：

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
	map<int,int>mp;
	mp[1000100000]=114514;
	cout<<mp[1000100000]<<endl;
	return 0;
}

运行结果：

所以他才被成为超级数组。
但是这个东西有一个很大的缺陷就是在数据很多的时候跑的很慢，所以能用普通数组解决的问题不会用map。
最后提一嘴：unordered_map和map的区别的话，map里面是用hash映射，前者不会排序，所以在效率上要高于普通的map。

精简结构体——pair

pair这个东西我不常用，因为一般pair能干的结构体也可以做，但还是有必要了解一下的。
pair可以存放两个元素，使用的时候直接调用，调用下面再说
先来看一下定义

pair<int,int>p;

看到这个是不是有点眼熟？像极了map，pair的尖括号里面分别表示存放的两个数据的类型
调用的时候也是非常的方便

int p1=p.first;
int p2=p.second;

这样就可以分别调用p存放的两个数据了。
在定义pair的时候，如果觉得一直pair<int,int>太麻烦了，你可以用自带的一个函数，

make_pair(1,1);

我并不觉得很方便，我一般不用。