P3384 【模板】重链剖分/树链剖分
题目描述
如题，已知一棵包含 $N$ 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：
1 x y z，表示将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$。2 x y，表示求树从 $x$ 到 $y$ 结点最短路径上所有节点的值之和。3 x z，表示将以 $x$ 为根节点的子树内所有节点值都加上 $z$。4 x，表示求以 $x$ 为根节点的子树内所有节点值之和。
输入格式
第一行包含 $4$ 个正整数 $N,M,R,P$，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。
接下来一行包含 $N$ 个非负整数，分别依次表示各个节点上初始的数值。
接下来 $N-1$ 行每行包含两个整数 $x,y$，表示点 $x$ 和点 $y$ 之间连有一条边（保证无环且连通）。
接下来 $M$ 行每行包含若干个正整数，每行表示一个操作。
输出格式
输出包含若干行，分别依次表示每个操作 $2$ 或操作 $4$ 所得的结果（对 $P$ 取模）。
输入输出样例 #1
输入 #1
5 5 2 24
7 3 7 8 0
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3输出 #1
2
21说明/提示
【数据规模】
对于 $30\%$ 的数据： $1 \leq N \leq 10$，$1 \leq M \leq 10$；
对于 $70\%$ 的数据： $1 \leq N \leq {10}^3$，$1 \leq M \leq {10}^3$；
对于 $100\%$ 的数据： $1\le N \leq {10}^5$，$1\le M \leq {10}^5$，$1\le R\le N$，$1\le P \le 2^{30}$。所有输入的数均在 int 范围内。
【样例说明】
树的结构如下：
各个操作如下：
故输出应依次为 $2$ 和 $21$。
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#define Rint register int
#define mem(a,b) memset(a,(b),sizeof(a))
#define Temp template<typename T>
using namespace std;
typedef long long LL;
Temp inline void read(T &x){
x=0;T w=1,ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
x=x*w;
}
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define len (r-l+1)
const int maxn=200000+10;
int n,m,r,mod;
//见题意
int e,beg[maxn],nex[maxn],to[maxn],w[maxn],wt[maxn];
//链式前向星数组，w[]、wt[]初始点权数组
int a[maxn<<2],laz[maxn<<2];
//线段树数组、lazy操作
int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn];
//son[]重儿子编号,id[]新编号,fa[]父亲节点,cnt dfs_clock/dfs序,dep[]深度,siz[]子树大小,top[]当前链顶端节点
int res=0;
//查询答案
inline void add(int x,int y){//链式前向星加边
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
}
//-------------------------------------- 以下为线段树
inline void pushdown(int rt,int lenn){
laz[rt<<1]+=laz[rt];
laz[rt<<1|1]+=laz[rt];
a[rt<<1]+=laz[rt]*(lenn-(lenn>>1));
a[rt<<1|1]+=laz[rt]*(lenn>>1);
a[rt<<1]%=mod;
a[rt<<1|1]%=mod;
laz[rt]=0;
}
inline void build(int rt,int l,int r){
if(l==r){
a[rt]=wt[l];
if(a[rt]>mod)a[rt]%=mod;
return;
}
build(lson);
build(rson);
a[rt]=(a[rt<<1]+a[rt<<1|1])%mod;
}
inline void query(int rt,int l,int r,int L,int R){
if(L<=l&&r<=R){res+=a[rt];res%=mod;return;}
else{
if(laz[rt])pushdown(rt,len);
if(L<=mid)query(lson,L,R);
if(R>mid)query(rson,L,R);
}
}
inline void update(int rt,int l,int r,int L,int R,int k){
if(L<=l&&r<=R){
laz[rt]+=k;
a[rt]+=k*len;
}
else{
if(laz[rt])pushdown(rt,len);
if(L<=mid)update(lson,L,R,k);
if(R>mid)update(rson,L,R,k);
a[rt]=(a[rt<<1]+a[rt<<1|1])%mod;
}
}
//---------------------------------以上为线段树
inline int qRange(int x,int y){
int ans=0;
while(top[x]!=top[y]){//当两个点不在同一条链上
if(dep[top[x]]<dep[top[y]])swap(x,y);//把x点改为所在链顶端的深度更深的那个点
res=0;
query(1,1,n,id[top[x]],id[x]);//ans加上x点到x所在链顶端 这一段区间的点权和
ans+=res;
ans%=mod;//按题意取模
x=fa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点
}
//直到两个点处于一条链上
if(dep[x]>dep[y])swap(x,y);//把x点深度更深的那个点
res=0;
query(1,1,n,id[x],id[y]);//这时再加上此时两个点的区间和即可
ans+=res;
return ans%mod;
}
inline void updRange(int x,int y,int k){//同上
k%=mod;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,1,n,id[top[x]],id[x],k);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
update(1,1,n,id[x],id[y],k);
}
inline int qSon(int x){
res=0;
query(1,1,n,id[x],id[x]+siz[x]-1);//子树区间右端点为id[x]+siz[x]-1
return res;
}
inline void updSon(int x,int k){//同上
update(1,1,n,id[x],id[x]+siz[x]-1,k);
}
inline void dfs1(int x,int f,int deep){//x当前节点，f父亲，deep深度
dep[x]=deep;//标记每个点的深度
fa[x]=f;//标记每个点的父亲
siz[x]=1;//标记每个非叶子节点的子树大小
int maxson=-1;//记录重儿子的儿子数
for(Rint i=beg[x];i;i=nex[i]){
int y=to[i];
if(y==f)continue;//若为父亲则continue
dfs1(y,x,deep+1);//dfs其儿子
siz[x]+=siz[y];//把它的儿子数加到它身上
if(siz[y]>maxson)son[x]=y,maxson=siz[y];//标记每个非叶子节点的重儿子编号
}
}
inline void dfs2(int x,int topf){//x当前节点，topf当前链的最顶端的节点
id[x]=++cnt;//标记每个点的新编号
wt[cnt]=w[x];//把每个点的初始值赋到新编号上来
top[x]=topf;//这个点所在链的顶端
if(!son[x])return;//如果没有儿子则返回
dfs2(son[x],topf);//按先处理重儿子，再处理轻儿子的顺序递归处理
for(Rint i=beg[x];i;i=nex[i]){
int y=to[i];
if(y==fa[x]||y==son[x])continue;
dfs2(y,y);//对于每一个轻儿子都有一条从它自己开始的链
}
}
int main(){
read(n);read(m);read(r);read(mod);
for(Rint i=1;i<=n;i++)read(w[i]);
for(Rint i=1;i<n;i++){
int a,b;
read(a);read(b);
add(a,b);add(b,a);
}
dfs1(r,0,1);
dfs2(r,r);
build(1,1,n);
while(m--){
int k,x,y,z;
read(k);
if(k==1){
read(x);read(y);read(z);
updRange(x,y,z);
}
else if(k==2){
read(x);read(y);
printf("%d\n",qRange(x,y));
}
else if(k==3){
read(x);read(y);
updSon(x,y);
}
else{
read(x);
printf("%d\n",qSon(x));
}
}
}P10814 【模板】离线二维数点
题目背景
青蛙。
题目描述
给你一个长为 $n$ 的序列 $a$，有 $m$ 次询问，每次询问给定 $l,r,x$，求 $[l,r]$ 区间中小于等于 $x$ 的元素个数。
输入格式
第一行两个数 $n,m$。
第二行 $n$ 个数表示序列 $a$。
之后 $m$ 行，每行三个数 $l,r,x$ 表示一次询问。
输出格式
对每个询问，输出一行一个数表示答案。
输入输出样例 #1
输入 #1
6 4
1 1 4 5 1 4
1 6 3
1 6 4
1 1 4
1 5 4输出 #1
3
5
1
4说明/提示
对于 $20\%$ 的数据，满足 $1\le n,m,a_i,l,r,x\le 100$。
对于 $40\%$ 的数据，满足 $1\le n,m,a_i,l,r,x\le 10^4$。
对于 $60\%$ 的数据，满足 $1\le n,m,a_i,l,r,x\le 10^5$。
对于 $80\%$ 的数据，满足 $1\le n,m,a_i,l,r,x\le 10^6$。
对于 $100\%$ 的数据，满足 $1\le n,m,a_i,l,r,x\le 2\times10^6$。
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,id,val;
};
int lowbit(int i){
return i&(-i);
}
int f[2000005];
void add(int x){
for(int i=x;i<=2000000;i+=lowbit(i))f[i]++;
}
int ask(int x){
int ans=0;
for(int i=x;i>=1;i-=lowbit(i))ans+=f[i];
return ans;
}
vector<node>vec[2000005];
int ans[2000005],n,m,a[2000006];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++){
int l,r,x;
cin>>l>>r>>x;
vec[l-1].push_back({x,i,-1});
vec[r].push_back({x,i,1});
}
for(int i=1;i<=n;i++){
add(a[i]);
for(int j=0;j<vec[i].size();j++){
ans[vec[i][j].id]+=vec[i][j].val*ask(vec[i][j].x);
}
}
for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
return 0;
}P5367 【模板】康托展开
题目描述
求 $1\sim N$ 的一个给定全排列在所有 $1\sim N$ 全排列中的排名。结果对 $998244353$ 取模。
输入格式
第一行一个正整数 $N$。
第二行 $N$ 个正整数，表示 $1\sim N$ 的一种全排列。
输出格式
一行一个非负整数，表示答案对 $998244353$ 取模的值。
输入输出样例 #1
输入 #1
3
2 1 3输出 #1
3输入输出样例 #2
输入 #2
4
1 2 4 3输出 #2
2说明/提示
对于 $10\%$ 数据，$1\le N\le 10$。
对于 $50\%$ 数据，$1\le N\le 5000$。
对于 $100\%$ 数据，$1\le N\le 1000000$。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000005;//上界
const int Mod=998244353；//神圣的模数
typedef long long ll;//加上这个很有用的，可以避免过多的重复long long
int n;
ll jc[maxn];//阶乘
ll tree[maxn];//树状数组
ll lowbit(ll x){return x&(-x);}//树状数组实现的支撑-取最低位,不知道的请翻到最后
ll sum(ll x)//求和
{
ll ans=0;
while(x!=0)
{
ans+=tree[x]%Mod;
x-=lowbit(x);
}
return ans%Mod;
}
void add(ll x,ll k)//加法
{
while(x<=n)
{
tree[x]+=k;
x+=lowbit(x);
}
}
int main()
{
scanf("%d",&n);
jc[0]=1;
for(int i=1;i<=n;i++)//预处理阶乘
{
jc[i]=jc[i-1]*i%Mod;
jc[i]%=Mod;
}
for(int i=1;i<=n;i++)
{
add(i,1);//如前面所说的那样，每一位都加上1
}
ll ans=1;//求排名，所以位置的值为1
for(int i=1;i<=n;i++)
{
ll a;
scanf("%lld",&a);//读入
ans+=((sum(a)-1)*jc[n-i]%Mod)%Mod;//取模运算分进去，不知道的往后看
add(a,-1);//这一个位置的值出现了，就把他减掉
}
printf("%lld\n",ans%Mod)；
return 0;
}P3369 【模板】普通平衡树
题目描述
您需要动态地维护一个可重集合 $M$，并且提供以下操作：
- 向 $M$ 中插入一个数 $x$。
- 从 $M$ 中删除一个数 $x$（若有多个相同的数，应只删除一个）。
- 查询 $M$ 中有多少个数比 $x$ 小，并且将得到的答案加一。
- 查询如果将 $M$ 从小到大排列后，排名位于第 $x$ 位的数。
- 查询 $M$ 中 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。
- 查询 $M$ 中 $x$ 的后继（后继定义为大于 $x$，且最小的数）。
对于操作 3,5,6，不保证当前可重集中存在数 $x$。
输入格式
第一行为 $n$，表示操作的个数,下面 $n$ 行每行有两个数 $\text{opt}$ 和 $x$，$\text{opt}$ 表示操作的序号（$ 1 \leq \text{opt} \leq 6 $）
输出格式
对于操作 $3,4,5,6$ 每行输出一个数，表示对应答案。
输入输出样例 #1
输入 #1
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598输出 #1
106465
84185
492737说明/提示
【数据范围】
对于 $100\%$ 的数据，$1\le n \le 10^5$，$|x| \le 10^7$
来源：Tyvj1728 原名：普通平衡树
在此鸣谢
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
typedef long long LL;
using namespace std;
int RD(){
int out = 0,flag = 1;char c = getchar();
while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
return flag * out;
}
//第一次打treap，不压行写注释XD
const int maxn = 1000019,INF = 1e9;
//平衡树，利用BST性质查询和修改，利用随机和堆优先级来保持平衡，把树的深度控制在log N，保证了操作效率
//基本平衡树有以下几个比较重要的函数：新建，插入，删除，旋转
//节点的基本属性有val(值)，dat(随机出来的优先级)
//通过增加属性，结合BST的性质可以达到一些效果，如size(子树大小，查询排名)，cnt(每个节点包含的副本数)等
int na;
int ch[maxn][2];//[i][0]代表i左儿子，[i][1]代表i右儿子
int val[maxn],dat[maxn];
int size[maxn],cnt[maxn];
int tot,root;
int New(int v){//新增节点，
val[++tot] = v;//节点赋值
dat[tot] = rand();//随机优先级
size[tot] = 1;//目前是新建叶子节点，所以子树大小为1
cnt[tot] = 1;//新建节点同理副本数为1
return tot;
}
void pushup(int id){//和线段树的pushup更新一样
size[id] = size[ch[id][0]] + size[ch[id][1]] + cnt[id];//本节点子树大小 = 左儿子子树大小 + 右儿子子树大小 + 本节点副本数
}
void build(){
root = New(-INF),ch[root][1] = New(INF);//先加入正无穷和负无穷，便于之后操作(貌似不加也行)
pushup(root);//因为INF > -INF,所以是右子树，
}
void Rotate(int &id,int d){//id是引用传递，d(irection)为旋转方向，0为左旋，1为右旋
int temp = ch[id][d ^ 1];//旋转理解：找个动图看一看就好(或参见其他OIer的blog)
ch[id][d ^ 1] = ch[temp][d];//这里讲一个记忆技巧，这些数据都是被记录后马上修改
ch[temp][d] = id;//所以像“Z”一样
id = temp;//比如这个id，在上一行才被记录过，ch[temp][d]、ch[id][d ^ 1]也是一样的
pushup(ch[id][d]),pushup(id);//旋转以后size会改变，看图就会发现只更新自己和转上来的点，pushup一下,注意先子节点再父节点
}//旋转实质是({在满足BST的性质的基础上比较优先级}通过交换本节点和其某个叶子节点)把链叉开成二叉形状(从而控制深度)，可以看图理解一下
void insert(int &id,int v){//id依然是引用，在新建节点时可以体现
if(!id){
id = New(v);//若节点为空，则新建一个节点
return ;
}
if(v == val[id])cnt[id]++;//若节点已存在，则副本数++;
else{//要满足BST性质，小于插到左边，大于插到右边
int d = v < val[id] ? 0 : 1;//这个d是方向的意思，按照BST的性质，小于本节点则向左，大于向右
insert(ch[id][d],v);//递归实现
if(dat[id] < dat[ch[id][d]])Rotate(id,d ^ 1);//(参考一下图)与左节点交换右旋，与右节点交换左旋
}
pushup(id);//现在更新一下本节点的信息
}
void Remove(int &id,int v){//最难de部分了
if(!id)return ;//到这了发现查不到这个节点，该点不存在，直接返回
if(v == val[id]){//检索到了这个值
if(cnt[id] > 1){cnt[id]--,pushup(id);return ;}//若副本不止一个，减去一个就好
if(ch[id][0] || ch[id][1]){//发现只有一个值，且有儿子节点,我们只能把值旋转到底部删除
if(!ch[id][1] || dat[ch[id][0]] > dat[ch[id][1]]){//当前点被移走之后，会有一个新的点补上来(左儿子或右儿子)，按照优先级，优先级大的补上来
Rotate(id,1),Remove(ch[id][1],v);//我们会发现，右旋是与左儿子交换，当前点变成右节点；左旋则是与右儿子交换，当前点变为左节点
}
else Rotate(id,0),Remove(ch[id][0],v);
pushup(id);
}
else id = 0;//发现本节点是叶子节点，直接删除
return ;//这个return对应的是检索到值de所有情况
}
v < val[id] ? Remove(ch[id][0],v) : Remove(ch[id][1],v);//继续BST性质
pushup(id);
}
int get_rank(int id,int v){
if(!id)return 1;//若查询值不存在，返回；因为最后要减一排除哨兵节点，想要结果为-1这里就返回0
if(v == val[id])return size[ch[id][0]] + 1;//查询到该值，由BST性质可知：该点左边值都比该点的值(查询值)小，故rank为左儿子大小 + 1
else if(v < val[id])return get_rank(ch[id][0],v);//发现需查询的点在该点左边，往左边递归查询
else return size[ch[id][0]] + cnt[id] + get_rank(ch[id][1],v);//若查询值大于该点值。说明询问点在当前点的右侧，且此点的值都小于查询值，所以要加上cnt[id]
}
int get_val(int id,int rank){
if(!id)return INF;//一直向右找找不到，说明是正无穷
if(rank <= size[ch[id][0]])return get_val(ch[id][0],rank);//左边排名已经大于rank了，说明rank对应的值在左儿子那里
else if(rank <= size[ch[id][0]] + cnt[id])return val[id];//上一步排除了在左区间的情况，若是rank在左与中(目前节点)中，则直接返回目前节点(中区间)的值
else return get_val(ch[id][1],rank - size[ch[id][0]] - cnt[id]);//剩下只能在右区间找了，rank减去左区间大小和中区间，继续递归
}
int get_pre(int v){
int id = root,pre;//递归不好返回，以循环求解
while(id){//查到节点不存在为止
if(val[id] < v)pre = val[id],id = ch[id][1];//满足当前节点比目标小，往当前节点的右侧寻找最优值
else id = ch[id][0];//无论是比目标节点大还是等于目标节点，都不满足前驱条件，应往更小处靠近
}
return pre;
}
int get_next(int v){
int id = root,next;
while(id){
if(val[id] > v)next = val[id],id = ch[id][0];//同理，满足条件向左寻找更小解(也就是最优解)
else id = ch[id][1];//与上方同理
}
return next;
}
int main(){
build();//不要忘记初始化[运行build()会连同root一并初始化，所以很重要]
na = RD();
for(int i = 1;i <= na;i++){
int cmd = RD(),x = RD();
if(cmd == 1)insert(root,x);//函数都写好了，注意：需要递归的函数都从根开始，不需要递归的函数直接查询
else if(cmd == 2)Remove(root,x);
else if(cmd == 3)printf("%d\n",get_rank(root,x) - 1);//注意：因为初始化时插入了INF和-INF,所以查询排名时要减1(-INF不是第一小，是“第零小”)
else if(cmd == 4)printf("%d\n",get_val(root,x + 1));//同理，用排名查询值得时候要查x + 1名，因为第一名(其实不是)是-INF
else if(cmd == 5)printf("%d\n",get_pre(x));
else if(cmd == 6)printf("%d\n",get_next(x));
}
return 0;
}P3380 【模板】树套树
题目描述
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
- 查询 $k$ 在区间内的排名；
- 查询区间内排名为 $k$ 的值；
- 修改某一位置上的数值；
- 查询 $k$ 在区间内的前驱（前驱定义为严格小于 $x$，且最大的数，若不存在输出
-2147483647）； - 查询 $k$ 在区间内的后继（后继定义为严格大于 $x$，且最小的数，若不存在输出
2147483647）。
对于一组元素，一个数的排名被定义为严格比它小的元素个数加一，而排名为 $k$ 的数被定义为“将元素从小到大排序后排在第 $k$ 位的元素值”。
输入格式
第一行两个数 $n,m$，表示长度为 $n$ 的有序序列和 $m$ 个操作。
第二行有 $n$ 个数，表示有序序列。
下面有 $m$ 行，$opt$ 表示操作标号。
若 $opt=1$，则为操作 $1$，之后有三个数 $l~r~k$，表示查询 $k$ 在区间 $[l,r]$ 的排名。
若 $opt=2$，则为操作 $2$，之后有三个数 $l~r~k$，表示查询区间 $[l,r]$ 内排名为 $k$ 的数。
若 $opt=3$，则为操作 $3$，之后有两个数 $pos~k$，表示将 $pos$ 位置的数修改为 $k$。
若 $opt=4$，则为操作 $4$，之后有三个数 $l~r~k$，表示查询区间 $[l,r]$ 内 $k$ 的前驱。
若 $opt=5$，则为操作 $5$，之后有三个数 $l~r~k$，表示查询区间 $[l,r]$ 内 $k$ 的后继。
输出格式
对于操作 $1,2,4,5$，各输出一行，表示查询结果。
输入输出样例 #1
输入 #1
9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5输出 #1
2
4
3
4
9说明/提示
$1\le n,m\le5\times 10^4$，序列中的值在任何时刻 $\in[0,10^8]$。
题目来源：bzoj3196 / Tyvj1730，在此鸣谢。
此数据为洛谷原创。（特别提醒：此数据不保证操作 4、5 一定存在，故请务必考虑不存在的情况。）
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;const int N=5*1e4+10;const int M=1e5+10;
const int B=260;const int B2=300;int a[N];//维护的表格
int cnt1[N/B+3][M/B2+3];int cnt2[N/B+3][M];int n;int m;int bi[N];int bi1[M];
int tr1[M];int tr2[M];map <int,int> mp;int S;int Pr[M];int Pl[M];int val[M];
inline int frk(int l,int r,int va)//查询元素的排名
{
int p1=bi[l];int p2=bi[r];int ret=0;
if(p1==p2){for(int i=l;i<=r;i++)ret+=(a[i]<va);return ret+1;}
for(int i=l;bi[i]==p1;i++)ret+=(a[i]<va);
for(int i=r;bi[i]==p2;i--)ret+=(a[i]<va);p2--;
for(int i=1;i<bi1[va];i++)ret+=cnt1[p2][i];
for(int i=1;i<bi1[va];i++)ret-=cnt1[p1][i];
for(int i=va-1;bi1[i]==bi1[va];i--)ret+=cnt2[p2][i];
for(int i=va-1;bi1[i]==bi1[va];i--)ret-=cnt2[p1][i];return ret+1;
}
inline int ckth(const int& p1,const int& p2,int k)//辅助函数，查询kth
{
int ret=B2;int cur=0;
for(int t=1;cur<k;ret+=B2,t++)cur+=cnt1[p2][t]-cnt1[p1][t]+tr1[t];ret-=B2;
for(;cur>=k;ret--)cur-=cnt2[p2][ret]-cnt2[p1][ret]+tr2[ret];return ret+1;
}
inline int cpre(const int& p1,const int& p2,int k)//辅助函数，查询前驱
{
for(int i=k-1;bi1[i]==bi1[k];i--)
if(cnt2[p2][i]-cnt2[p1][i]+tr2[i])return i;
int p;for(p=bi1[k]-1;(cnt1[p2][p]-cnt1[p1][p]+tr1[p])==0;p--);
for(int i=Pr[p];;i--)if(cnt2[p2][i]-cnt2[p1][i]+tr2[i])return i;
}
inline int csuf(const int& p1,const int& p2,int k)//辅助函数，查询后继
{
for(int i=k+1;bi1[i]==bi1[k];i++)
if(cnt2[p2][i]-cnt2[p1][i]+tr2[i])return i;
int p;for(p=bi1[k]+1;(cnt1[p2][p]-cnt1[p1][p]+tr1[p])==0;p++);
for(int i=Pl[p];;i++)if(cnt2[p2][i]-cnt2[p1][i]+tr2[i])return i;
}
# define ins(x) tr1[bi1[x]]++,tr2[x]++
# define del(x) tr1[bi1[x]]--,tr2[x]--
inline int calc(int l,int r,int k,int(*f)(const int& p1,const int& p2,int k))//这里用了个函数指针
{
int p1=bi[l];int p2=bi[r];int ret=0;//直接处理出区间的cnt1,cnt2数组
if(p1==p2)
{
for(int i=l;i<=r;i++)ins(a[i]);ret=f(p1,p2,k);
for(int i=l;i<=r;i++)del(a[i]);return val[ret];
}
for(int i=l;bi[i]==p1;i++)ins(a[i]);
for(int i=r;bi[i]==p2;i--)ins(a[i]);ret=f(p1,p2-1,k);
for(int i=l;bi[i]==p1;i++)del(a[i]);
for(int i=r;bi[i]==p2;i--)del(a[i]);return val[ret];//记得还原回离散化之前的值
}
inline void modify(int pos,int y)//暴力修改
{
int p=bi1[a[pos]];for(int i=bi[pos];i<=bi[n];i++)cnt1[i][p]--;
p=a[pos];for(int i=bi[pos];i<=bi[n];i++)cnt2[i][p]--;
p=bi1[y];for(int i=bi[pos];i<=bi[n];i++)cnt1[i][p]++;
for(int i=bi[pos];i<=bi[n];i++)cnt2[i][y]++;a[pos]=y;
}
struct opt{int tp;int l;int r;int k;}op[N];
int main()
{
scanf("%d%d",&n,&m);mp[-2147483647]=1;mp[2147483647]=1;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),mp[a[i]]=1;
for(int i=1;i<=m;i++)
{
scanf("%d",&op[i].tp);
if(op[i].tp!=3)scanf("%d%d%d",&op[i].l,&op[i].r,&op[i].k);
else scanf("%d%d",&op[i].l,&op[i].k);if(op[i].tp!=2)mp[op[i].k]=1;
}
S=mp.size();map <int,int> :: iterator it,it1;//离散化
for(it=mp.begin(),it1=it,++it1;it1!=mp.end();++it,++it1)it1->second+=it->second;
for(it=mp.begin();it!=mp.end();++it)val[it->second]=it->first;
for(int i=1;i<=n;i++)a[i]=mp[a[i]];
for(int i=1;i<=m;i++)if(op[i].tp!=2)op[i].k=mp[op[i].k];
for(int i=1;i<=n;i++)bi[i]=(i-1)/B+1;for(int i=1;i<=S;i++)bi1[i]=(i-1)/B2+1;
for(int i=1;i<=S;i++)Pr[bi1[i]]=i;for(int i=S;i>=1;i--)Pl[bi1[i]]=i;
for(int i=1;i<=n;i++)
{
int p=bi1[a[i]];for(int j=bi[i];j<=bi[n];j++)cnt1[j][p]++;
p=a[i];for(int j=bi[i];j<=bi[n];j++)cnt2[j][p]++;
}ins(1);ins(S);//插入哨兵
for(int i=1;i<=m;i++)
switch(op[i].tp)
{
case 1:{printf("%d\n",frk(op[i].l,op[i].r,op[i].k));break;}
case 2:{printf("%d\n",calc(op[i].l,op[i].r,op[i].k+1,ckth));break;}
case 3:{modify(op[i].l,op[i].k);break;}
case 4:{printf("%d\n",calc(op[i].l,op[i].r,op[i].k,cpre));break;}
case 5:{printf("%d\n",calc(op[i].l,op[i].r,op[i].k,csuf));break;}
}return 0;//拜拜程序~
}P3373 【模板】线段树 2
题目描述
如题，已知一个数列 $a$，你需要进行下面三种操作：
- 将某区间每一个数乘上 $x$；
- 将某区间每一个数加上 $x$；
- 求出某区间每一个数的和。
输入格式
第一行包含三个整数 $n,q,m$，分别表示该数列数字的个数、操作的总个数和模数。
第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值 $a_i$。
接下来 $q$ 行每行包含若干个整数，表示一个操作，具体如下：
操作 $1$： 格式：1 x y k 含义：将区间 $[x,y]$ 内每个数乘上 $k$。
操作 $2$： 格式：2 x y k 含义：将区间 $[x,y]$ 内每个数加上 $k$。
操作 $3$： 格式：3 x y 含义：输出区间 $[x,y]$ 内每个数的和对 $m$ 取模所得的结果。
输出格式
输出包含若干行整数，即为所有操作 $3$ 的结果。
输入输出样例 #1
输入 #1
5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4输出 #1
17
2说明/提示
【数据范围】
对于 $30\%$ 的数据：$n \le 8$，$q \le 10$。
对于 $70\%$ 的数据：$n \le 10^3 $，$q \le 10^4$。
对于 $100\%$ 的数据：$1 \le n \le 10^5$，$1 \le q \le 10^5,1\le a_i,k\le 10^4$。
除样例外，$m = 571373$。
（数据已经过加强 ^_^）
样例说明：
故输出应为 $17$、$2$（$40 \bmod 38 = 2$）。
#include <bits/stdc++.h>
#define MAXN 100010
#define ll long long
using namespace std;
int n, m, mod;
int a[MAXN];
struct Segment_Tree {
ll sum, add, mul;
int l, r;
}s[MAXN * 4];
void update(int pos) {
s[pos].sum = (s[pos << 1].sum + s[pos << 1 | 1].sum) % mod;
return;
}
void pushdown(int pos) { //pushdown的维护
s[pos << 1].sum = (s[pos << 1].sum * s[pos].mul + s[pos].add * (s[pos << 1].r - s[pos << 1].l + 1)) % mod;
s[pos << 1 | 1].sum = (s[pos << 1 | 1].sum * s[pos].mul + s[pos].add * (s[pos << 1 | 1].r - s[pos << 1 | 1].l + 1)) % mod;
s[pos << 1].mul = (s[pos << 1].mul * s[pos].mul) % mod;
s[pos << 1 | 1].mul = (s[pos << 1 | 1].mul * s[pos].mul) % mod;
s[pos << 1].add = (s[pos << 1].add * s[pos].mul + s[pos].add) % mod;
s[pos << 1 | 1].add = (s[pos << 1 | 1].add * s[pos].mul + s[pos].add) % mod;
s[pos].add = 0;
s[pos].mul = 1;
return;
}
void build_tree(int pos, int l, int r) { //建树
s[pos].l = l;
s[pos].r = r;
s[pos].mul = 1;
if (l == r) {
s[pos].sum = a[l] % mod;
return;
}
int mid = (l + r) >> 1;
build_tree(pos << 1, l, mid);
build_tree(pos << 1 | 1, mid + 1, r);
update(pos);
return;
}
void ChangeMul(int pos, int x, int y, int k) { //区间乘法
if (x <= s[pos].l && s[pos].r <= y) {
s[pos].add = (s[pos].add * k) % mod;
s[pos].mul = (s[pos].mul * k) % mod;
s[pos].sum = (s[pos].sum * k) % mod;
return;
}
pushdown(pos);
int mid = (s[pos].l + s[pos].r) >> 1;
if (x <= mid) ChangeMul(pos << 1, x, y, k);
if (y > mid) ChangeMul(pos << 1 | 1, x, y, k);
update(pos);
return;
}
void ChangeAdd(int pos, int x, int y, int k) { //区间加法
if (x <= s[pos].l && s[pos].r <= y) {
s[pos].add = (s[pos].add + k) % mod;
s[pos].sum = (s[pos].sum + k * (s[pos].r - s[pos].l + 1)) % mod;
return;
}
pushdown(pos);
int mid = (s[pos].l + s[pos].r) >> 1;
if (x <= mid) ChangeAdd(pos << 1, x, y, k);
if (y > mid) ChangeAdd(pos << 1 | 1, x, y, k);
update(pos);
return;
}
ll AskRange(int pos, int x, int y) { //区间询问
if (x <= s[pos].l && s[pos].r <= y) {
return s[pos].sum;
}
pushdown(pos);
ll val = 0;
int mid = (s[pos].l + s[pos].r) >> 1;
if (x <= mid) val = (val + AskRange(pos << 1, x, y)) % mod;
if (y > mid) val = (val + AskRange(pos << 1 | 1, x, y)) % mod;
return val;
}
int main() {
scanf("%d%d%d", &n, &m, &mod);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
build_tree(1, 1, n);
for (int i = 1; i <= m; i++) {
int opt, x, y;
scanf("%d%d%d", &opt, &x, &y);
if (opt == 1) {
int k;
scanf("%d", &k);
ChangeMul(1, x, y, k);
}
if (opt == 2) {
int k;
scanf("%d", &k);
ChangeAdd(1, x, y, k);
}
if (opt == 3) {
printf("%lld\n", AskRange(1, x, y));
}
}
return 0;
}P6242 【模板】线段树 3（区间最值操作、区间历史最值）
题目背景
本题是线段树维护区间最值操作与区间历史最值的模板。
题目描述
给出一个长度为 $n$ 的数列 $A$，同时定义一个辅助数组 $B$，$B$ 开始与 $A$ 完全相同。接下来进行了 $m$ 次操作，操作有五种类型，按以下格式给出：
1 l r k：对于所有的 $i\in[l,r]$，将 $A_i$ 加上 $k$（$k$ 可以为负数）。2 l r v：对于所有的 $i\in[l,r]$，将 $A_i$ 变成 $\min(A_i,v)$。3 l r：求 $\sum_{i=l}^{r}A_i$。4 l r：对于所有的 $i\in[l,r]$，求 $A_i$ 的最大值。5 l r：对于所有的 $i\in[l,r]$，求 $B_i$ 的最大值。
在每一次操作后，我们都进行一次更新，让 $B_i\gets\max(B_i,A_i)$。
输入格式
第一行包含两个正整数 $n,m$，分别表示数列 $A$ 的长度和操作次数。
第二行包含 $n$ 个整数 $A_1,A_2,\cdots,A_n$，表示数列 $A$。
接下来 $m$ 行，每行行首有一个整数 $op$，表示操作类型；接下来两个或三个整数表示操作参数，格式见【题目描述】。
输出格式
对于 $op\in\{3,4,5\}$ 的操作，输出一行包含一个整数，表示这个询问的答案。
输入输出样例 #1
输入 #1
5 6
1 2 3 4 5
3 2 5
1 1 3 3
4 2 4
2 3 4 1
5 1 5
3 1 4输出 #1
14
6
6
11说明/提示
样例说明 #1
| 操作次数 | 输入内容 | 操作 | 数列 | 输出结果 |
|---|---|---|---|---|
| 0 | $1,2,3,4,5$ | |||
| 1 | 3 2 5 |
求出 $[2,5]$ 所有数的和 | $1,2,3,4,5$ | 14 |
| 2 | 1 1 3 3 |
将 $[1,3]$ 内所有数加 $3$ | $4,5,6,4,5$ | |
| 3 | 4 2 4 |
求出 $[2,4]$ 所有数的最大值 | $4,5,6,4,5$ | 6 |
| 4 | 2 3 4 1 |
将 $[3,4]$ 所有数与 $1$ 取最小值 | $4,5,1,1,5$ | |
| 5 | 5 1 5 |
求出 $[1,5]$ 所有位置历史最大值的最大值 | $4,5,1,1,5$ | 6 |
| 6 | 3 1 4 |
求出 $[1,4]$ 所有数的和 | $4,5,1,1,5$ | 11 |
数据规模与约定
- 对于测试点 $1,2$，满足 $n,m\leq 5000$；
- 对于测试点 $3,4$，满足 $op\in\{1,2,3,4\}$；
- 对于测试点 $5,6$，满足 $op\in\{1,3,4,5\}$；
- 对于全部测试数据，保证 $1\leq n,m\leq 5\times 10^5$，$-5\times10^8\leq A_i\leq 5\times10^8$，$op\in[1,5]$，$1 \leq l\leq r \leq n$，$-2000\leq k\leq 2000$，$-5\times10^8\leq v\leq 5\times10^8$。
提示
本题输入量较大，请使用合理高效的读入方法。
/*
this code is made by warzone
2022.2.14 21:25
*/
#include<stdio.h>
#include<string.h>
typedef long long ll;
typedef unsigned int word;
struct READ{//快读
char pool[5<<22],*top,w;
inline READ(){fread(top=pool,5<<22,1,stdin);}
template<typename type>
inline READ& operator >>(type& num){
for(w=1;'0'>*top||*top>'9';)
w=*(top++)=='-'? -1:1;
for(num=0;'0'<=*top&&*top<='9';)
num=num*10+(*(top++)-'0');
return num*=w,*this;
}
}cin;
const int inf=0x80000000;//−∞
inline int max(const int a,const int b){
return a>b? a:b;}
/* 向量/矩阵
⎡a⎤ ⎡a −∞⎤
⎣b⎦ ⎣b 0⎦
*/
struct matrix{
int a,b;
inline matrix(){}
inline matrix(const matrix &p)=default;
inline matrix(int A,int B):a(A),b(B){}
inline matrix operator+(const matrix &p)const{//矩阵/向量 加法
return matrix(max(a,p.a),max(b,p.b));}
inline matrix operator()(const matrix &p)const{//矩阵乘法
return matrix(a==inf||p.a==inf? inf:a+p.a,
b==inf||p.a==inf? p.b:max(b+p.a,p.b));}
inline bool operator!=(const matrix &p)const{
return a!=p.a||b!=p.b;}
}const I(0,inf),vec0(inf,inf);
word n,m;
struct segment_tree{//线段树（zkw）
ll sum[1u<<20];
int cnt[1u<<20];
matrix mx[1u<<20],M[1u<<20];
matrix se[1u<<20],E[1u<<20];
inline segment_tree(){
for(word i=0;i<(1u<<20);++i) M[i]=E[i]=I;
se[1u<<19]=vec0,cnt[1u<<19]=1,cin>>n>>m;
for(int i=(1u<<19)+1,num;i<=(1u<<19|n);++i){
se[i]=vec0,cnt[i]=1,cin>>num;
sum[i]=mx[i].a=mx[i].b=num;
}
for(word i=(1u<<19|n)+1;i<(1u<<20);++i)
se[i]=vec0,cnt[i]=1;
for(word i=(1u<<19)-1;i;--i) pushup(i);
}
#define l (rt<<1)
#define r (rt<<1|1)
inline void pushup(const word rt){//上传信息
sum[rt]=sum[l]+sum[r];
if(mx[l].a>mx[r].a){
mx[rt]=mx[l],cnt[rt]=cnt[l];
se[rt]=se[l]+se[r]+mx[r];
}else if(mx[l].a<mx[r].a){
mx[rt]=mx[r],cnt[rt]=cnt[r];
se[rt]=se[l]+se[r]+mx[l];
}else{
mx[rt]=mx[l]+mx[r];
cnt[rt]=cnt[l]+cnt[r];
se[rt]=se[l]+se[r];
}
}
inline void Mmul(const matrix &p,const word id){//修改 mx
mx[id]=p(mx[id]),M[id]=p(M[id]),sum[id]+=1ll*cnt[id]*p.a;}
inline void Emul(const matrix &p,const word id,const word size){//修改 se
se[id]=p(se[id]),E[id]=p(E[id]);
sum[id]+=1ll*(size-cnt[id])*p.a;
}
inline void pushdown(const word rt,const word size){//下传标记
Mmul(mx[l].a==mx[rt].a-M[rt].a? M[rt]:E[rt],l);
Mmul(mx[r].a==mx[rt].a-M[rt].a? M[rt]:E[rt],r);
//注意此处不能用 mx[l].a 和 mx[r].a 的大小关系来判断划分，因为标记下传后 mx 会被修改
if(size!=1) Emul(E[rt],l,size),Emul(E[rt],r,size);
M[rt]=E[rt]=I;
}
inline void plus(const word f,const word t,const int k,
const word rt=1,const word size=1u<<18){//区间加
if(size==0||(f==0&&t==(size<<1)-1))
return Mmul(matrix(k,k),rt),Emul(matrix(k,k),rt,size? size<<1:1);
auto lf=[&](word f,word t){plus(f,t,k,l,size>>1);};
auto rf=[&](word f,word t){plus(f,t,k,r,size>>1);};
pushdown(rt,size);
if(f&size) rf(f&~size,t&~size);
else if((t&size)^size) lf(f,t);
else lf(f,size-1),rf(0,t&~size);
pushup(rt);
}
inline void min(const word f,const word t,const int k,
const word rt=1,const word size=1u<<18){//区间取 min
if(k>=mx[rt].a) return;
const auto lf=[&](word f,word t){min(f,t,k,l,size>>1);};
const auto rf=[&](word f,word t){min(f,t,k,r,size>>1);};
if(size==0||(f==0&&t==(size<<1)-1)){
if(k>se[rt].a) return Mmul(matrix(k-mx[rt].a,k-mx[rt].a),rt);
return pushdown(rt,size),lf(0,size-1),rf(0,size-1),pushup(rt);
}
pushdown(rt,size);
if(f&size) rf(f&~size,t&~size);
else if((t&size)^size) lf(f,t);
else lf(f,size-1),rf(0,t&~size);
pushup(rt);
}
inline ll getsum(const word f,const word t,
const word rt=1,const word size=1u<<18){//区间求和
if(size==0||(f==0&&t==(size<<1)-1)) return sum[rt];
const auto lf=[&](word f,word t)->ll{return getsum(f,t,l,size>>1);};
const auto rf=[&](word f,word t)->ll{return getsum(f,t,r,size>>1);};
pushdown(rt,size);
if(f&size) return rf(f&~size,t&~size);
else if((t&size)^size) return lf(f,t);
return lf(f,size-1)+rf(0,t&~size);
}
inline int geta(const word f,const word t,
const word rt=1,const word size=1u<<18){//区间最值
if(size==0||(f==0&&t==(size<<1)-1)) return mx[rt].a;
const auto lf=[&](word f,word t)->ll{return geta(f,t,l,size>>1);};
const auto rf=[&](word f,word t)->ll{return geta(f,t,r,size>>1);};
pushdown(rt,size);
if(f&size) return rf(f&~size,t&~size);
else if((t&size)^size) return lf(f,t);
return max(lf(f,size-1),rf(0,t&~size));
}
inline int getb(const word f,const word t,
const word rt=1,const word size=1u<<18){//区间历史最值
if(size==0||(f==0&&t==(size<<1)-1)) return max(mx[rt].b,se[rt].b);
const auto lf=[&](word f,word t)->ll{return getb(f,t,l,size>>1);};
const auto rf=[&](word f,word t)->ll{return getb(f,t,r,size>>1);};
pushdown(rt,size);
if(f&size) return rf(f&~size,t&~size);
else if((t&size)^size) return lf(f,t);
return max(lf(f,size-1),rf(0,t&~size));
}
#undef l
#undef r
}tree;
int main(){
for(int opt,l,r;m;--m)
if(cin>>opt>>l>>r,opt==1)
cin>>opt,tree.plus(l,r,opt);
else if(opt==2) cin>>opt,tree.min(l,r,opt);
else if(opt==4) printf("%d\n",tree.geta(l,r));
else if(opt==5) printf("%d\n",tree.getb(l,r));
else printf("%lld\n",tree.getsum(l,r));
return 0;
}标准库头文件 <algorithm>
C++ 标准库头文件
此头文件是算法库的一部分。
包含
<initializer_list>
(C++11)
std::initializer_list 类模板
类
定义于命名空间 std::ranges
返回类型 (C++20)
ranges::in_fun_result
(C++20)
提供了一种将迭代器和函数对象存储为单个单元的方法
(类模板)
ranges::in_in_result
(C++20)
提供了一种将两个迭代器存储为单个单元的方法
(类模板)
ranges::in_out_result
(C++20)
提供了一种将两个迭代器存储为单个单元的方法
(类模板)
ranges::in_in_out_result
(C++20)
提供了一种将三个迭代器存储为单个单元的方法
(类模板)
ranges::in_out_out_result
(C++20)
提供了一种将三个迭代器存储为单个单元的方法
(类模板)
ranges::min_max_result
(C++20)
提供了一种将两个相同类型的对象或引用存储为单个单元的方法
(类模板)
ranges::in_found_result
(C++20)
提供了一种将迭代器和布尔标志存储为单个单元的方法
(类模板)
ranges::in_value_result
(C++23)
提供了一种将迭代器和值存储为单个单元的方法
(类模板)
ranges::out_value_result
(C++23)
提供了一种将迭代器和值存储为单个单元的方法
(类模板)
函数
非修改序列操作
all_of
any_of
none_of
(C++11)
(C++11)
(C++11)
检查谓词对于范围中所有、任何或没有元素是否为真
(函数模板)
for_each
将一元函数对象应用于来自范围的元素
(函数模板)
for_each_n
(C++17)
将函数对象应用于序列的前 N 个元素
(函数模板)
count
count_if
返回满足特定条件的元素数量
(函数模板)
mismatch
查找两个范围不同的第一个位置
(函数模板)
find
find_if
find_if_not
(C++11)
查找满足特定条件的第一个元素
(函数模板)
find_end
查找某个范围中元素的最后一个序列
(函数模板)
find_first_of
搜索元素集合中的任何一个
(函数模板)
adjacent_find
查找第一个相等的相邻项（或满足给定谓词的相邻项）
(函数模板)
search
搜索元素范围的第一次出现
(函数模板)
search_n
搜索范围中连续重复元素一定次数的第一次出现
(函数模板)
修改序列操作
copy
copy_if
(C++11)
将元素范围复制到新位置
(函数模板)
copy_n
(C++11)
将一定数量的元素复制到新位置
(函数模板)
copy_backward
以向后顺序复制元素范围
(函数模板)
move
(C++11)
将元素范围移动到新位置
(函数模板)
move_backward
(C++11)
以向后顺序将元素范围移动到新位置
(函数模板)
fill
将给定值复制赋值给范围中的每个元素
(函数模板)
fill_n
将给定值复制赋值给范围中的 N 个元素
(函数模板)
transform
将函数应用于元素范围，并将结果存储在目标范围中
(函数模板)
generate
将连续函数调用的结果赋值给范围中的每个元素
(函数模板)
generate_n
将连续函数调用的结果赋值给范围中的 N 个元素
(函数模板)
remove
remove_if
移除满足特定条件的元素
(函数模板)
remove_copy
remove_copy_if
复制元素范围，省略那些满足特定条件的元素
(函数模板)
replace
replace_if
将所有满足特定条件的值替换为另一个值
(函数模板)
replace_copy
replace_copy_if
复制一个范围，将满足特定条件的元素替换为另一个值
(函数模板)
swap
交换两个对象的值
(函数模板)
swap_ranges
交换两个元素范围
(函数模板)
iter_swap
交换两个迭代器指向的元素
(函数模板)
reverse
反转范围中元素的顺序
(函数模板)
reverse_copy
创建一个反转的范围副本
(函数模板)
rotate
旋转范围中元素的顺序
(函数模板)
rotate_copy
复制并旋转元素范围
(函数模板)
shift_left
shift_right
(C++20)
移动范围中的元素
(函数模板)
random_shuffle
shuffle
(until C++17)
(C++11)
随机重新排序范围中的元素
(函数模板)
sample
(C++17)
从序列中选择 N 个随机元素
(函数模板)
unique
移除范围中连续重复的元素
(函数模板)
unique_copy
创建某个元素范围的副本，其中不包含连续重复项
(函数模板)
分区操作
is_partitioned
(C++11)
确定范围是否由给定谓词分区
(函数模板)
partition
将元素范围划分为两组
(函数模板)
partition_copy
(C++11)
复制一个范围，将元素划分为两组
(函数模板)
stable_partition
将元素划分为两组，同时保持其相对顺序
(函数模板)
partition_point
(C++11)
定位已分区范围的分区点
(函数模板)
排序操作
is_sorted
(C++11)
检查范围是否已排序为升序
(函数模板)
is_sorted_until
(C++11)
查找最大的已排序子范围
(函数模板)
sort
将范围排序为升序
(函数模板)
partial_sort
对范围的前 N 个元素进行排序
(函数模板)
partial_sort_copy
复制并部分排序元素范围
(函数模板)
stable_sort
排序元素范围，同时保持相等元素之间的顺序
(函数模板)
nth_element
部分排序给定范围，确保它按给定元素分区
(函数模板)
二分搜索操作 (在已排序范围上)
lower_bound
返回指向第一个不小于给定值的元素的迭代器
(function template)
upper_bound
返回指向首个大于某值的元素的迭代器
(function template)
binary_search
确定元素是否存在于部分有序的范围内
(function template)
equal_range
返回与特定键匹配的元素范围
(function template)
其他排序范围上的操作
merge
合并两个已排序的范围
(function template)
inplace_merge
就地合并两个有序范围
(function template)
集合操作（在已排序的范围上）
includes
如果一个序列是另一个序列的子序列，则返回 true
(function template)
set_difference
计算两个集合的差集
(function template)
set_intersection
计算两个集合的交集
(function template)
set_symmetric_difference
计算两个集合的对称差集
(function template)
set_union
计算两个集合的并集
(function template)
堆操作
is_heap
(C++11)
检查给定范围是否为最大堆
(function template)
is_heap_until
(C++11)
查找作为最大堆的最大子范围
(function template)
make_heap
从元素范围创建最大堆
(function template)
push_heap
向最大堆添加元素
(function template)
pop_heap
从最大堆中移除最大的元素
(function template)
sort_heap
将最大堆转换为升序排序的元素范围
(function template)
最小值/最大值操作
max
返回给定值中较大的那个
(function template)
max_element
返回范围中最大的元素
(function template)
min
返回给定值中较小的那个
(function template)
min_element
返回范围中最小的元素
(function template)
minmax
(C++11)
返回两个元素中较小和较大的那个
(function template)
minmax_element
(C++11)
返回范围中最小和最大的元素
(function template)
clamp
(C++17)
将值限制在边界值对之间
(function template)
比较操作
equal
确定两组元素是否相同
(function template)
lexicographical_compare
如果一个范围在字典序上小于另一个范围，则返回 true
(function template)
lexicographical_compare_three_way
(C++20)
使用三路比较比较两个范围
(function template)
排列操作
is_permutation
(C++11)
确定一个序列是否是另一个序列的排列
(function template)
next_permutation
生成元素范围的下一个更大的字典序排列
(function template)
prev_permutation
生成元素范围的下一个更小的字典序排列
(function template)
类似函数的实体 (C++20)
定义于命名空间 std::ranges
非修改序列操作
ranges::all_of
ranges::any_of
ranges::none_of
(C++20)
(C++20)
(C++20)
检查谓词对于范围中所有、任何或没有元素是否为真
(algorithm function object)
ranges::for_each
(C++20)
将一元函数对象应用于来自范围的元素
(algorithm function object)
ranges::for_each_n
(C++20)
将函数对象应用于序列的前 N 个元素
(algorithm function object)
ranges::count
ranges::count_if
(C++20)
(C++20)
返回满足特定条件的元素数量
(algorithm function object)
ranges::mismatch
(C++20)
查找两个范围不同的第一个位置
(algorithm function object)
ranges::find
ranges::find_if
ranges::find_if_not
(C++20)
(C++20)
(C++20)
查找满足特定条件的第一个元素
(algorithm function object)
ranges::find_last
ranges::find_last_if
ranges::find_last_if_not
(C++23)
(C++23)
(C++23)
查找满足特定条件的最后一个元素
(algorithm function object)
ranges::find_end
(C++20)
查找某个范围中元素的最后一个序列
(algorithm function object)
ranges::find_first_of
(C++20)
搜索元素集合中的任何一个
(algorithm function object)
ranges::adjacent_find
(C++20)
查找第一个相等的相邻项（或满足给定谓词的相邻项）
(algorithm function object)
ranges::search
(C++20)
搜索元素范围的第一次出现
(algorithm function object)
ranges::search_n
(C++20)
搜索范围中连续重复元素一定次数的第一次出现
(algorithm function object)
ranges::contains
ranges::contains_subrange
(C++23)
(C++23)
检查范围是否包含给定的元素或子范围
(algorithm function object)
ranges::starts_with
(C++23)
检查一个范围是否以另一个范围开始
(algorithm function object)
ranges::ends_with
(C++23)
检查一个范围是否以另一个范围结束
(algorithm function object)
折叠操作
ranges::fold_left
(C++23)
左折叠元素范围
(algorithm function object)
ranges::fold_left_first
(C++23)
使用第一个元素作为初始值左折叠元素范围
(algorithm function object)
ranges::fold_right
(C++23)
右折叠元素范围
(algorithm function object)
ranges::fold_right_last
(C++23)
使用最后一个元素作为初始值右折叠元素范围
(algorithm function object)
ranges::fold_left_with_iter
(C++23)
左折叠元素范围，并返回一个 pair (迭代器, 值)
(algorithm function object)
ranges::fold_left_first_with_iter
(C++23)
使用第一个元素作为初始值左折叠元素范围，并返回一个 pair (迭代器, optional)
(algorithm function object)
修改序列操作
ranges::copy
ranges::copy_if
(C++20)
(C++20)
将元素范围复制到新位置
(algorithm function object)
ranges::copy_n
(C++20)
将一定数量的元素复制到新位置
(algorithm function object)
ranges::copy_backward
(C++20)
以向后顺序复制元素范围
(algorithm function object)
ranges::move
(C++20)
将元素范围移动到新位置
(algorithm function object)
ranges::move_backward
(C++20)
以向后顺序将元素范围移动到新位置
(algorithm function object)
ranges::fill
(C++20)
为元素范围赋值
(algorithm function object)
ranges::fill_n
(C++20)
为若干元素赋值
(algorithm function object)
ranges::transform
(C++20)
将函数应用于元素范围
(algorithm function object)
ranges::generate
(C++20)
将函数结果保存在范围中
(algorithm function object)
ranges::generate_n
(C++20)
保存函数 N 次应用的结果
(algorithm function object)
ranges::remove
ranges::remove_if
(C++20)
(C++20)
移除满足特定条件的元素
(algorithm function object)
ranges::remove_copy
ranges::remove_copy_if
(C++20)
(C++20)
复制元素范围，省略那些满足特定条件的元素
(algorithm function object)
ranges::replace
ranges::replace_if
(C++20)
(C++20)
将所有满足特定条件的值替换为另一个值
(algorithm function object)
ranges::replace_copy
ranges::replace_copy_if
(C++20)
(C++20)
复制一个范围，将满足特定条件的元素替换为另一个值
(algorithm function object)
ranges::swap_ranges
(C++20)
交换两个元素范围
(algorithm function object)
ranges::reverse
(C++20)
反转范围中元素的顺序
(algorithm function object)
ranges::reverse_copy
(C++20)
创建一个反转的范围副本
(algorithm function object)
ranges::rotate
(C++20)
旋转范围中元素的顺序
(algorithm function object)
ranges::rotate_copy
(C++20)
复制并旋转元素范围
(algorithm function object)
ranges::shift_left
ranges::shift_right
(C++23)
移动范围中的元素
(algorithm function object)
ranges::sample
(C++20)
从序列中选择 N 个随机元素
(algorithm function object)
ranges::shuffle
(C++20)
随机重新排序范围中的元素
(algorithm function object)
ranges::unique
(C++20)
移除范围中连续重复的元素
(algorithm function object)
ranges::unique_copy
(C++20)
创建某个元素范围的副本，其中不包含连续重复项
(algorithm function object)
分区操作
ranges::is_partitioned
(C++20)
确定范围是否由给定谓词分区
(algorithm function object)
ranges::partition
(C++20)
将元素范围划分为两组
(algorithm function object)
ranges::partition_copy
(C++20)
复制一个范围，将元素划分为两组
(algorithm function object)
ranges::stable_partition
(C++20)
将元素划分为两组，同时保持其相对顺序
(algorithm function object)
ranges::partition_point
(C++20)
定位已分区范围的分区点
(algorithm function object)
排序操作
ranges::is_sorted
(C++20)
检查范围是否已排序为升序
(algorithm function object)
ranges::is_sorted_until
(C++20)
查找最大的已排序子范围
(algorithm function object)
ranges::sort
(C++20)
将范围排序为升序
(algorithm function object)
ranges::partial_sort
(C++20)
对范围的前 N 个元素进行排序
(algorithm function object)
ranges::partial_sort_copy
(C++20)
复制并部分排序元素范围
(algorithm function object)
ranges::stable_sort
(C++20)
排序元素范围，同时保持相等元素之间的顺序
(algorithm function object)
ranges::nth_element
(C++20)
部分排序给定范围，确保它按给定元素分区
(algorithm function object)
二分搜索操作 (在已排序范围上)
ranges::lower_bound
(C++20)
返回指向第一个不小于给定值的元素的迭代器
(algorithm function object)
ranges::upper_bound
(C++20)
返回指向首个大于某值的元素的迭代器
(algorithm function object)
ranges::binary_search
(C++20)
确定元素是否存在于部分有序的范围内
(algorithm function object)
ranges::equal_range
(C++20)
返回与特定键匹配的元素范围
(algorithm function object)
其他排序范围上的操作
ranges::merge
(C++20)
合并两个已排序的范围
(algorithm function object)
ranges::inplace_merge
(C++20)
就地合并两个有序范围
(algorithm function object)
集合操作（在已排序的范围上）
ranges::includes
(C++20)
如果一个序列是另一个序列的子序列，则返回 true
(algorithm function object)
ranges::set_difference
(C++20)
计算两个集合的差集
(algorithm function object)
ranges::set_intersection
(C++20)
计算两个集合的交集
(algorithm function object)
ranges::set_symmetric_difference
(C++20)
计算两个集合的对称差集
(algorithm function object)
ranges::set_union
(C++20)
计算两个集合的并集
(algorithm function object)
堆操作
ranges::is_heap
(C++20)
检查给定范围是否为最大堆
(algorithm function object)
ranges::is_heap_until
(C++20)
查找作为最大堆的最大子范围
(algorithm function object)
ranges::make_heap
(C++20)
从元素范围创建最大堆
(algorithm function object)
ranges::push_heap
(C++20)
向最大堆添加元素
(algorithm function object)
ranges::pop_heap
(C++20)
从最大堆中移除最大的元素
(algorithm function object)
ranges::sort_heap
(C++20)
将最大堆转换为升序排序的元素范围
(algorithm function object)
最小值/最大值操作
ranges::max
(C++20)
返回给定值中较大的那个
(algorithm function object)
ranges::max_element
(C++20)
返回范围中最大的元素
(algorithm function object)
ranges::min
(C++20)
返回给定值中较小的那个
(algorithm function object)
ranges::min_element
(C++20)
返回范围中最小的元素
(algorithm function object)
ranges::minmax
(C++20)
返回两个元素中较小和较大的那个
(algorithm function object)
ranges::minmax_element
(C++20)
返回范围中最小和最大的元素
(algorithm function object)
ranges::clamp
(C++20)
将值限制在边界值对之间
(algorithm function object)
比较操作
ranges::equal
(C++20)
确定两组元素是否相同
(algorithm function object)
ranges::lexicographical_compare
(C++20)
如果一个范围在字典序上小于另一个范围，则返回 true
(算法函数对象)
排列操作
ranges::is_permutation
(C++20)
确定一个序列是否是另一个序列的排列
(算法函数对象)
ranges::next_permutation
(C++20)
生成元素范围的下一个更大的字典序排列
(算法函数对象)
ranges::prev_permutation
(C++20)
生成元素范围的下一个更小的字典序排列
(算法函数对象)
概要
#include <initializer_list>
namespace std {
namespace ranges {
// algorithm result types
template<class I, class F>
struct in_fun_result;
template<class I1, class I2>
struct in_in_result;
template<class I, class O>
struct in_out_result;
template<class I1, class I2, class O>
struct in_in_out_result;
template<class I, class O1, class O2>
struct in_out_out_result;
template<class T>
struct min_max_result;
template<class I>
struct in_found_result;
template<class I, class T>
struct in_value_result;
template<class O, class T>
struct out_value_result;
}
// non-modifying sequence operations
// all of
template<class InputIter, class Pred>
constexpr bool all_of(InputIter first, InputIter last, Pred pred);
template<class ExecutionPolicy, class ForwardIter, class Pred>
bool all_of(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, Pred pred);
namespace ranges {
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr bool all_of(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr bool all_of(R&& r, Pred pred, Proj proj = {});
}
// any of
template<class InputIter, class Pred>
constexpr bool any_of(InputIter first, InputIter last, Pred pred);
template<class ExecutionPolicy, class ForwardIter, class Pred>
bool any_of(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, Pred pred);
namespace ranges {
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr bool any_of(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr bool any_of(R&& r, Pred pred, Proj proj = {});
}
// none of
template<class InputIter, class Pred>
constexpr bool none_of(InputIter first, InputIter last, Pred pred);
template<class ExecutionPolicy, class ForwardIter, class Pred>
bool none_of(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, Pred pred);
namespace ranges {
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr bool none_of(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr bool none_of(R&& r, Pred pred, Proj proj = {});
}
// contains
namespace ranges {
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
constexpr bool contains(I first, S last, const T& value, Proj proj = {});
template<input_range R, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>>
requires indirect_binary_predicate<ranges::equal_to,
projected<iterator_t<R>, Proj>, const T*>
constexpr bool contains(R&& r, const T& value, Proj proj = {});
template<forward_iterator I1, sentinel_for<I1> S1,
forward_iterator I2, sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity,
class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr bool contains_subrange(I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = {}, Proj1 proj1 = {},
Proj2 proj2 = {});
template<forward_range R1, forward_range R2,
class Pred = ranges::equal_to, class Proj1 = identity,
class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr bool contains_subrange(R1&& r1, R2&& r2,
Pred pred = {}, Proj1 proj1 = {},
Proj2 proj2 = {});
}
// for each
template<class InputIter, class Function>
constexpr Function for_each(InputIter first, InputIter last, Function f);
template<class ExecutionPolicy, class ForwardIter, class Function>
void for_each(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, Function f);
namespace ranges {
template<class I, class F>
using for_each_result = in_fun_result<I, F>;
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
indirectly_unary_invocable<projected<I, Proj>> Fun>
constexpr for_each_result<I, Fun>
for_each(I first, S last, Fun f, Proj proj = {});
template<input_range R, class Proj = identity,
indirectly_unary_invocable<projected<iterator_t<R>, Proj>> Fun>
constexpr for_each_result<borrowed_iterator_t<R>, Fun>
for_each(R&& r, Fun f, Proj proj = {});
}
template<class InputIter, class Size, class Function>
constexpr InputIter for_each_n(InputIter first, Size n, Function f);
template<class ExecutionPolicy, class ForwardIter, class Size, class Function>
ForwardIter for_each_n(ExecutionPolicy&& exec,
ForwardIter first, Size n, Function f);
namespace ranges {
template<class I, class F>
using for_each_n_result = in_fun_result<I, F>;
template<input_iterator I, class Proj = identity,
indirectly_unary_invocable<projected<I, Proj>> Fun>
constexpr for_each_n_result<I, Fun>
for_each_n(I first, iter_difference_t<I> n, Fun f, Proj proj = {});
}
// find
template<class InputIter, class T = typename iterator_traits<InputIter>::value_type>
constexpr InputIter find(InputIter first, InputIter last, const T& value);
template<class ExecutionPolicy, class ForwardIter,
class T = typename iterator_traits<InputIter>::value_type>
ForwardIter find(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, const T& value);
template<class InputIter, class Pred>
constexpr InputIter find_if(InputIter first, InputIter last, Pred pred);
template<class ExecutionPolicy, class ForwardIter, class Pred>
ForwardIter find_if(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, Pred pred);
template<class InputIter, class Pred>
constexpr InputIter find_if_not(InputIter first, InputIter last, Pred pred);
template<class ExecutionPolicy, class ForwardIter, class Pred>
ForwardIter find_if_not(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, Pred pred);
namespace ranges {
template<input_iterator I, sentinel_for<I> S, class Proj = identity
class T = projected_value_t<I, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
constexpr I find(I first, S last, const T& value, Proj proj = {});
template<input_range R, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>>
requires indirect_binary_predicate<ranges::equal_to,
projected<iterator_t<R>, Proj>, const T*>
constexpr borrowed_iterator_t<R>
find(R&& r, const T& value, Proj proj = {});
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr I find_if(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr borrowed_iterator_t<R>
find_if(R&& r, Pred pred, Proj proj = {});
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr I find_if_not(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr borrowed_iterator_t<R>
find_if_not(R&& r, Pred pred, Proj proj = {});
}
// find last
namespace ranges {
template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
constexpr subrange<I> find_last(I first, S last, const T& value, Proj proj = {});
template<forward_range R, class T, class Proj = identity>
requires
indirect_binary_predicate<ranges::equal_to,
projected<iterator_t<R>, Proj>, const T*>
constexpr borrowed_subrange_t<R> find_last(R&& r, const T& value, Proj proj = {});
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr subrange<I> find_last_if(I first, S last, Pred pred, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr borrowed_subrange_t<R> find_last_if(R&& r, Pred pred, Proj proj = {});
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr subrange<I> find_last_if_not(I first, S last, Pred pred, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr borrowed_subrange_t<R> find_last_if_not(R&& r, Pred pred, Proj proj = {});
}
// find end
template<class ForwardIter1, class ForwardIter2>
constexpr ForwardIter1
find_end(ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2);
template<class ForwardIter1, class ForwardIter2, class BinaryPred>
constexpr ForwardIter1
find_end(ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2,
BinaryPred pred);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2>
ForwardIter1
find_end(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2);
template<class ExecutionPolicy, class ForwardIter1,
class ForwardIter2, class BinaryPred>
ForwardIter1
find_end(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2,
BinaryPred pred);
namespace ranges {
template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
sentinel_for<I2> S2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr subrange<I1>
find_end(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<forward_range R1, forward_range R2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr borrowed_subrange_t<R1>
find_end(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
}
// find first
template<class InputIter, class ForwardIter>
constexpr InputIter
find_first_of(InputIter first1, InputIter last1,
ForwardIter first2, ForwardIter last2);
template<class InputIter, class ForwardIter, class BinaryPred>
constexpr InputIter
find_first_of(InputIter first1, InputIter last1,
ForwardIter first2, ForwardIter last2,
BinaryPred pred);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2>
ForwardIter1
find_first_of(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2);
template<class ExecutionPolicy, class ForwardIter1,
class ForwardIter2, class BinaryPred>
ForwardIter1
find_first_of(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2,
BinaryPred pred);
namespace ranges {
template<input_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
sentinel_for<I2> S2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr I1 find_first_of(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, forward_range R2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr borrowed_iterator_t<R1>
find_first_of(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
}
// adjacent find
template<class ForwardIter>
constexpr ForwardIter adjacent_find(ForwardIter first, ForwardIter last);
template<class ForwardIter, class BinaryPred>
constexpr ForwardIter adjacent_find(ForwardIter first, ForwardIter last,
BinaryPred pred);
template<class ExecutionPolicy, class ForwardIter>
ForwardIter adjacent_find(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last);
template<class ExecutionPolicy, class ForwardIter, class BinaryPred>
ForwardIter adjacent_find(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, BinaryPred pred);
namespace ranges {
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_binary_predicate<projected<I, Proj>,
projected<I, Proj>> Pred = ranges::equal_to>
constexpr I adjacent_find(I first, S last, Pred pred = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_binary_predicate<projected<iterator_t<R>, Proj>,
projected<iterator_t<R>, Proj>>
Pred = ranges::equal_to>
constexpr borrowed_iterator_t<R>
adjacent_find(R&& r, Pred pred = {}, Proj proj = {});
}
// count
template<class InputIter, class T = typename iterator_traits<InputIter>::value_type>
constexpr typename iterator_traits<InputIter>::difference_type
count(InputIter first, InputIter last, const T& value);
template<class ExecutionPolicy, class ForwardIter,
class T = typename iterator_traits<InputIterator>::value_type>
typename iterator_traits<ForwardIter>::difference_type
count(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, const T& value);
template<class InputIter, class Pred>
constexpr typename iterator_traits<InputIter>::difference_type
count_if(InputIter first, InputIter last, Pred pred);
template<class ExecutionPolicy, class ForwardIter, class Pred>
typename iterator_traits<ForwardIter>::difference_type
count_if(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, Pred pred);
namespace ranges {
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
constexpr iter_difference_t<I>
count(I first, S last, const T& value, Proj proj = {});
template<input_range R, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>>
requires indirect_binary_predicate<ranges::equal_to,
projected<iterator_t<R>, Proj>, const T*>
constexpr range_difference_t<R>
count(R&& r, const T& value, Proj proj = {});
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr iter_difference_t<I>
count_if(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr range_difference_t<R>
count_if(R&& r, Pred pred, Proj proj = {});
}
// mismatch
template<class InputIter1, class InputIter2>
constexpr pair<InputIter1, InputIter2>
mismatch(InputIter1 first1, InputIter1 last1,
InputIter2 first2);
template<class InputIter1, class InputIter2, class BinaryPred>
constexpr pair<InputIter1, InputIter2>
mismatch(InputIter1 first1, InputIter1 last1,
InputIter2 first2, BinaryPred pred);
template<class InputIter1, class InputIter2>
constexpr pair<InputIter1, InputIter2>
mismatch(InputIter1 first1, InputIter1 last1,
InputIter2 first2, InputIter2 last2);
template<class InputIter1, class InputIter2, class BinaryPred>
constexpr pair<InputIter1, InputIter2>
mismatch(InputIter1 first1, InputIter1 last1,
InputIter2 first2, InputIter2 last2,
BinaryPred pred);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2>
pair<ForwardIter1, ForwardIter2>
mismatch(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class BinaryPred>
pair<ForwardIter1, ForwardIter2>
mismatch(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, BinaryPred pred);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2>
pair<ForwardIter1, ForwardIter2>
mismatch(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class BinaryPred>
pair<ForwardIter1, ForwardIter2>
mismatch(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2,
BinaryPred pred);
namespace ranges {
template<class I1, class I2>
using mismatch_result = in_in_result<I1, I2>;
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2,
sentinel_for<I2> S2, class Pred = ranges::equal_to, class Proj1 = identity,
class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr mismatch_result<I1, I2>
mismatch(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2,
class Pred = ranges::equal_to, class Proj1 = identity,
class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr mismatch_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
mismatch(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
}
// equal
template<class InputIter1, class InputIter2>
constexpr bool equal(InputIter1 first1, InputIter1 last1,
InputIter2 first2);
template<class InputIter1, class InputIter2, class BinaryPred>
constexpr bool equal(InputIter1 first1, InputIter1 last1,
InputIter2 first2, BinaryPred pred);
template<class InputIter1, class InputIter2>
constexpr bool equal(InputIter1 first1, InputIter1 last1,
InputIter2 first2, InputIter2 last2);
template<class InputIter1, class InputIter2, class BinaryPred>
constexpr bool equal(InputIter1 first1, InputIter1 last1,
InputIter2 first2, InputIter2 last2,
BinaryPred pred);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2>
bool equal(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class BinaryPred>
bool equal(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, BinaryPred pred);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2>
bool equal(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class BinaryPred>
bool equal(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2,
BinaryPred pred);
namespace ranges {
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2,
sentinel_for<I2> S2, class Pred = ranges::equal_to, class Proj1 = identity,
class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr bool equal(I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr bool equal(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
}
// is permutation
template<class ForwardIter1, class ForwardIter2>
constexpr bool is_permutation(ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2);
template<class ForwardIter1, class ForwardIter2, class BinaryPred>
constexpr bool is_permutation(ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, BinaryPred pred);
template<class ForwardIter1, class ForwardIter2>
constexpr bool is_permutation(ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2);
template<class ForwardIter1, class ForwardIter2, class BinaryPred>
constexpr bool is_permutation(ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2,
BinaryPred pred);
namespace ranges {
template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
sentinel_for<I2> S2, class Proj1 = identity, class Proj2 = identity,
indirect_equivalence_relation<projected<I1, Proj1>,
projected<I2, Proj2>> Pred = ranges::equal_to>
constexpr bool is_permutation(I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<forward_range R1, forward_range R2,
class Proj1 = identity, class Proj2 = identity,
indirect_equivalence_relation<projected<iterator_t<R1>, Proj1>,
projected<iterator_t<R2>, Proj2>>
Pred = ranges::equal_to>
constexpr bool is_permutation(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
}
// search
template<class ForwardIter1, class ForwardIter2>
constexpr ForwardIter1
search(ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2);
template<class ForwardIter1, class ForwardIter2, class BinaryPred>
constexpr ForwardIter1
search(ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2, BinaryPred pred);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2>
ForwardIter1
search(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class BinaryPred>
ForwardIter1
search(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2, BinaryPred pred);
namespace ranges {
template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
sentinel_for<I2> S2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr subrange<I1>
search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<forward_range R1, forward_range R2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr borrowed_subrange_t<R1>
search(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
}
template<class ForwardIter, class Size,
class T = typename iterator_traits<ForwardIter>::value_type>
constexpr ForwardIter
search_n(ForwardIter first, ForwardIter last,
Size count, const T& value);
template<class ForwardIter, class Size,
class T = typename iterator_traits<ForwardIter>::value_type, class BinaryPred>
constexpr ForwardIter
search_n(ForwardIter first, ForwardIter last,
Size count, const T& value, BinaryPred pred);
template<class ExecutionPolicy, class ForwardIter, class Size,
class T = typename iterator_traits<ForwardIter>::value_type>
ForwardIter
search_n(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last,
Size count, const T& value);
template<class ExecutionPolicy, class ForwardIter, class Size,
class T = typename iterator_traits<ForwardIter>::value_type, class BinaryPred>
ForwardIter
search_n(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last,
Size count, const T& value, BinaryPred pred);
namespace ranges {
template<forward_iterator I, sentinel_for<I> S,
class Pred = ranges::equal_to, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirectly_comparable<I, const T*, Pred, Proj>
constexpr subrange<I>
search_n(I first, S last, iter_difference_t<I> count,
const T& value, Pred pred = {}, Proj proj = {});
template<forward_range R, class Pred = ranges::equal_to, class Proj = identity,
projected_value_t<iterator_t<R>, Proj>>
requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj>
constexpr borrowed_subrange_t<R>
search_n(R&& r, range_difference_t<R> count,
const T& value, Pred pred = {}, Proj proj = {});
}
template<class ForwardIter, class Searcher>
constexpr ForwardIter
search(ForwardIter first, ForwardIter last, const Searcher& searcher);
namespace ranges {
// starts with
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2,
sentinel_for<I2> S2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr bool starts_with(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr bool starts_with(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
// ends with
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2,
sentinel_for<I2> S2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires (forward_iterator<I1> || sized_sentinel_for<S1, I1>) &&
(forward_iterator<I2> || sized_sentinel_for<S2, I2>) &&
indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr bool ends_with(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires (forward_range<R1> || sized_range<R1>) &&
(forward_range<R2> || sized_range<R2>) &&
indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr bool ends_with(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
// fold
template<class F>
class /* flipped */ { // exposition only
F f; // exposition only
public:
template<class T, class U> requires invocable<F&, U, T>
invoke_result_t<F&, U, T> operator()(T&&, U&&);
};
template<class F, class T, class I, class U>
concept /* indirectly-binary-left-foldable-impl */ = // exposition only
movable<T> && movable<U> &&
convertible_to<T, U> && invocable<F&, U, iter_reference_t<I>> &&
assignable_from<U&, invoke_result_t<F&, U, iter_reference_t<I>>>;
template<class F, class T, class I>
concept /* indirectly-binary-left-foldable */ = // exposition only
copy_constructible<F> && indirectly_readable<I> &&
invocable<F&, T, iter_reference_t<I>> &&
convertible_to<invoke_result_t<F&, T, iter_reference_t<I>>,
decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>> &&
/* indirectly-binary-left-foldable-impl */
<F, T, I, decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>>;
template<class F, class T, class I>
concept /* indirectly-binary-right-foldable */ = // exposition only
/* indirectly-binary-left-foldable */</* flipped */<F>, T, I>;
template<input_iterator I, sentinel_for<I> S, class T = iter_value_t<I>,
/* indirectly-binary-left-foldable */<T, I> F>
constexpr auto fold_left(I first, S last, T init, F f);
template<input_range R, class T = range_value_t<R>,
/* indirectly-binary-left-foldable */<T, iterator_t<R>> F>
constexpr auto fold_left(R&& r, T init, F f);
template<input_iterator I, sentinel_for<I> S,
/* indirectly-binary-left-foldable */<iter_value_t<I>, I> F>
requires constructible_from<iter_value_t<I>, iter_reference_t<I>>
constexpr auto fold_left_first(I first, S last, F f);
template<input_range R,
/* indirectly-binary-left-foldable */<range_value_t<R>, iterator_t<R>> F>
requires constructible_from<range_value_t<R>, range_reference_t<R>>
constexpr auto fold_left_first(R&& r, F f);
template<bidirectional_iterator I, sentinel_for<I> S, class T = iter_value_t<I>,
/* indirectly-binary-right-foldable */<T, I> F>
constexpr auto fold_right(I first, S last, T init, F f);
template<bidirectional_range R, class T = range_value_t<R>,
/* indirectly-binary-right-foldable */<T, iterator_t<R>> F>
constexpr auto fold_right(R&& r, T init, F f);
template<bidirectional_iterator I, sentinel_for<I> S,
/* indirectly-binary-right-foldable */<iter_value_t<I>, I> F>
requires constructible_from<iter_value_t<I>, iter_reference_t<I>>
constexpr auto fold_right_last(I first, S last, F f);
template<bidirectional_range R,
/* indirectly-binary-right-foldable */<range_value_t<R>, iterator_t<R>> F>
requires constructible_from<range_value_t<R>, range_reference_t<R>>
constexpr auto fold_right_last(R&& r, F f);
template<class I, class T>
using fold_left_with_iter_result = in_value_result<I, T>;
template<class I, class T>
using fold_left_first_with_iter_result = in_value_result<I, T>;
template<input_iterator I, sentinel_for<I> S, class T = iter_value_t<I>,
/* indirectly-binary-left-foldable */<T, I> F>
constexpr /* see description */ fold_left_with_iter(I first, S last, T init, F f);
template<input_range R, class T = range_value_t<R>,
/* indirectly-binary-left-foldable */<T, iterator_t<R>> F>
constexpr /* see description */ fold_left_with_iter(R&& r, T init, F f);
template<input_iterator I, sentinel_for<I> S,
/* indirectly-binary-left-foldable */<iter_value_t<I>, I> F>
requires constructible_from<iter_value_t<I>, iter_reference_t<I>>
constexpr /* see description */ fold_left_first_with_iter(I first, S last, F f);
template<input_range R,
/* indirectly-binary-left-foldable */<range_value_t<R>, iterator_t<R>> F>
requires constructible_from<range_value_t<R>, range_reference_t<R>>
constexpr /* see description */ fold_left_first_with_iter(R&& r, F f);
}
// mutating sequence operations
// copy
template<class InputIter, class OutputIter>
constexpr OutputIter copy(InputIter first, InputIter last,
OutputIter result);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2>
ForwardIter2 copy(ExecutionPolicy&& exec,
ForwardIter1 first, ForwardIter1 last,
ForwardIter2 result);
namespace ranges {
template<class I, class O>
using copy_result = in_out_result<I, O>;
template<input_iterator I, sentinel_for<I> S, weakly_incrementable O>
requires indirectly_copyable<I, O>
constexpr copy_result<I, O> copy(I first, S last, O result);
template<input_range R, weakly_incrementable O>
requires indirectly_copyable<iterator_t<R>, O>
constexpr copy_result<borrowed_iterator_t<R>, O> copy(R&& r, O result);
}
template<class InputIter, class Size, class OutputIter>
constexpr OutputIter copy_n(InputIter first, Size n, OutputIter result);
template<class ExecutionPolicy,
class ForwardIter1, class Size, class ForwardIter2>
ForwardIter2 copy_n(ExecutionPolicy&& exec,
ForwardIter1 first, Size n, ForwardIter2 result);
namespace ranges {
template<class I, class O>
using copy_n_result = in_out_result<I, O>;
template<input_iterator I, weakly_incrementable O>
requires indirectly_copyable<I, O>
constexpr copy_n_result<I, O> copy_n(I first, iter_difference_t<I> n, O result);
}
template<class InputIter, class OutputIter, class Pred>
constexpr OutputIter copy_if(InputIter first, InputIter last,
OutputIter result, Pred pred);
template<class ExecutionPolicy,
class ForwardIter1, class ForwardIter2, class Pred>
ForwardIter2 copy_if(ExecutionPolicy&& exec,
ForwardIter1 first, ForwardIter1 last,
ForwardIter2 result, Pred pred);
namespace ranges {
template<class I, class O>
using copy_if_result = in_out_result<I, O>;
template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
requires indirectly_copyable<I, O>
constexpr copy_if_result<I, O>
copy_if(I first, S last, O result, Pred pred, Proj proj = {});
template<input_range R, weakly_incrementable O, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires indirectly_copyable<iterator_t<R>, O>
constexpr copy_if_result<borrowed_iterator_t<R>, O>
copy_if(R&& r, O result, Pred pred, Proj proj = {});
}
template<class BidirectionalIter1, class BidirectionalIter2>
constexpr BidirectionalIter2
copy_backward(BidirectionalIter1 first, BidirectionalIter1 last,
BidirectionalIter2 result);
namespace ranges {
template<class I1, class I2>
using copy_backward_result = in_out_result<I1, I2>;
template<bidirectional_iterator I1, sentinel_for<I1> S1, bidirectional_iterator I2>
requires indirectly_copyable<I1, I2>
constexpr copy_backward_result<I1, I2>
copy_backward(I1 first, S1 last, I2 result);
template<bidirectional_range R, bidirectional_iterator I>
requires indirectly_copyable<iterator_t<R>, I>
constexpr copy_backward_result<borrowed_iterator_t<R>, I>
copy_backward(R&& r, I result);
}
// move
template<class InputIter, class OutputIter>
constexpr OutputIter move(InputIter first, InputIter last, OutputIter result);
template<class ExecutionPolicy, class ForwardIter1,
class ForwardIter2>
ForwardIter2 move(ExecutionPolicy&& exec,
ForwardIter1 first, ForwardIter1 last, ForwardIter2 result);
namespace ranges {
template<class I, class O>
using move_result = in_out_result<I, O>;
template<input_iterator I, sentinel_for<I> S, weakly_incrementable O>
requires indirectly_movable<I, O>
constexpr move_result<I, O> move(I first, S last, O result);
template<input_range R, weakly_incrementable O>
requires indirectly_movable<iterator_t<R>, O>
constexpr move_result<borrowed_iterator_t<R>, O> move(R&& r, O result);
}
template<class BidirectionalIter1, class BidirectionalIter2>
constexpr BidirectionalIter2
move_backward(BidirectionalIter1 first, BidirectionalIter1 last,
BidirectionalIter2 result);
namespace ranges {
template<class I1, class I2>
using move_backward_result = in_out_result<I1, I2>;
template<bidirectional_iterator I1, sentinel_for<I1> S1, bidirectional_iterator I2>
requires indirectly_movable<I1, I2>
constexpr move_backward_result<I1, I2>
move_backward(I1 first, S1 last, I2 result);
template<bidirectional_range R, bidirectional_iterator I>
requires indirectly_movable<iterator_t<R>, I>
constexpr move_backward_result<borrowed_iterator_t<R>, I>
move_backward(R&& r, I result);
}
// swap
template<class ForwardIter1, class ForwardIter2>
constexpr ForwardIter2 swap_ranges(ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2>
ForwardIter2 swap_ranges(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2);
namespace ranges {
template<class I1, class I2>
using swap_ranges_result = in_in_result<I1, I2>;
template<input_iterator I1, sentinel_for<I1> S1,
input_iterator I2, sentinel_for<I2> S2>
requires indirectly_swappable<I1, I2>
constexpr swap_ranges_result<I1, I2>
swap_ranges(I1 first1, S1 last1, I2 first2, S2 last2);
template<input_range R1, input_range R2>
requires indirectly_swappable<iterator_t<R1>, iterator_t<R2>>
constexpr swap_ranges_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
swap_ranges(R1&& r1, R2&& r2);
}
template<class ForwardIter1, class ForwardIter2>
constexpr void iter_swap(ForwardIter1 a, ForwardIter2 b);
// transform
template<class InputIter, class OutputIter, class UnaryOperation>
constexpr OutputIter
transform(InputIter first1, InputIter last1,
OutputIter result, UnaryOperation op);
template<class InputIter1, class InputIter2, class OutputIter,
class BinaryOperation>
constexpr OutputIter
transform(InputIter1 first1, InputIter1 last1,
InputIter2 first2, OutputIter result,
BinaryOperation binary_op);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class UnaryOperation>
ForwardIter2
transform(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 result, UnaryOperation op);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class ForwardIter, class BinaryOperation>
ForwardIter
transform(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter result,
BinaryOperation binary_op);
namespace ranges {
template<class I, class O>
using unary_transform_result = in_out_result<I, O>;
template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
copy_constructible F, class Proj = identity>
requires indirectly_writable<O, indirect_result_t<F&, projected<I, Proj>>>
constexpr unary_transform_result<I, O>
transform(I first1, S last1, O result, F op, Proj proj = {});
template<input_range R, weakly_incrementable O,
copy_constructible F, class Proj = identity>
requires
indirectly_writable<O, indirect_result_t<F&, projected<iterator_t<R>, Proj>>>
constexpr unary_transform_result<borrowed_iterator_t<R>, O>
transform(R&& r, O result, F op, Proj proj = {});
template<class I1, class I2, class O>
using binary_transform_result = in_in_out_result<I1, I2, O>;
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2,
sentinel_for<I2> S2, weakly_incrementable O, copy_constructible F,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_writable<O, indirect_result_t<F&, projected<I1, Proj1>,
projected<I2, Proj2>>>
constexpr binary_transform_result<I1, I2, O>
transform(I1 first1, S1 last1, I2 first2, S2 last2, O result,
F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, weakly_incrementable O,
copy_constructible F, class Proj1 = identity, class Proj2 = identity>
requires indirectly_writable
<O, indirect_result_t<F&, projected<iterator_t<R1>, Proj1>,
projected<iterator_t<R2>, Proj2>>>
constexpr binary_transform_result<borrowed_iterator_t<R1>,
borrowed_iterator_t<R2>, O>
transform(R1&& r1, R2&& r2, O result,
F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {});
}
// replace
template<class ForwardIter, class T = typename iterator_traits<ForwardIter>::value_type>
constexpr void replace(ForwardIter first, ForwardIter last,
const T& old_value, const T& new_value);
template<class ExecutionPolicy, class ForwardIter,
class T = typename iterator_traits<ForwardIter>::value_type>
void replace(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last,
const T& old_value, const T& new_value);
template<class ForwardIter, class Pred,
class T = typename iterator_traits<ForwardIter>::value_type>
constexpr void replace_if(ForwardIter first, ForwardIter last,
Pred pred, const T& new_value);
template<class ExecutionPolicy, class ForwardIter, class Pred,
class T = typename iterator_traits<ForwardIter>::value_type>
void replace_if(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last,
Pred pred, const T& new_value);
namespace ranges {
template<input_iterator I, sentinel_for<I> S,
class Proj = identity, class T1 = projected_value_t<I, Proj>, class T2 = T1>
requires indirectly_writable<I, const T2&> &&
indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*>
constexpr I replace(I first, S last, const T1& old_value,
const T2& new_value, Proj proj = {});
template<input_range R, class Proj = identity,
class T1 = projected_value_t<iterator_t<R>, Proj>, class T2 = T1>
requires indirectly_writable<iterator_t<R>, const T2&> &&
indirect_binary_predicate<ranges::equal_to,
projected<iterator_t<R>, Proj>, const T1*>
constexpr borrowed_iterator_t<R> replace(R&& r, const T1& old_value,
const T2& new_value, Proj proj = {});
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>,
indirect_unary_predicate<projected<I, Proj>> Pred>
requires indirectly_writable<I, const T&>
constexpr I replace_if(I first, S last, Pred pred,
const T& new_value, Proj proj = {});
template<input_range R, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires indirectly_writable<iterator_t<R>, const T&>
constexpr borrowed_iterator_t<R> replace_if(R&& r, Pred pred,
const T& new_value, Proj proj = {});
}
template<class InputIter, class OutputIter, class T>
constexpr OutputIter replace_copy(InputIter first, InputIter last, OutputIter result,
const T& old_value, const T& new_value);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2, class T>
ForwardIter2 replace_copy(ExecutionPolicy&& exec,
ForwardIter1 first, ForwardIter1 last, ForwardIter2 result,
const T& old_value, const T& new_value);
template<class InputIter, class OutputIter, class Pred,
class T = typename iterator_traits<OutputIter>::value_type>
constexpr OutputIter replace_copy_if(InputIter first, InputIter last,
OutputIter result,
Pred pred, const T& new_value);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class Pred, class T = typename iterator_traits<ForwardIter2>::value_type>
ForwardIter2 replace_copy_if(ExecutionPolicy&& exec,
ForwardIter1 first, ForwardIter1 last,
ForwardIter2 result,
Pred pred, const T& new_value);
namespace ranges {
template<class I, class O>
using replace_copy_result = in_out_result<I, O>;
template<input_iterator I, sentinel_for<I> S, class O, class Proj = identity,
class T1 = projected_value_t<I, Proj>, class T2 = iter_value_t<O>>
requires indirectly_copyable<I, O> &&
indirect_binary_predicate<ranges::equal_to,
projected<I, Proj>, const T1*> &&
output_iterator<O, const T2&>
constexpr replace_copy_result<I, O>
replace_copy(I first, S last, O result, const T1& old_value,
const T2& new_value, Proj proj = {});
template<input_range R, class O, class Proj = identity,
class T1 = projected_value_t<iterator_t<R>, Proj>,
class T2 = iter_value_t<O>>
requires indirectly_copyable<iterator_t<R>, O> &&
indirect_binary_predicate<ranges::equal_to,
projected<iterator_t<R>, Proj>, const T1*> &&
output_iterator<O, const T2&>
constexpr replace_copy_result<borrowed_iterator_t<R>, O>
replace_copy(R&& r, O result, const T1& old_value,
const T2& new_value, Proj proj = {});
template<class I, class O>
using replace_copy_if_result = in_out_result<I, O>;
template<input_iterator I, sentinel_for<I> S, class O, class T = iter_value_t<O>,
class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
requires indirectly_copyable<I, O> && output_iterator<O, const T&>
constexpr replace_copy_if_result<I, O>
replace_copy_if(I first, S last, O result, Pred pred,
const T& new_value, Proj proj = {});
template<input_range R, class O, class T = iter_value_t<O>, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires indirectly_copyable<iterator_t<R>, O> && output_iterator<O, const T&>
constexpr replace_copy_if_result<borrowed_iterator_t<R>, O>
replace_copy_if(R&& r, O result, Pred pred,
const T& new_value, Proj proj = {});
}
// fill
template<class ForwardIter, class T = typename iterator_traits<ForwardIter>::value_type>
constexpr void fill(ForwardIter first, ForwardIter last, const T& value);
template<class ExecutionPolicy, class ForwardIter,
class T = typename iterator_traits<ForwardIter>::value_type>
void fill(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, const T& value);
template<class OutputIter, class Size,
class T = typename iterator_traits<OutputIter>::value_type>
constexpr OutputIter fill_n(OutputIter first, Size n, const T& value);
template<class ExecutionPolicy, class ForwardIter,
class Size, class T = typename iterator_traits<OutputIter>::value_type>
ForwardIter fill_n(ExecutionPolicy&& exec,
ForwardIter first, Size n, const T& value);
namespace ranges {
template<class O, sentinel_for<O> S, class T = iter_value_t<O>>
requires output_iterator<O, const T&>
constexpr O fill(O first, S last, const T& value);
template<class R, class T = range_value_t<R>>
requires output_range<R, const T&>
constexpr borrowed_iterator_t<R> fill(R&& r, const T& value);
template<class O, class T = iter_value_t<O>>
requires output_iterator<O, const T&>
constexpr O fill_n(O first, iter_difference_t<O> n, const T& value);
}
// generate
template<class ForwardIter, class Generator>
constexpr void generate(ForwardIter first, ForwardIter last, Generator gen);
template<class ExecutionPolicy, class ForwardIter, class Generator>
void generate(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, Generator gen);
template<class OutputIter, class Size, class Generator>
constexpr OutputIter generate_n(OutputIter first, Size n, Generator gen);
template<class ExecutionPolicy, class ForwardIter, class Size, class Generator>
ForwardIter generate_n(ExecutionPolicy&& exec,
ForwardIter first, Size n, Generator gen);
namespace ranges {
template<input_or_output_iterator O, sentinel_for<O> S, copy_constructible F>
requires invocable<F&> && indirectly_writable<O, invoke_result_t<F&>>
constexpr O generate(O first, S last, F gen);
template<class R, copy_constructible F>
requires invocable<F&> && output_range<R, invoke_result_t<F&>>
constexpr borrowed_iterator_t<R> generate(R&& r, F gen);
template<input_or_output_iterator O, copy_constructible F>
requires invocable<F&> && indirectly_writable<O, invoke_result_t<F&>>
constexpr O generate_n(O first, iter_difference_t<O> n, F gen);
}
// remove
template<class ForwardIter, class T = typename iterator_traits<ForwardIter>::value_type>
constexpr ForwardIter remove(ForwardIter first, ForwardIter last, const T& value);
template<class ExecutionPolicy, class ForwardIter,
class T = typename iterator_traits<ForwardIter>::value_type>
ForwardIter remove(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, const T& value);
template<class ForwardIter, class Pred>
constexpr ForwardIter remove_if(ForwardIter first, ForwardIter last, Pred pred);
template<class ExecutionPolicy, class ForwardIter, class Pred>
ForwardIter remove_if(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, Pred pred);
namespace ranges {
template<permutable I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
constexpr subrange<I> remove(I first, S last, const T& value, Proj proj = {});
template<forward_range R, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>>
requires permutable<iterator_t<R>> &&
indirect_binary_predicate<ranges::equal_to,
projected<iterator_t<R>, Proj>, const T*>
constexpr borrowed_subrange_t<R> remove(R&& r, const T& value, Proj proj = {});
template<permutable I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr subrange<I> remove_if(I first, S last, Pred pred, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R> remove_if(R&& r, Pred pred, Proj proj = {});
}
template<class InputIter, class OutputIter,
class T = typename iterator_traits<InputIter>::value_type>
constexpr OutputIter remove_copy(InputIter first, InputIter last,
OutputIter result, const T& value);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class T = typename iterator_traits<ForwardIter1>::value_type>
ForwardIter2 remove_copy(ExecutionPolicy&& exec,
ForwardIter1 first, ForwardIter1 last,
ForwardIter2 result, const T& value);
template<class InputIter, class OutputIter, class Pred>
constexpr OutputIter remove_copy_if(InputIter first, InputIter last,
OutputIter result, Pred pred);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2, class Pred>
ForwardIter2 remove_copy_if(ExecutionPolicy&& exec,
ForwardIter1 first, ForwardIter1 last,
ForwardIter2 result, Pred pred);
namespace ranges {
template<class I, class O>
using remove_copy_result = in_out_result<I, O>;
template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
class Proj = identity, class T = projected_value_t<I, Proj>>
requires indirectly_copyable<I, O> &&
indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
constexpr remove_copy_result<I, O>
remove_copy(I first, S last, O result, const T& value, Proj proj = {});
template<input_range R, weakly_incrementable O, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>>
requires indirectly_copyable<iterator_t<R>, O> &&
indirect_binary_predicate<ranges::equal_to,
projected<iterator_t<R>, Proj>, const T*>
constexpr remove_copy_result<borrowed_iterator_t<R>, O>
remove_copy(R&& r, O result, const T& value, Proj proj = {});
template<class I, class O>
using remove_copy_if_result = in_out_result<I, O>;
template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
requires indirectly_copyable<I, O>
constexpr remove_copy_if_result<I, O>
remove_copy_if(I first, S last, O result, Pred pred, Proj proj = {});
template<input_range R, weakly_incrementable O, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires indirectly_copyable<iterator_t<R>, O>
constexpr remove_copy_if_result<borrowed_iterator_t<R>, O>
remove_copy_if(R&& r, O result, Pred pred, Proj proj = {});
}
// unique
template<class ForwardIter>
constexpr ForwardIter unique(ForwardIter first, ForwardIter last);
template<class ForwardIter, class BinaryPred>
constexpr ForwardIter unique(ForwardIter first, ForwardIter last, BinaryPred pred);
template<class ExecutionPolicy, class ForwardIter>
ForwardIter unique(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last);
template<class ExecutionPolicy, class ForwardIter, class BinaryPred>
ForwardIter unique(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, BinaryPred pred);
namespace ranges {
template<permutable I, sentinel_for<I> S, class Proj = identity,
indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
constexpr subrange<I> unique(I first, S last, C comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_equivalence_relation
<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
requires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R> unique(R&& r, C comp = {}, Proj proj = {});
}
template<class InputIter, class OutputIter>
constexpr OutputIter unique_copy(InputIter first, InputIter last,
OutputIter result);
template<class InputIter, class OutputIter, class BinaryPred>
constexpr OutputIter unique_copy(InputIter first, InputIter last,
OutputIter result, BinaryPred pred);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2>
ForwardIter2 unique_copy(ExecutionPolicy&& exec,
ForwardIter1 first, ForwardIter1 last,
ForwardIter2 result);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class BinaryPred>
ForwardIter2 unique_copy(ExecutionPolicy&& exec,
ForwardIter1 first, ForwardIter1 last,
ForwardIter2 result, BinaryPred pred);
namespace ranges {
template<class I, class O>
using unique_copy_result = in_out_result<I, O>;
template<input_iterator I, sentinel_for<I> S,
weakly_incrementable O, class Proj = identity,
indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
requires indirectly_copyable<I, O> &&
(forward_iterator<I> ||
(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) ||
indirectly_copyable_storable<I, O>)
constexpr unique_copy_result<I, O>
unique_copy(I first, S last, O result, C comp = {}, Proj proj = {});
template<input_range R, weakly_incrementable O, class Proj = identity,
indirect_equivalence_relation
<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
requires indirectly_copyable<iterator_t<R>, O> &&
(forward_iterator<iterator_t<R>> ||
(input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>) ||
indirectly_copyable_storable<iterator_t<R>, O>)
constexpr unique_copy_result<borrowed_iterator_t<R>, O>
unique_copy(R&& r, O result, C comp = {}, Proj proj = {});
}
// reverse
template<class BidirectionalIter>
constexpr void reverse(BidirectionalIter first, BidirectionalIter last);
template<class ExecutionPolicy, class BidirectionalIter>
void reverse(ExecutionPolicy&& exec,
BidirectionalIter first, BidirectionalIter last);
namespace ranges {
template<bidirectional_iterator I, sentinel_for<I> S>
requires permutable<I>
constexpr I reverse(I first, S last);
template<bidirectional_range R>
requires permutable<iterator_t<R>>
constexpr borrowed_iterator_t<R> reverse(R&& r);
}
template<class BidirectionalIter, class OutputIter>
constexpr OutputIter reverse_copy(BidirectionalIter first, BidirectionalIter last,
OutputIter result);
template<class ExecutionPolicy, class BidirectionalIter, class ForwardIter>
ForwardIter reverse_copy(ExecutionPolicy&& exec,
BidirectionalIter first, BidirectionalIter last,
ForwardIter result);
namespace ranges {
template<class I, class O>
using reverse_copy_result = in_out_result<I, O>;
template<bidirectional_iterator I, sentinel_for<I> S, weakly_incrementable O>
requires indirectly_copyable<I, O>
constexpr reverse_copy_result<I, O>
reverse_copy(I first, S last, O result);
template<bidirectional_range R, weakly_incrementable O>
requires indirectly_copyable<iterator_t<R>, O>
constexpr reverse_copy_result<borrowed_iterator_t<R>, O>
reverse_copy(R&& r, O result);
}
// rotate
template<class ForwardIter>
constexpr ForwardIter rotate(ForwardIter first, ForwardIter middle, ForwardIter last);
template<class ExecutionPolicy, class ForwardIter>
ForwardIter rotate(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter middle, ForwardIter last);
namespace ranges {
template<permutable I, sentinel_for<I> S>
constexpr subrange<I> rotate(I first, I middle, S last);
template<forward_range R>
requires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R> rotate(R&& r, iterator_t<R> middle);
}
template<class ForwardIter, class OutputIter>
constexpr OutputIter rotate_copy(ForwardIter first, ForwardIter middle,
ForwardIter last, OutputIter result);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2>
ForwardIter2 rotate_copy(ExecutionPolicy&& exec,
ForwardIter1 first, ForwardIter1 middle,
ForwardIter1 last, ForwardIter2 result);
namespace ranges {
template<class I, class O>
using rotate_copy_result = in_out_result<I, O>;
template<forward_iterator I, sentinel_for<I> S, weakly_incrementable O>
requires indirectly_copyable<I, O>
constexpr rotate_copy_result<I, O>
rotate_copy(I first, I middle, S last, O result);
template<forward_range R, weakly_incrementable O>
requires indirectly_copyable<iterator_t<R>, O>
constexpr rotate_copy_result<borrowed_iterator_t<R>, O>
rotate_copy(R&& r, iterator_t<R> middle, O result);
}
// sample
template<class PopulationIter, class SampleIter,
class Distance, class UniformRandomBitGenerator>
SampleIter sample(PopulationIter first, PopulationIter last,
SampleIter out, Distance n, UniformRandomBitGenerator&& g);
namespace ranges {
template<input_iterator I, sentinel_for<I> S,
weakly_incrementable O, class Gen>
requires (forward_iterator<I> || random_access_iterator<O>) &&
indirectly_copyable<I, O> &&
uniform_random_bit_generator<remove_reference_t<Gen>>
O sample(I first, S last, O out, iter_difference_t<I> n, Gen&& g);
template<input_range R, weakly_incrementable O, class Gen>
requires (forward_range<R> || random_access_iterator<O>) &&
indirectly_copyable<iterator_t<R>, O> &&
uniform_random_bit_generator<remove_reference_t<Gen>>
O sample(R&& r, O out, range_difference_t<R> n, Gen&& g);
}
// shuffle
template<class RandomAccessIter, class UniformRandomBitGenerator>
void shuffle(RandomAccessIter first, RandomAccessIter last,
UniformRandomBitGenerator&& g);
namespace ranges {
template<random_access_iterator I, sentinel_for<I> S, class Gen>
requires permutable<I> &&
uniform_random_bit_generator<remove_reference_t<Gen>>
I shuffle(I first, S last, Gen&& g);
template<random_access_range R, class Gen>
requires permutable<iterator_t<R>> &&
uniform_random_bit_generator<remove_reference_t<Gen>>
borrowed_iterator_t<R> shuffle(R&& r, Gen&& g);
}
// shift
template<class ForwardIter>
constexpr ForwardIter
shift_left(ForwardIter first, ForwardIter last,
typename iterator_traits<ForwardIter>::difference_type n);
template<class ExecutionPolicy, class ForwardIter>
ForwardIter
shift_left(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last,
typename iterator_traits<ForwardIter>::difference_type n);
namespace ranges {
template<permutable I, sentinel_for<I> S>
constexpr subrange<I> shift_left(I first, S last, iter_difference_t<I> n);
template<forward_range R>
requires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R> shift_left(R&& r, range_difference_t<R> n);
}
template<class ForwardIter>
constexpr ForwardIter
shift_right(ForwardIter first, ForwardIter last,
typename iterator_traits<ForwardIter>::difference_type n);
template<class ExecutionPolicy, class ForwardIter>
ForwardIter
shift_right(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last,
typename iterator_traits<ForwardIter>::difference_type n);
namespace ranges {
template<permutable I, sentinel_for<I> S>
constexpr subrange<I> shift_right(I first, S last, iter_difference_t<I> n);
template<forward_range R>
requires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R> shift_right(R&& r, range_difference_t<R> n);
}
// sorting and related operations
// sorting
template<class RandomAccessIter>
constexpr void sort(RandomAccessIter first, RandomAccessIter last);
template<class RandomAccessIter, class Compare>
constexpr void sort(RandomAccessIter first, RandomAccessIter last, Compare comp);
template<class ExecutionPolicy, class RandomAccessIter>
void sort(ExecutionPolicy&& exec,
RandomAccessIter first, RandomAccessIter last);
template<class ExecutionPolicy, class RandomAccessIter, class Compare>
void sort(ExecutionPolicy&& exec,
RandomAccessIter first, RandomAccessIter last, Compare comp);
namespace ranges {
template<random_access_iterator I, sentinel_for<I> S,
class Comp = ranges::less, class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr I sort(I first, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R> sort(R&& r, Comp comp = {}, Proj proj = {});
}
template<class RandomAccessIter>
void stable_sort(RandomAccessIter first, RandomAccessIter last);
template<class RandomAccessIter, class Compare>
void stable_sort(RandomAccessIter first, RandomAccessIter last, Compare comp);
template<class ExecutionPolicy, class RandomAccessIter>
void stable_sort(ExecutionPolicy&& exec,
RandomAccessIter first, RandomAccessIter last);
template<class ExecutionPolicy, class RandomAccessIter, class Compare>
void stable_sort(ExecutionPolicy&& exec,
RandomAccessIter first, RandomAccessIter last, Compare comp);
namespace ranges {
template<random_access_iterator I, sentinel_for<I> S,
class Comp = ranges::less, class Proj = identity>
requires sortable<I, Comp, Proj>
I stable_sort(I first, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
borrowed_iterator_t<R> stable_sort(R&& r, Comp comp = {}, Proj proj = {});
}
template<class RandomAccessIter>
constexpr void partial_sort(RandomAccessIter first, RandomAccessIter middle,
RandomAccessIter last);
template<class RandomAccessIter, class Compare>
constexpr void partial_sort(RandomAccessIter first, RandomAccessIter middle,
RandomAccessIter last, Compare comp);
template<class ExecutionPolicy, class RandomAccessIter>
void partial_sort(ExecutionPolicy&& exec,
RandomAccessIter first, RandomAccessIter middle,
RandomAccessIter last);
template<class ExecutionPolicy, class RandomAccessIter, class Compare>
void partial_sort(ExecutionPolicy&& exec,
RandomAccessIter first, RandomAccessIter middle,
RandomAccessIter last, Compare comp);
namespace ranges {
template<random_access_iterator I, sentinel_for<I> S,
class Comp = ranges::less, class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr I
partial_sort(I first, I middle, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R>
partial_sort(R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});
}
template<class InputIter, class RandomAccessIter>
constexpr RandomAccessIter
partial_sort_copy(InputIter first, InputIter last,
RandomAccessIter result_first,
RandomAccessIter result_last);
template<class InputIter, class RandomAccessIter, class Compare>
constexpr RandomAccessIter
partial_sort_copy(InputIter first, InputIter last,
RandomAccessIter result_first,
RandomAccessIter result_last, Compare comp);
template<class ExecutionPolicy, class ForwardIter, class RandomAccessIter>
RandomAccessIter
partial_sort_copy(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last,
RandomAccessIter result_first,
RandomAccessIter result_last);
template<class ExecutionPolicy, class ForwardIter, class RandomAccessIter,
class Compare>
RandomAccessIter
partial_sort_copy(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last,
RandomAccessIter result_first,
RandomAccessIter result_last, Compare comp);
namespace ranges {
template<class I, class O>
using partial_sort_copy_result = in_out_result<I, O>;
template<input_iterator I1, sentinel_for<I1> S1,
random_access_iterator I2, sentinel_for<I2> S2,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires indirectly_copyable<I1, I2> && sortable<I2, Comp, Proj2> &&
indirect_strict_weak_order<Comp, projected<I1, Proj1>,
projected<I2, Proj2>>
constexpr partial_sort_copy_result<I1, I2>
partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, random_access_range R2, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_copyable<iterator_t<R1>, iterator_t<R2>> &&
sortable<iterator_t<R2>, Comp, Proj2> &&
indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
projected<iterator_t<R2>, Proj2>>
constexpr partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
}
template<class ForwardIter>
constexpr bool is_sorted(ForwardIter first, ForwardIter last);
template<class ForwardIter, class Compare>
constexpr bool is_sorted(ForwardIter first, ForwardIter last, Compare comp);
template<class ExecutionPolicy, class ForwardIter>
bool is_sorted(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last);
template<class ExecutionPolicy, class ForwardIter, class Compare>
bool is_sorted(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, Compare comp);
namespace ranges {
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
constexpr bool is_sorted(I first, S last, Comp comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_strict_weak_order
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr bool is_sorted(R&& r, Comp comp = {}, Proj proj = {});
}
template<class ForwardIter>
constexpr ForwardIter is_sorted_until(ForwardIter first, ForwardIter last);
template<class ForwardIter, class Compare>
constexpr ForwardIter is_sorted_until(ForwardIter first, ForwardIter last,
Compare comp);
template<class ExecutionPolicy, class ForwardIter>
ForwardIter is_sorted_until(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last);
template<class ExecutionPolicy, class ForwardIter, class Compare>
ForwardIter is_sorted_until(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last,
Compare comp);
namespace ranges {
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
constexpr I is_sorted_until(I first, S last, Comp comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_strict_weak_order
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr borrowed_iterator_t<R>
is_sorted_until(R&& r, Comp comp = {}, Proj proj = {});
}
// Nth element
template<class RandomAccessIter>
constexpr void nth_element(RandomAccessIter first, RandomAccessIter nth,
RandomAccessIter last);
template<class RandomAccessIter, class Compare>
constexpr void nth_element(RandomAccessIter first, RandomAccessIter nth,
RandomAccessIter last, Compare comp);
template<class ExecutionPolicy, class RandomAccessIter>
void nth_element(ExecutionPolicy&& exec,
RandomAccessIter first, RandomAccessIter nth,
RandomAccessIter last);
template<class ExecutionPolicy, class RandomAccessIter, class Compare>
void nth_element(ExecutionPolicy&& exec,
RandomAccessIter first, RandomAccessIter nth,
RandomAccessIter last, Compare comp);
namespace ranges {
template<random_access_iterator I, sentinel_for<I> S,
class Comp = ranges::less, class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr I
nth_element(I first, I nth, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R>
nth_element(R&& r, iterator_t<R> nth, Comp comp = {}, Proj proj = {});
}
// binary search
template<class ForwardIter, class T = typename iterator_traits<ForwardIter>::value_type>
constexpr ForwardIter lower_bound(ForwardIter first, ForwardIter last,
const T& value);
template<class ForwardIter, class T = typename iterator_traits<ForwardIter>::value_type,
class Compare>
constexpr ForwardIter lower_bound(ForwardIter first, ForwardIter last,
const T& value, Compare comp);
namespace ranges {
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>,
indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
constexpr I
lower_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>,
indirect_strict_weak_order
<const T*, projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr borrowed_iterator_t<R>
lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});
}
template<class ForwardIter, class T = typename iterator_traits<ForwardIter>::value_type>
constexpr ForwardIter upper_bound(ForwardIter first, ForwardIter last,
const T& value);
template<class ForwardIter, class T = typename iterator_traits<ForwardIter>::value_type,
class Compare>
constexpr ForwardIter upper_bound(ForwardIter first, ForwardIter last,
const T& value, Compare comp);
namespace ranges {
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>,
indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
constexpr I
upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {});
template<forward_range R, class T, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>,
indirect_strict_weak_order
<const T*, projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr borrowed_iterator_t<R>
upper_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});
}
template<class ForwardIter, class T = typename iterator_traits<ForwardIter>::value_type>
constexpr pair<ForwardIter, ForwardIter>
equal_range(ForwardIter first, ForwardIter last, const T& value);
template<class ForwardIter, class T = typename iterator_traits<ForwardIter>::value_type,
class Compare>
constexpr pair<ForwardIter, ForwardIter>
equal_range(ForwardIter first, ForwardIter last, const T& value, Compare comp);
namespace ranges {
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>,
indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
constexpr subrange<I>
equal_range(I first, S last, const T& value, Comp comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>,
indirect_strict_weak_order
<const T*, projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr borrowed_subrange_t<R>
equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {});
}
template<class ForwardIter, class T = typename iterator_traits<ForwardIter>::value_type>
constexpr bool binary_search(ForwardIter first, ForwardIter last,
const T& value);
template<class ForwardIter, class T = typename iterator_traits<ForwardIter>::value_type,
class Compare>
constexpr bool binary_search(ForwardIter first, ForwardIter last,
const T& value, Compare comp);
namespace ranges {
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>,
indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
constexpr bool binary_search(I first, S last, const T& value,
Comp comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>,
indirect_strict_weak_order
<const T*, projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr bool binary_search(R&& r, const T& value, Comp comp = {}, Proj proj = {});
}
// partitions
template<class InputIter, class Pred>
constexpr bool is_partitioned(InputIter first, InputIter last, Pred pred);
template<class ExecutionPolicy, class ForwardIter, class Pred>
bool is_partitioned(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, Pred pred);
namespace ranges {
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr bool is_partitioned(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr bool is_partitioned(R&& r, Pred pred, Proj proj = {});
}
template<class ForwardIter, class Pred>
constexpr ForwardIter partition(ForwardIter first, ForwardIter last, Pred pred);
template<class ExecutionPolicy, class ForwardIter, class Pred>
ForwardIter partition(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, Pred pred);
namespace ranges {
template<permutable I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr subrange<I> partition(I first, S last, Pred pred, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R> partition(R&& r, Pred pred, Proj proj = {});
}
template<class BidirectionalIter, class Pred>
BidirectionalIter stable_partition(BidirectionalIter first,
BidirectionalIter last, Pred pred);
template<class ExecutionPolicy, class BidirectionalIter, class Pred>
BidirectionalIter stable_partition(ExecutionPolicy&& exec,
BidirectionalIter first,
BidirectionalIter last, Pred pred);
namespace ranges {
template<bidirectional_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
requires permutable<I>
subrange<I> stable_partition(I first, S last, Pred pred, Proj proj = {});
template<bidirectional_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires permutable<iterator_t<R>>
borrowed_subrange_t<R> stable_partition(R&& r, Pred pred, Proj proj = {});
}
template<class InputIter, class OutputIter1,
class OutputIter2, class Pred>
constexpr pair<OutputIter1, OutputIter2>
partition_copy(InputIter first, InputIter last,
OutputIter1 out_true, OutputIter2 out_false, Pred pred);
template<class ExecutionPolicy, class ForwardIter, class ForwardIter1,
class ForwardIter2, class Pred>
pair<ForwardIter1, ForwardIter2>
partition_copy(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last,
ForwardIter1 out_true, ForwardIter2 out_false, Pred pred);
namespace ranges {
template<class I, class O1, class O2>
using partition_copy_result = in_out_out_result<I, O1, O2>;
template<input_iterator I, sentinel_for<I> S,
weakly_incrementable O1, weakly_incrementable O2,
class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
requires indirectly_copyable<I, O1> && indirectly_copyable<I, O2>
constexpr partition_copy_result<I, O1, O2>
partition_copy(I first, S last, O1 out_true, O2 out_false,
Pred pred, Proj proj = {});
template<input_range R, weakly_incrementable O1, weakly_incrementable O2,
class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires indirectly_copyable<iterator_t<R>, O1> &&
indirectly_copyable<iterator_t<R>, O2>
constexpr partition_copy_result<borrowed_iterator_t<R>, O1, O2>
partition_copy(R&& r, O1 out_true, O2 out_false, Pred pred, Proj proj = {});
}
template<class ForwardIter, class Pred>
constexpr ForwardIter
partition_point(ForwardIter first, ForwardIter last, Pred pred);
namespace ranges {
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr I partition_point(I first, S last, Pred pred, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr borrowed_iterator_t<R>
partition_point(R&& r, Pred pred, Proj proj = {});
}
// merge
template<class InputIter1, class InputIter2, class OutputIter>
constexpr OutputIter merge(InputIter1 first1, InputIter1 last1,
InputIter2 first2, InputIter2 last2, OutputIter result);
template<class InputIter1, class InputIter2, class OutputIter,
class Compare>
constexpr OutputIter merge(InputIter1 first1, InputIter1 last1,
InputIter2 first2, InputIter2 last2,
OutputIter result, Compare comp);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class ForwardIter>
ForwardIter merge(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2, ForwardIter result);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class ForwardIter, class Compare>
ForwardIter merge(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2,
ForwardIter result, Compare comp);
namespace ranges {
template<class I1, class I2, class O>
using merge_result = in_in_out_result<I1, I2, O>;
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2,
sentinel_for<I2> S2, weakly_incrementable O, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr merge_result<I1, I2, O>
merge(I1 first1, S1 last1, I2 first2, S2 last2, O result,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, weakly_incrementable O,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
constexpr merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
merge(R1&& r1, R2&& r2, O result,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
}
template<class BidirectionalIter>
void inplace_merge(BidirectionalIter first, BidirectionalIter middle,
BidirectionalIter last);
template<class BidirectionalIter, class Compare>
void inplace_merge(BidirectionalIter first, BidirectionalIter middle,
BidirectionalIter last, Compare comp);
template<class ExecutionPolicy, class BidirectionalIter>
void inplace_merge(ExecutionPolicy&& exec,
BidirectionalIter first, BidirectionalIter middle,
BidirectionalIter last);
template<class ExecutionPolicy, class BidirectionalIter, class Compare>
void inplace_merge(ExecutionPolicy&& exec,
BidirectionalIter first, BidirectionalIter middle,
BidirectionalIter last, Compare comp);
namespace ranges {
template<bidirectional_iterator I, sentinel_for<I> S,
class Comp = ranges::less, class Proj = identity>
requires sortable<I, Comp, Proj>
I inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {});
template<bidirectional_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
borrowed_iterator_t<R> inplace_merge(R&& r, iterator_t<R> middle,
Comp comp = {}, Proj proj = {});
}
// set operations
template<class InputIter1, class InputIter2>
constexpr bool includes(InputIter1 first1, InputIter1 last1,
InputIter2 first2, InputIter2 last2);
template<class InputIter1, class InputIter2, class Compare>
constexpr bool includes(InputIter1 first1, InputIter1 last1,
InputIter2 first2, InputIter2 last2, Compare comp);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2>
bool includes(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2, class Compare>
bool includes(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2, Compare comp);
namespace ranges {
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2,
sentinel_for<I2> S2, class Proj1 = identity, class Proj2 = identity,
indirect_strict_weak_order
<projected<I1, Proj1>, projected<I2, Proj2>> Comp = ranges::less>
constexpr bool includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2,
class Proj1 = identity, class Proj2 = identity,
indirect_strict_weak_order
<projected<iterator_t<R1>, Proj1>,
projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
constexpr bool includes(R1&& r1, R2&& r2, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
}
template<class InputIter1, class InputIter2, class OutputIter>
constexpr OutputIter set_union(InputIter1 first1, InputIter1 last1,
InputIter2 first2, InputIter2 last2,
OutputIter result);
template<class InputIter1, class InputIter2, class OutputIter, class Compare>
constexpr OutputIter set_union(InputIter1 first1, InputIter1 last1,
InputIter2 first2, InputIter2 last2,
OutputIter result, Compare comp);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class ForwardIter>
ForwardIter set_union(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2,
ForwardIter result);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class ForwardIter, class Compare>
ForwardIter set_union(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2,
ForwardIter result, Compare comp);
namespace ranges {
template<class I1, class I2, class O>
using set_union_result = in_in_out_result<I1, I2, O>;
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2,
sentinel_for<I2> S2, weakly_incrementable O, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr set_union_result<I1, I2, O>
set_union(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, weakly_incrementable O,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
constexpr set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
set_union(R1&& r1, R2&& r2, O result, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
}
template<class InputIter1, class InputIter2, class OutputIter>
constexpr OutputIter set_intersection(InputIter1 first1, InputIter1 last1,
InputIter2 first2, InputIter2 last2,
OutputIter result);
template<class InputIter1, class InputIter2, class OutputIter, class Compare>
constexpr OutputIter set_intersection(InputIter1 first1, InputIter1 last1,
InputIter2 first2, InputIter2 last2,
OutputIter result, Compare comp);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class ForwardIter>
ForwardIter set_intersection(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2,
ForwardIter result);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class ForwardIter, class Compare>
ForwardIter set_intersection(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2,
ForwardIter result, Compare comp);
namespace ranges {
template<class I1, class I2, class O>
using set_intersection_result = in_in_out_result<I1, I2, O>;
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2,
sentinel_for<I2> S2, weakly_incrementable O, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr set_intersection_result<I1, I2, O>
set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, weakly_incrementable O,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
constexpr set_intersection_result<borrowed_iterator_t<R1>,
borrowed_iterator_t<R2>, O>
set_intersection(R1&& r1, R2&& r2, O result,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
}
template<class InputIter1, class InputIter2, class OutputIter>
constexpr OutputIter set_difference(InputIter1 first1, InputIter1 last1,
InputIter2 first2, InputIter2 last2,
OutputIter result);
template<class InputIter1, class InputIter2, class OutputIter, class Compare>
constexpr OutputIter set_difference(InputIter1 first1, InputIter1 last1,
InputIter2 first2, InputIter2 last2,
OutputIter result, Compare comp);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class ForwardIter>
ForwardIter set_difference(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2,
ForwardIter result);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class ForwardIter, class Compare>
ForwardIter set_difference(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2,
ForwardIter result, Compare comp);
namespace ranges {
template<class I, class O>
using set_difference_result = in_out_result<I, O>;
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2,
sentinel_for<I2> S2, weakly_incrementable O, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr set_difference_result<I1, O>
set_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, weakly_incrementable O,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
constexpr set_difference_result<borrowed_iterator_t<R1>, O>
set_difference(R1&& r1, R2&& r2, O result,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
}
template<class InputIter1, class InputIter2, class OutputIter>
constexpr OutputIter set_symmetric_difference(InputIter1 first1, InputIter1 last1,
InputIter2 first2, InputIter2 last2,
OutputIter result);
template<class InputIter1, class InputIter2, class OutputIter, class Compare>
constexpr OutputIter set_symmetric_difference(InputIter1 first1, InputIter1 last1,
InputIter2 first2, InputIter2 last2,
OutputIter result, Compare comp);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class ForwardIter>
ForwardIter set_symmetric_difference(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2,
ForwardIter result);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class ForwardIter, class Compare>
ForwardIter set_symmetric_difference(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2,
ForwardIter result, Compare comp);
namespace ranges {
template<class I1, class I2, class O>
using set_symmetric_difference_result = in_in_out_result<I1, I2, O>;
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2,
sentinel_for<I2> S2, weakly_incrementable O, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr set_symmetric_difference_result<I1, I2, O>
set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, weakly_incrementable O,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
constexpr set_symmetric_difference_result<borrowed_iterator_t<R1>,
borrowed_iterator_t<R2>, O>
set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
}
// heap operations
template<class RandomAccessIter>
constexpr void push_heap(RandomAccessIter first, RandomAccessIter last);
template<class RandomAccessIter, class Compare>
constexpr void push_heap(RandomAccessIter first, RandomAccessIter last,
Compare comp);
namespace ranges {
template<random_access_iterator I, sentinel_for<I> S,
class Comp = ranges::less, class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr I push_heap(I first, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R> push_heap(R&& r, Comp comp = {}, Proj proj = {});
}
template<class RandomAccessIter>
constexpr void pop_heap(RandomAccessIter first, RandomAccessIter last);
template<class RandomAccessIter, class Compare>
constexpr void pop_heap(RandomAccessIter first, RandomAccessIter last,
Compare comp);
namespace ranges {
template<random_access_iterator I, sentinel_for<I> S,
class Comp = ranges::less, class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr I pop_heap(I first, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R> pop_heap(R&& r, Comp comp = {}, Proj proj = {});
}
template<class RandomAccessIter>
constexpr void make_heap(RandomAccessIter first, RandomAccessIter last);
template<class RandomAccessIter, class Compare>
constexpr void make_heap(RandomAccessIter first, RandomAccessIter last,
Compare comp);
namespace ranges {
template<random_access_iterator I, sentinel_for<I> S,
class Comp = ranges::less, class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr I make_heap(I first, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R> make_heap(R&& r, Comp comp = {}, Proj proj = {});
}
template<class RandomAccessIter>
constexpr void sort_heap(RandomAccessIter first, RandomAccessIter last);
template<class RandomAccessIter, class Compare>
constexpr void sort_heap(RandomAccessIter first, RandomAccessIter last,
Compare comp);
namespace ranges {
template<random_access_iterator I, sentinel_for<I> S,
class Comp = ranges::less, class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr I sort_heap(I first, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R> sort_heap(R&& r, Comp comp = {}, Proj proj = {});
}
template<class RandomAccessIter>
constexpr bool is_heap(RandomAccessIter first, RandomAccessIter last);
template<class RandomAccessIter, class Compare>
constexpr bool is_heap(RandomAccessIter first, RandomAccessIter last,
Compare comp);
template<class ExecutionPolicy, class RandomAccessIter>
bool is_heap(ExecutionPolicy&& exec,
RandomAccessIter first, RandomAccessIter last);
template<class ExecutionPolicy, class RandomAccessIter, class Compare>
bool is_heap(ExecutionPolicy&& exec,
RandomAccessIter first, RandomAccessIter last, Compare comp);
namespace ranges {
template<random_access_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
constexpr bool is_heap(I first, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Proj = identity,
indirect_strict_weak_order
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr bool is_heap(R&& r, Comp comp = {}, Proj proj = {});
}
template<class RandomAccessIter>
constexpr RandomAccessIter
is_heap_until(RandomAccessIter first, RandomAccessIter last);
template<class RandomAccessIter, class Compare>
constexpr RandomAccessIter
is_heap_until(RandomAccessIter first, RandomAccessIter last, Compare comp);
template<class ExecutionPolicy, class RandomAccessIter>
RandomAccessIter
is_heap_until(ExecutionPolicy&& exec,
RandomAccessIter first, RandomAccessIter last);
template<class ExecutionPolicy, class RandomAccessIter, class Compare>
RandomAccessIter
is_heap_until(ExecutionPolicy&& exec,
RandomAccessIter first, RandomAccessIter last, Compare comp);
namespace ranges {
template<random_access_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
constexpr I is_heap_until(I first, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Proj = identity,
indirect_strict_weak_order
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr borrowed_iterator_t<R>
is_heap_until(R&& r, Comp comp = {}, Proj proj = {});
}
// minimum and maximum
template<class T> constexpr const T& min(const T& a, const T& b);
template<class T, class Compare>
constexpr const T& min(const T& a, const T& b, Compare comp);
template<class T>
constexpr T min(initializer_list<T> t);
template<class T, class Compare>
constexpr T min(initializer_list<T> t, Compare comp);
namespace ranges {
template<class T, class Proj = identity,
indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
constexpr const T& min(const T& a, const T& b, Comp comp = {}, Proj proj = {});
template<copyable T, class Proj = identity,
indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
constexpr T min(initializer_list<T> r, Comp comp = {}, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_strict_weak_order
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
constexpr range_value_t<R> min(R&& r, Comp comp = {}, Proj proj = {});
}
template<class T> constexpr const T& max(const T& a, const T& b);
template<class T, class Compare>
constexpr const T& max(const T& a, const T& b, Compare comp);
template<class T>
constexpr T max(initializer_list<T> t);
template<class T, class Compare>
constexpr T max(initializer_list<T> t, Compare comp);
namespace ranges {
template<class T, class Proj = identity,
indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
constexpr const T& max(const T& a, const T& b, Comp comp = {}, Proj proj = {});
template<copyable T, class Proj = identity,
indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
constexpr T max(initializer_list<T> r, Comp comp = {}, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_strict_weak_order
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
constexpr range_value_t<R> max(R&& r, Comp comp = {}, Proj proj = {});
}
template<class T> constexpr pair<const T&, const T&> minmax(const T& a, const T& b);
template<class T, class Compare>
constexpr pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
template<class T>
constexpr pair<T, T> minmax(initializer_list<T> t);
template<class T, class Compare>
constexpr pair<T, T> minmax(initializer_list<T> t, Compare comp);
namespace ranges {
template<class T>
using minmax_result = min_max_result<T>;
template<class T, class Proj = identity,
indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
constexpr minmax_result<const T&>
minmax(const T& a, const T& b, Comp comp = {}, Proj proj = {});
template<copyable T, class Proj = identity,
indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
constexpr minmax_result<T>
minmax(initializer_list<T> r, Comp comp = {}, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_strict_weak_order
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
constexpr minmax_result<range_value_t<R>>
minmax(R&& r, Comp comp = {}, Proj proj = {});
}
template<class ForwardIter>
constexpr ForwardIter min_element(ForwardIter first, ForwardIter last);
template<class ForwardIter, class Compare>
constexpr ForwardIter min_element(ForwardIter first, ForwardIter last,
Compare comp);
template<class ExecutionPolicy, class ForwardIter>
ForwardIter min_element(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last);
template<class ExecutionPolicy, class ForwardIter, class Compare>
ForwardIter min_element(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last,
Compare comp);
namespace ranges {
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
constexpr I min_element(I first, S last, Comp comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_strict_weak_order
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr borrowed_iterator_t<R>
min_element(R&& r, Comp comp = {}, Proj proj = {});
}
template<class ForwardIter>
constexpr ForwardIter max_element(ForwardIter first, ForwardIter last);
template<class ForwardIter, class Compare>
constexpr ForwardIter max_element(ForwardIter first, ForwardIter last,
Compare comp);
template<class ExecutionPolicy, class ForwardIter>
ForwardIter max_element(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last);
template<class ExecutionPolicy, class ForwardIter, class Compare>
ForwardIter max_element(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last,
Compare comp);
namespace ranges {
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
constexpr I max_element(I first, S last, Comp comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_strict_weak_order
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr borrowed_iterator_t<R>
max_element(R&& r, Comp comp = {}, Proj proj = {});
}
template<class ForwardIter>
constexpr pair<ForwardIter, ForwardIter>
minmax_element(ForwardIter first, ForwardIter last);
template<class ForwardIter, class Compare>
constexpr pair<ForwardIter, ForwardIter>
minmax_element(ForwardIter first, ForwardIter last, Compare comp);
template<class ExecutionPolicy, class ForwardIter>
pair<ForwardIter, ForwardIter>
minmax_element(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last);
template<class ExecutionPolicy, class ForwardIter, class Compare>
pair<ForwardIter, ForwardIter>
minmax_element(ExecutionPolicy&& exec,
ForwardIter first, ForwardIter last, Compare comp);
namespace ranges {
template<class I>
using minmax_element_result = min_max_result<I>;
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
constexpr minmax_element_result<I>
minmax_element(I first, S last, Comp comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_strict_weak_order
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr minmax_element_result<borrowed_iterator_t<R>>
minmax_element(R&& r, Comp comp = {}, Proj proj = {});
}
// bounded value
template<class T>
constexpr const T& clamp(const T& v, const T& lo, const T& hi);
template<class T, class Compare>
constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp);
namespace ranges {
template<class T, class Proj = identity,
indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
constexpr const T&
clamp(const T& v, const T& lo, const T& hi, Comp comp = {}, Proj proj = {});
}
// lexicographical comparison
template<class InputIter1, class InputIter2>
constexpr bool lexicographical_compare(InputIter1 first1, InputIter1 last1,
InputIter2 first2, InputIter2 last2);
template<class InputIter1, class InputIter2, class Compare>
constexpr bool lexicographical_compare(InputIter1 first1, InputIter1 last1,
InputIter2 first2, InputIter2 last2,
Compare comp);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2>
bool lexicographical_compare(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2);
template<class ExecutionPolicy, class ForwardIter1, class ForwardIter2,
class Compare>
bool lexicographical_compare(ExecutionPolicy&& exec,
ForwardIter1 first1, ForwardIter1 last1,
ForwardIter2 first2, ForwardIter2 last2,
Compare comp);
namespace ranges {
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2,
sentinel_for<I2> S2, class Proj1 = identity, class Proj2 = identity,
indirect_strict_weak_order
<projected<I1, Proj1>, projected<I2, Proj2>> Comp = ranges::less>
constexpr bool
lexicographical_compare(I1 first1, S1 last1, I2 first2, S2 last2,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, class Proj1 = identity,
class Proj2 = identity,
indirect_strict_weak_order
<projected<iterator_t<R1>, Proj1>,
projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
constexpr bool
lexicographical_compare(R1&& r1, R2&& r2, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
}
// three-way comparison algorithms
template<class InputIter1, class InputIter2, class Cmp>
constexpr auto lexicographical_compare_three_way(InputIter1 b1, InputIter1 e1,
InputIter2 b2, InputIter2 e2,
Cmp comp)
-> decltype(comp(*b1, *b2));
template<class InputIter1, class InputIter2>
constexpr auto lexicographical_compare_three_way(InputIter1 b1, InputIter1 e1,
InputIter2 b2, InputIter2 e2);
// permutations
template<class BidirectionalIter>
constexpr bool next_permutation(BidirectionalIter first,
BidirectionalIter last);
template<class BidirectionalIter, class Compare>
constexpr bool next_permutation(BidirectionalIter first,
BidirectionalIter last, Compare comp);
namespace ranges {
template<class I>
using next_permutation_result = in_found_result<I>;
template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr next_permutation_result<I>
next_permutation(I first, S last, Comp comp = {}, Proj proj = {});
template<bidirectional_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr next_permutation_result<borrowed_iterator_t<R>>
next_permutation(R&& r, Comp comp = {}, Proj proj = {});
}
template<class BidirectionalIter>
constexpr bool prev_permutation(BidirectionalIter first,
BidirectionalIter last);
template<class BidirectionalIter, class Compare>
constexpr bool prev_permutation(BidirectionalIter first,
BidirectionalIter last, Compare comp);
namespace ranges {
template<class I>
using prev_permutation_result = in_found_result<I>;
template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr prev_permutation_result<I>
prev_permutation(I first, S last, Comp comp = {}, Proj proj = {});
template<bidirectional_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr prev_permutation_result<borrowed_iterator_t<R>>
prev_permutation(R&& r, Comp comp = {}, Proj proj = {});
}
}
类模板 std::ranges::in_fun_result
namespace std::ranges {
template<class I, class F>
struct in_fun_result {
[[no_unique_address]] I in;
[[no_unique_address]] F fun;
template<class I2, class F2>
requires convertible_to<const I&, I2> && convertible_to<const F&, F2>
constexpr operator in_fun_result<I2, F2>() const & {
return {in, fun};
}
template<class I2, class F2>
requires convertible_to<I, I2> && convertible_to<F, F2>
constexpr operator in_fun_result<I2, F2>() && {
return {std::move(in), std::move(fun)};
}
};
}
类模板 std::ranges::in_in_result
namespace std::ranges {
template<class I1, class I2>
struct in_in_result {
[[no_unique_address]] I1 in1;
[[no_unique_address]] I2 in2;
template<class II1, class II2>
requires convertible_to<const I1&, II1> && convertible_to<const I2&, II2>
constexpr operator in_in_result<II1, II2>() const & {
return {in1, in2};
}
template<class II1, class II2>
requires convertible_to<I1, II1> && convertible_to<I2, II2>
constexpr operator in_in_result<II1, II2>() && {
return {std::move(in1), std::move(in2)};
}
};
}
类模板 std::ranges::in_out_result
namespace std::ranges {
template<class I, class O>
struct in_out_result {
[[no_unique_address]] I in;
[[no_unique_address]] O out;
template<class I2, class O2>
requires convertible_to<const I&, I2> && convertible_to<const O&, O2>
constexpr operator in_out_result<I2, O2>() const & {
return {in, out};
}
template<class I2, class O2>
requires convertible_to<I, I2> && convertible_to<O, O2>
constexpr operator in_out_result<I2, O2>() && {
return {std::move(in), std::move(out)};
}
};
}
类模板 std::ranges::in_in_out_result
namespace std::ranges {
template<class I1, class I2, class O>
struct in_in_out_result {
[[no_unique_address]] I1 in1;
[[no_unique_address]] I2 in2;
[[no_unique_address]] O out;
template<class II1, class II2, class OO>
requires convertible_to<const I1&, II1> &&
convertible_to<const I2&, II2> &&
convertible_to<const O&, OO>
constexpr operator in_in_out_result<II1, II2, OO>() const & {
return {in1, in2, out};
}
template<class II1, class II2, class OO>
requires convertible_to<I1, II1> &&
convertible_to<I2, II2> &&
convertible_to<O, OO>
constexpr operator in_in_out_result<II1, II2, OO>() && {
return {std::move(in1), std::move(in2), std::move(out)};
}
};
}
类模板 std::ranges::in_out_out_result
namespace std::ranges {
template<class I, class O1, class O2>
struct in_out_out_result {
[[no_unique_address]] I in;
[[no_unique_address]] O1 out1;
[[no_unique_address]] O2 out2;
template<class II, class OO1, class OO2>
requires convertible_to<const I&, II> &&
convertible_to<const O1&, OO1> &&
convertible_to<const O2&, OO2>
constexpr operator in_out_out_result<II, OO1, OO2>() const & {
return {in, out1, out2};
}
template<class II, class OO1, class OO2>
requires convertible_to<I, II> &&
convertible_to<O1, OO1> &&
convertible_to<O2, OO2>
constexpr operator in_out_out_result<II, OO1, OO2>() && {
return {std::move(in), std::move(out1), std::move(out2)};
}
};
}
类模板 std::ranges::min_max_result
namespace std::ranges {
template<class T>
struct min_max_result {
[[no_unique_address]] T min;
[[no_unique_address]] T max;
template<class T2>
requires convertible_to<const T&, T2>
constexpr operator min_max_result<T2>() const & {
return {min, max};
}
template<class T2>
requires convertible_to<T, T2>
constexpr operator min_max_result<T2>() && {
return {std::move(min), std::move(max)};
}
};
}
类模板 std::ranges::in_found_result
namespace std::ranges {
template<class I>
struct in_found_result {
[[no_unique_address]] I in;
bool found;
template<class I2>
requires convertible_to<const I&, I2>
constexpr operator in_found_result<I2>() const & {
return {in, found};
}
template<class I2>
requires convertible_to<I, I2>
constexpr operator in_found_result<I2>() && {
return {std::move(in), found};
}
};
}
类模板 std::ranges::in_value_result
namespace std::ranges {
template<class I, class T>
struct in_value_result {
[[no_unique_address]] I in;
[[no_unique_address]] T value;
template<class I2, class T2>
requires convertible_to<const I&, I2> && convertible_to<const T&, T2>
constexpr operator in_value_result<I2, T2>() const & {
return {in, value};
}
template<class I2, class T2>
requires convertible_to<I, I2> && convertible_to<T, T2>
constexpr operator in_value_result<I2, T2>() && {
return {std::move(in), std::move(value)};
}
};
}
类模板 std::ranges::out_value_result
namespace std::ranges {
template<class O, class T>
struct out_value_result {
[[no_unique_address]] O out;
[[no_unique_address]] T value;
template<class O2, class T2>
requires convertible_to<const O&, O2> && convertible_to<const T&, T2>
constexpr operator out_value_result<O2, T2>() const & {
return {out, value};
}
template<class O2, class T2>
requires convertible_to<O, O2> && convertible_to<T, T2>
constexpr operator out_value_result<O2, T2>() && {
return {std::move(out), std::move(value)};
}
};
}
C++ 标准库头文件
此头文件是 numeric 库的一部分。
函数
iota
(C++11)
用起始值的连续增量填充一个范围
(函数模板)
ranges::iota
(C++23)
用起始值的连续增量填充一个范围
(算法函数对象)
accumulate
对元素范围求和或折叠
(函数模板)
reduce
(C++17)
类似于 std::accumulate，但顺序不定
(函数模板)
transform_reduce
(C++17)
应用一个可调用对象，然后以无序方式归约
(函数模板)
inner_product
计算两个元素范围的内积
(函数模板)
adjacent_difference
计算范围内相邻元素之间的差值
(函数模板)
partial_sum
计算元素范围的部分和
(函数模板)
inclusive_scan
(C++17)
类似于 std::partial_sum，在第 ith 个和中包含第 ith 个输入元素
(函数模板)
exclusive_scan
(C++17)
类似于 std::partial_sum，在第 ith 个和中排除第 ith 个输入元素
(函数模板)
transform_inclusive_scan
(C++17)
应用一个可调用对象，然后计算包含扫描
(函数模板)
transform_exclusive_scan
(C++17)
应用一个可调用对象，然后计算排除扫描
(函数模板)
gcd
(C++17)
计算两个整数的最大公约数
(函数模板)
lcm
(C++17)
计算两个整数的最小公倍数
(函数模板)
midpoint
(C++20)
两个数字或指针之间的中点
(函数模板)
add_sat
(C++26)
两个整数的饱和加法运算
(函数模板)
sub_sat
(C++26)
两个整数的饱和减法运算
(函数模板)
mul_sat
(C++26)
两个整数的饱和乘法运算
(函数模板)
div_sat
(C++26)
两个整数的饱和除法运算
(函数模板)
saturate_cast
(C++26)
返回一个整数值，该值被钳制到另一种整数类型的范围内
(函数模板)
概要
namespace std {
// accumulate
template<class InputIt, class T>
constexpr T accumulate(InputIt first, InputIt last, T init);
template<class InputIt, class T, class BinaryOperation>
constexpr T accumulate(InputIt first, InputIt last, T init, BinaryOperation binary_op);
// reduce
template<class InputIt>
constexpr typename iterator_traits<InputIt>::value_type
reduce(InputIt first, InputIt last);
template<class InputIt, class T>
constexpr T reduce(InputIt first, InputIt last, T init);
template<class InputIt, class T, class BinaryOperation>
constexpr T reduce(InputIt first, InputIt last, T init, BinaryOperation binary_op);
template<class ExecutionPolicy, class ForwardIt>
typename iterator_traits<ForwardIt>::value_type
reduce(ExecutionPolicy&& exec,
ForwardIt first, ForwardIt last);
template<class ExecutionPolicy, class ForwardIt, class T>
T reduce(ExecutionPolicy&& exec,
ForwardIt first, ForwardIt last, T init);
template<class ExecutionPolicy, class ForwardIt, class T, class BinaryOperation>
T reduce(ExecutionPolicy&& exec,
ForwardIt first, ForwardIt last, T init, BinaryOperation binary_op);
// inner product
template<class InputIt1, class InputIt2, class T>
constexpr T inner_product(InputIt1 first1, InputIt1 last1,
InputIt2 first2, T init);
template<class InputIt1, class InputIt2, class T,
class BinaryOperation1, class BinaryOperation2>
constexpr T inner_product(InputIt1 first1, InputIt1 last1,
InputIt2 first2, T init,
BinaryOperation1 binary_op1,
BinaryOperation2 binary_op2);
// transform reduce
template<class InputIt1, class InputIt2, class T>
constexpr T transform_reduce(InputIt1 first1, InputIt1 last1,
InputIt2 first2,
T init);
template<class InputIt1, class InputIt2, class T,
class BinaryOperation1, class BinaryOperation2>
constexpr T transform_reduce(InputIt1 first1, InputIt1 last1,
InputIt2 first2,
T init,
BinaryOperation1 binary_op1,
BinaryOperation2 binary_op2);
template<class InputIt, class T,
class BinaryOperation, class UnaryOperation>
constexpr T transform_reduce(InputIt first, InputIt last,
T init,
BinaryOperation binary_op, UnaryOperation unary_op);
template<class ExecutionPolicy,
class ForwardIt1, class ForwardIt2, class T>
T transform_reduce(ExecutionPolicy&& exec,
ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2,
T init);
template<class ExecutionPolicy,
class ForwardIt1, class ForwardIt2, class T,
class BinaryOperation1, class BinaryOperation2>
T transform_reduce(ExecutionPolicy&& exec,
ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2,
T init,
BinaryOperation1 binary_op1,
BinaryOperation2 binary_op2);
template<class ExecutionPolicy,
class ForwardIt, class T,
class BinaryOperation, class UnaryOperation>
T transform_reduce(ExecutionPolicy&& exec,
ForwardIt first, ForwardIt last,
T init,
BinaryOperation binary_op, UnaryOperation unary_op);
// partial sum
template<class InputIt, class OutputIt>
constexpr OutputIt partial_sum(InputIt first,
InputIt last,
OutputIt result);
template<class InputIt, class OutputIt, class BinaryOperation>
constexpr OutputIt partial_sum(InputIt first,
InputIt last,
OutputIt result,
BinaryOperation binary_op);
// exclusive scan
template<class InputIt, class OutputIt, class T>
constexpr OutputIt exclusive_scan(InputIt first, InputIt last,
OutputIt result,
T init);
template<class InputIt, class OutputIt, class T, class BinaryOperation>
constexpr OutputIt exclusive_scan(InputIt first, InputIt last,
OutputIt result,
T init, BinaryOperation binary_op);
template<class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T>
ForwardIt2 exclusive_scan(ExecutionPolicy&& exec,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 result,
T init);
template<class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T,
class BinaryOperation>
ForwardIt2 exclusive_scan(ExecutionPolicy&& exec,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 result,
T init, BinaryOperation binary_op);
// inclusive scan
template<class InputIt, class OutputIt>
constexpr OutputIt inclusive_scan(InputIt first, InputIt last, OutputIt result);
template<class InputIt, class OutputIt, class BinaryOperation>
constexpr OutputIt inclusive_scan(InputIt first, InputIt last,
OutputIt result,
BinaryOperation binary_op);
template<class InputIt, class OutputIt, class BinaryOperation, class T>
constexpr OutputIt inclusive_scan(InputIt first, InputIt last,
OutputIt result,
BinaryOperation binary_op, T init);
template<class ExecutionPolicy, class ForwardIt1, class ForwardIt2>
ForwardIt2 inclusive_scan(ExecutionPolicy&& exec,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 result);
template<class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
class BinaryOperation>
ForwardIt2 inclusive_scan(ExecutionPolicy&& exec,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 result,
BinaryOperation binary_op);
template<class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
class BinaryOperation, class T>
ForwardIt2 inclusive_scan(ExecutionPolicy&& exec,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 result,
BinaryOperation binary_op, T init);
// transform exclusive scan
template<class InputIt, class OutputIt, class T,
class BinaryOperation, class UnaryOperation>
constexpr OutputIt transform_exclusive_scan(InputIt first, InputIt last,
OutputIt result,
T init,
BinaryOperation binary_op,
UnaryOperation unary_op);
template<class ExecutionPolicy,
class ForwardIt1, class ForwardIt2, class T,
class BinaryOperation, class UnaryOperation>
ForwardIt2 transform_exclusive_scan(ExecutionPolicy&& exec,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 result,
T init,
BinaryOperation binary_op,
UnaryOperation unary_op);
// transform inclusive scan
template<class InputIt, class OutputIt,
class BinaryOperation, class UnaryOperation>
constexpr OutputIt transform_inclusive_scan(InputIt first, InputIt last,
OutputIt result,
BinaryOperation binary_op,
UnaryOperation unary_op);
template<class InputIt, class OutputIt,
class BinaryOperation, class UnaryOperation, class T>
constexpr OutputIt transform_inclusive_scan(InputIt first, InputIt last,
OutputIt result,
BinaryOperation binary_op,
UnaryOperation unary_op,
T init);
template<class ExecutionPolicy,
class ForwardIt1, class ForwardIt2,
class BinaryOperation, class UnaryOperation>
ForwardIt2 transform_inclusive_scan(ExecutionPolicy&& exec,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 result,
BinaryOperation binary_op,
UnaryOperation unary_op);
template<class ExecutionPolicy,
class ForwardIt1, class ForwardIt2,
class BinaryOperation, class UnaryOperation, class T>
ForwardIt2 transform_inclusive_scan(ExecutionPolicy&& exec,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 result,
BinaryOperation binary_op,
UnaryOperation unary_op,
T init);
// adjacent difference
template<class InputIt, class OutputIt>
constexpr OutputIt adjacent_difference(InputIt first, InputIt last,
OutputIt result);
template<class InputIt, class OutputIt, class BinaryOperation>
constexpr OutputIt adjacent_difference(InputIt first, InputIt last,
OutputIt result,
BinaryOperation binary_op);
template<class ExecutionPolicy, class ForwardIt1, class ForwardIt2>
ForwardIt2 adjacent_difference(ExecutionPolicy&& exec,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 result);
template<class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
class BinaryOperation>
ForwardIt2 adjacent_difference(ExecutionPolicy&& exec,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 result,
BinaryOperation binary_op);
// iota
template<class ForwardIt, class T>
constexpr void iota(ForwardIt first, ForwardIt last, T value);
namespace ranges {
template<class O, class T>
using iota_result = out_value_result<O, T>;
template<input_or_output_iterator O, sentinel_for<O> S, weakly_incrementable T>
requires indirectly_writable<O, const T&>
constexpr iota_result<O, T> iota(O first, S last, T value);
template<weakly_incrementable T, output_range<const T&> R>
constexpr iota_result<borrowed_iterator_t<R>, T> iota(R&& r, T value);
}
// greatest common divisor
template<class M, class N>
constexpr common_type_t<M, N> gcd(M m, N n);
// least common multiple
template<class M, class N>
constexpr common_type_t<M, N> lcm(M m, N n);
// midpoint
template<class T>
constexpr T midpoint(T a, T b) noexcept;
template<class T>
constexpr T* midpoint(T* a, T* b);
// saturation arithmetic
template<class T>
constexpr T add_sat(T x, T y) noexcept; // freestanding
template<class T>
constexpr T sub_sat(T x, T y) noexcept; // freestanding
template<class T>
constexpr T mul_sat(T x, T y) noexcept; // freestanding
template<class T>
constexpr T div_sat(T x, T y) noexcept; // freestanding
template<class T, class U>
constexpr T saturate_cast(U x) noexcept; // freestanding
}
鲁ICP备2025150228号