欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

STL使用方法

程序员文章站 2022-04-23 07:52:18
...

\(STL\)使用方法

前置知识

如果您已学习高一数学必修1,请自动忽略此内容

首先
区间\([l,r]\),表示从\(l\)\(r\)的所有数据,包括\(l\)\(r\)
区间\([l,r)\),表示从\(l\)\(r\)的所有数据,不包括\(r\)
区间\((l,r)\),表示从\(l\)\(r\)的所有数据,不包括\(l\)\(r\)

容器类

对于容器类的\(STL\),因为在\(C++\)中容器中统一使用迭代器来表示数据位置,所以你需要先记住这个代码:

容器类型<定义容器的方式>::iterator 变量名

在容器中迭代器类型的变量只能用++,--操作,另外暴力遍历一个容器一般是\(O(n)\)的,所以一般使用容器中的自带函数比较多一些。

vector在#include<vector>using namesapce std;

vector相当于一个数组,只不过是不定长的,不用定义大小,也就是你可以在任意时刻插入,所用空间只取决于你存储数据的大小,不过vector常数特别大,一般能别用就不用。

定义:

vector<数据类型>名称;
二维:
vector<数据类型>名称[第二维大小];

一些自带函数:

v.front();返回vector中第一个数据(值)

v.back();返回vector中最后一个数据(值)

v.at(x);返回vector中第x+1个数据(值)(因为vector从0开始存储,所以是第x+1个数据,如果没有数据会RE)

v.push_back(x);在vector最后插入x。一般情况下可认为\(O(1)\)

v.pop_back();弹出最后一个元素。\(O(1)\)

v.begin();开始位置

v.end();结束位置+1

v.clear();清空vector

v.empty();判断vector是否为空,如果为空返回1,否则返回0

v.insert(迭代器,x);在迭代器的位置插入x

v.erase(开始位置(迭代器),结束位置(迭代器));删除\([begin,end)\)(如果需要\(end\)包括需要+1)的数据(vector的迭代器相当于数组下标,支持加减操作)

如何快速取得在数组中第x个数的迭代器v.begin()+x;

遍历(访问)方式1:迭代器

    for (vector<int>::iterator it=v.begin();it!=v.end();it++)
    printf("%d ",*it);

遍历(访问)方式2:下标

    for (int i=0;i<(int)v.size();i++)
    printf("%d ",v[i]);

需要注意的是vector默认从0开始存储。

算法类

二分查找 lower_boundupper_bound

lower_bound#include<cstdio>using namespace std;

upper_bound#include<algorithm>

对单调线性数据进行查找 (默认数据从小到大)

数组:

lower_bound(区间开始位置,区间开始结束位置,key)\([begin,end)\)(如果需要\(end\)包括需要+1)

lower_bound返回最后一个不比key元素小的元素的位置(迭代器)。也就是说,区间里有key元素就返回第一个key元素的位置,如果没有key元素就返回小于key元素的最后一个最大元素的位置。

upper_bound(区间开始位置,区间开始结束位置,key)\([begin,end)\)(如果需要\(end\)包括需要+1)

upper_bound返回第一个比key元素大的元素的位置(迭代器)。也就是说,不管区间有没有key元素都会返回第一个比key元素大的元素的位置。

STL容器

lower_bound(名称.begin(),名称.end(),key)

upper_bound(名称.begin(),名称.end(),key)

因为是迭代器,所以想要输出数据时要加*

如果想要输出在区间里的位置(第几个)upper_bound(区间开始位置,区间开始结束位置,,key)-数组名称(或者容器.begin())

如果区间里没有满足条件的元素,就返回最后一个数据后面的位置。(在STL容器中就是end

时间复杂度:\(log_2(n)\)

#include<algorithm>
#include<cstdio>
using namespace std;
const int N=1e5+100;
int n,m;
int a[N];
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    scanf("%d",a+i);
    sort(a+1,a+n+1);
    for (int i=1;i<=m;i++)
    {
        int x;
        scanf("%d",&x);
        printf("lower_bound返回元素:");
        printf("%d\n",*lower_bound(a+1,a+n+1,x));
        printf("lower_bound返回元素在序列中位置:");
        printf("%d\n",lower_bound(a+1,a+n+1,x)-a);
        printf("upper_bound返回元素:");
        printf("%d\n",*upper_bound(a+1,a+n+1,x));
        printf("upper_bound返回元素在序列中位置:");
        printf("%d\n",upper_bound(a+1,a+n+1,x)-a);
    }
    return 0;
}

结果:
STL使用方法