7.15 暑假集训(上) – STL

7.15 暑假集训(上) – STL

本人太菜了,STL就作为大家新生训练和暑假集训的衔接吧~~~~会的话可以略过qwq

一.前言 – 什么是STL?

标准模板库(英文:Standard Template Library,缩写:STL),是一个C++软件库,大量影响了C++标准程序库但并非是其的一部分。

其中包含4个组件,分别为算法、容器、函数、迭代器

由于acm中使用的很少,咱们就只介绍一些容器,其他的大家可以去了解。

STl简介

acm中主要是如何使用!!!

二.STL – 容器

1.顺序容器

首先思考一下啥是顺序容器???

顺序容器故名思意就是 元素加入容器的顺序决定了其在容器中的位置。

1)vector – 不定长数组

从最简单的vector的来说,vector是可变长数组,咱们和普通数组做一个对比

#include <bits/stdc++.h>
using namespace std;

int main(){
    int arr[] = {1, 2, 3};
    int a[2] = {1, 2};
    
    vector<int > v = {1, 2, 3, 4};

    v.push_back(666);

    return 0;
}

这个地方大家可能有两个地方不懂,第一个是vector的定义为什么那么写,为什么后面能用{}直接初始化,以及大家还不知道push_back是什么意思,不要慌(滑稽)~

首先说一下定义,暂时不用知道为什么,先记住

vector<type> name:定义一个存储type类型的不定长数组
C++11标准中支持 直接通过 = {1, 2, 3,}这样的方式初始化(先记住)

push_back()是vector容器支持的一个操作,为什么是v.呢?这个之前大家学过类就知道了,其实vector是一个内置类(这个地方说的不准确,其实是类模板),不过大家可以先理解为vector是一个内置的类,然后那就是 通过成员运算符“.”来访问其中的成员函数了(Java中学过的就不多说啦),其中就有push_back(),功能是在vector容器的后面加入一个元素,我们来输出一个上面通过push_back操作后的vector数组

嗯???咋输出???我只知道数组是从0开始 然后巴拉巴拉的输出,vector是啥子????

还记得咱们在上面说到的vector和数组吗?其实vector和数组一样都是顺序存储的,所以vector同样支持数组的下标运算符[],就像数组一样,同样是从0开始存储的,哈哈,这个时候咱们就可以这样写出来了。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int arr[] = {1, 2, 3};
    int a[2] = {1, 2};
    
    vector<int > v = {1, 2, 3, 4};

    v.push_back(666);

    for(int i = 0;i < 5;++i){
        cout << v[i] << " ";
    }
    cout << endl;

    return 0;
}
// 1 2 3 4 666

然后运行出来就是1 2 3 4 666,这时候大家学会了

  • vector的定义方法
  • vector的一种初始化方法(C++11)
  • push_back()操作
  • 和数组类似的输出方法(支持下表运算符)

那么有push_back()操作,有没有在前面插入元素的方法呢?

很可惜,vector没有在前面插入元素的方法(为什么到后面再说,其实是可以的,如何操作,这个可能咱们不讲,有兴趣的同学可以查一下泛型算法insert)

好的,之后咱们再学习两个东西,默认初始化和size()成员函数

先看size()成员函数,很简单,就是返回当前有效长度(为什么说是有效长度呢?之后会说),有效长度简单的说就是目前容器中存储了几个元素

我们再看看上面的那个例子:

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int > v = {1, 2, 3, 4};

    cout << v.size() << endl;
   
    v.push_back(666);
    
    cout << v.size() << endl;

    return 0;
}
// 4
// 5

哇!这个时候有没有感觉很开心?大家想一想我们之前是如何遍历vector的??

虽然大家可能不愿意承认,但是你肯定是这样做的:

  • 数一下{}里面有几个
  • 然后写for循环

如果{}里面有很多个数字,那岂不是很麻烦~~~~

当咱们学习了size()之后,想要遍历整个vector就会很简单(其实还有更简单的,参考泛型算法begin / end or 范围for循环 or 迭代器)

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int > v = {1, 2, 3, 4};

    cout << v.size() << endl;
   
    v.push_back(666);
    
    cout << v.size() << endl;

    for(int i = 0;i < v.size();++i){
        cout << v[i] << " ";
    }
    cout << endl;

    return 0;
}
// 4
// 5
// 1 2 3 4 666

默认初始化(这个地方提一下,初始化和赋值是完全不一样的东西,一定要理解这个)比较简单,举个例子:

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int > v;

    cout << v.size() << endl;

    return 0;
}
// 0

默认初始化的方法就是空的容器(感觉是废话qwq,其实不是,后面大家就会知道了)

然后vector容器总不能一直push_back把,岂不是要吃撑???撑死??

那我们可爱的vector肯定不会这样的,vector为了保持身材,又学会了一项技能,就是pop_back(),它的功能就是减肥,故名思意就是将最后一个元素取出来扔掉,我们来看一段代码:

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int > v = {1, 2, 3, 4, 5};

    // print vector - v
    for(int i = 0;i < v.size();++i){
        cout << v[i] << " ";
    }
    cout << endl;

    // 可爱的vector要减肥!!!!!
    v.pop_back();

    // print vector - v
    for(int i = 0;i < v.size();++i){
        cout << v[i] << " ";
    }
    cout << endl;

    return 0;
}
// 1 2 3 4 5
// 1 2 3 4

同样的,不支持pop_front()操作~~~~~

总结一下咱们学到了啥

  • vector的定义方法
  • vector的一种初始化方法(C++11)
  • push_back()操作
  • 和数组类似的遍历方法(支持下表运算符)
  • size()操作
  • 使用size()操作更加方便地遍历vector
  • 默认初始化方法(空容器)
  • pop_back()减肥!!

acm中会使用的大致就是这些了,对于迭代器和范围for循环如果想了解的话,可以查一下,PS:迭代器会很好用的

2)deque – 双端队列

这个也是顺序容器,有同学会疑惑为什么不讲queue呢?这个其实不属于顺序容器,后面会细致的说

vector讲完了,这个就很好理解了,就简单的说一下

双端队列故名思意就是 排了个队伍,然后只能从两端进出

定义的格式:

deque<type > dq

支持默认初始化 和 直接赋值初始化(C++11):

 deque<int > dq1;
 deque<int > dq2 = {1, 2, 3, 4};

size()操作

#include <bits/stdc++.h>
using namespace std;

int main(){
    deque<int > dq = {1, 2, 3, 4};
    cout << dq.size() << endl;

    return 0;
}
// 4

支持下表运算符

#include <bits/stdc++.h>
using namespace std;

int main(){
    deque<int > dq = {1, 2, 3, 4};

    cout << dq[0] << endl;

    return 0;
}
// 1

入队(前面和后面):push_back,push_front

#include <bits/stdc++.h>
using namespace std;

int main(){
    deque<int > dq = {1, 2, 3, 4};
    
    dq.push_back(5);
    dq.push_front(0);

    for(int i = 0;i < dq.size();++i){
        cout << dq[i] << " ";
    }
    cout << endl;

    return 0;
}
// 0 1 2 3 4 5

出队(前面和后面):pop_back(),pop_front()

#include <bits/stdc++.h>
using namespace std;

int main(){
    deque<int > dq = {1, 2, 3, 4};
    
    dq.pop_back();
    dq.pop_front();
  
    for(int i = 0;i < dq.size();++i){
        cout << dq[i] << " ";
    }
    cout << endl;

    return 0;
}
// 2 3

总结一下acm中的常用操作:

  • 默认初始化(空容器)
  • 直接赋值初始化(C++11)
  • size()操作
  • 出队(前pop_front(),后pop_back())
  • 入队(前push_front(),后push_back())

3)string – 字符串

string和vector类似,区别在于string专门用于保存字符

初始化:

初始化也介绍两种,第一种是默认初始化,初始化得到有个空串,另外一种初始化是string特有的,string支持将字符串常量直接赋值初始化(隐式转换)

#include <bits/stdc++.h>
using namespace std;

int main(){
    // 默认初始化
    string str1;
    cout << str1 << endl;

    // 隐式转换
    string str2 = "123";
    cout << str2 << endl;

    return 0;
}
// 
// 123

PS:直接string初始化那肯定也是可以的啦~

size()操作:

同样的,获取string的有效长度

#include <bits/stdc++.h>
using namespace std;

int main(){
    string str = "123";
    cout << str.size() << endl;
    
    return 0;
}
// 3

支持下标运算符

#include <bits/stdc++.h>
using namespace std;

int main(){
    string str = "123";
    cout << str[0] << endl;

    for(int i = 0;i < str.size();++i){
        cout << str[i] << " ";
    }
    cout << endl;

    return 0;
}
// 1
// 1 2 3

push_back() 以及 等价操作(重载 + 号)

string和vector一样,支持push_back(),不支持push_front()

#include <bits/stdc++.h>
using namespace std;

int main(){
    string str = "123";
    
    str.push_back('4');
    
    cout << str << endl;

    return 0;
}
// 1234

PS:push_back操作需要一个元素类型(或能够隐式转换成元素类型)的元素,string需要一个char类型

大家学习了Java,知道函数重载,而string使用了运算符重载,运算符重载是啥呢?和函数重载一样,先想一下函数重载是什么?函数重载是对于同样标识符的函数对于不同形式参数表,都能存在,在调用的时候会进行函数匹配操作。而运算符重载就是重载了运算符(比如>, = , < 等等),理解成 使得这些符号能够有不同的功能。暂时理解为能够使得运算符具有其他不同的功能即可。

string重载了 = 号,支持的常用操作有:

string1 + string2 :string1后面接上string2

#include <bits/stdc++.h>
using namespace std;

int main(){
    string str1 = "123", str2 = "456";
    cout << str1 + str2 << endl;

    return 0;
}
// 123456

同样,支持隐式转换:常见 的有字符串常量:

#include <bits/stdc++.h>
using namespace std;

int main(){
    string str = "123";
    cout << str + "456" << endl;
    cout << str + string("456") << endl;

    return 0;
}
// 123456
// 123456

这个地方会有个小错误,犯错概率比较小,但是还是说一下吧:

下面的输出是什么???

#include <bits/stdc++.h>
using namespace std;

int main(){
    string str1 = "0";
    cout << str1 + "123" + "456" << endl;

    string str2 = "7";
    cout << "123" + "456" + str2 << endl; 

    return 0;
}

有些同学会认为这个输出就是 0123456 下一行是 1234567

其实不是,第一个是0123456,但是第二个会报错,因为字符串常量是不能相加的,这个程序等价于你在做这个操作(复习一下c语言):

#include <bits/stdc++.h>
using namespace std;

int main(){
    int a = 1, b = 2;
    int *p = &a, *q = &b;

    cout << p + q << endl;  // error!

    return 0;
}

C/C++不支持将两个指针做+操作,所以会报错的

切记:string支持的是:string + string,字符串常量不是string

string1 + char:string后接上char,相当于push_back()操作

#include <bits/stdc++.h>
using namespace std;

int main(){
    string str1 = "123";
    char ch = 'c';
    cout << str1 + ch << endl;

    return 0;
}
// 123c

还有一个操作不是很常用,是substr获取string中部分字串

s.substr(pos, len)

从pos下标开始,返回一个长度为len的字串:

#include <bits/stdc++.h>
using namespace std;

int main(){
    string str = "123456";
    cout << str.substr(0, 3) << endl;

    return 0;
}
// 123

总结一下:

  • 默认初始化
  • 值初始化
  • size()操作
  • push_back()
  • + 号
  • substr()

2.关联容器

关联容器,为什么叫关联容器呢?因为这些容器中的元素都是一个关联的对,key-value对,这里面有个词是”关键词“,关键词是什么?关键词就是在容器元素中起到索引作用的,关键词对应的另外一个就是”值“

STL中有8中关联容器,acm中常用的有3中,分别是map,set 和 unordered_map

1)map – 关联数组

map叫关联数组,比如举个和蔼可亲的例子(滑稽),名字和电话号码,一个人对应一个电话号码,那么为什么叫map为关联数组??

首先思考一个map在映射方面和数组有啥区别?

这个明显的是 map可以映射上面刚刚说的名字,关键词可以为名字,但是数组关键词只能是unsigned int。

经过上面的学习,不多细致说了,map支持的操作有:

初始化:

每个容器声明的时候都要指明元素是什么,map的元素是一个对,因此要指明关键词和值的类型,同时C++11支持直接赋值初始化

map<string, string > mp1;
map<string, string > mp2 = { {"a", "1"}, {"b", "2"}, {"c", "3"} }; 

支持下标运算符

#include <bits/stdc++.h>
using namespace std;

int main(){
    map<string, string > mp1;
    map<string, string > mp2 = { {"a", "1"}, {"b", "2"}, {"c", "3"} }; 

    cout << mp2["a"] << endl;
    
    cout << mp2["d"] << endl;


    return 0;
}

如果访问没有建立的映射就为空

再看一下将访问作为左值使用的几种情况:

#include <bits/stdc++.h>
using namespace std;

int main(){
    map<string, string > mp = { {"a", "1"}, {"b", "2"}, {"c", "3"} }; 

    cout << mp["a"] << endl;
    mp["a"] = "yyy";
    cout << mp["a"] << endl;

    cout << mp["d"] << endl;
    mp["d"] = "4";
    cout << mp["d"] << endl;

    return 0;
}
// 1
// yyy
// 
// 4

可以看到,如果对于没有建立的影射,如果对其赋值则会建立这样的映射

因此,我们可以用这样的方式直接建立映射

其他操作用的不多就不多说了~

总结一下:

  • 两种初始化
  • 下标运算符访问
  • 通过下标运算符建立映射

2)set – 集合

set比较简单,就是一个关键词所构成的集合(不能有重复元素的集合)

初始化:同样的

set<int > s1;
set<int > s2 = {1, 2 ,3 ,4, 5, 5};

size()操作

#include <bits/stdc++.h>
using namespace std;

int main(){
    set<int > s1;
    set<int > s2 = {1, 2 ,3 ,4, 5, 5};

    cout << s1.size() << endl;
    cout << s2.size() << endl;

    return 0;
}
// 0
// 5

如何把数据放入set中呢 ???

set给出一个操作是insert

#include <bits/stdc++.h>
using namespace std;

int main(){
    set<int > s = {1, 2 ,3 ,4, 5, 5};

    cout << s.size() << endl;
    s.insert(6);
    cout << s.size() << endl;

    return 0;
}
// 5
// 6

使用set判断某个元素是否在容器中,使用count

count本身是用来记录元素出现的次数,而set中的元素是非重复的,因此count的返回值为1即为存在该元素,0为不存在该元素

#include <bits/stdc++.h>
using namespace std;

int main(){
    set<int > s = {1, 2 ,3 ,4, 5, 5};

    if(s.count(1)){
        puts("yes");
    }else puts("no");

    return 0;
}
// yes

empty – 返回set是否为空,判空

#include <bits/stdc++.h>
using namespace std;

int main(){
    set<int > s;
    if(s.empty()){
        puts("1");
    }

    return 0;
}
// 1

总结一下:

  • 两种初始化的方式
  • size()操作
  • insert操作
  • count()判断元素是否存在于set中
  • 判空

3)unordered_map – 哈希

unordered_map与map的区别就是这个是用哈希函数组织的map

操作和map一样,查询的速度更快

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

int main(){
    unordered_map<int ,string > hash = { {1, "1"}, {2, "2"} };
    cout << hash[1] << endl;
    cout << hash[3] << endl;
    hash[3] = "3";
    cout << hash[3] << endl;

    return 0;
}
// 1
// 
// 3

有的同学可能会看到我上面又补充了一个头文件,可能是没有必要的。

补充的原因是(不重要):

首先头文件bits/stdc++中是有unordered_map的头文件的,但是需要C++11的支持,我用的vs的msvc编译器对C++11的支持不完全,定义__cplusplus还是等于199711L,并不是 201103L(C++11支持的值) ,所以这一部分就需要加上去(有兴趣的话,可以看一下bits/stdc++源码 和 使用预编译 __cplusplus的值 来解决C/C++的兼容问题)

三.容器适配器

为什么叫容器适配器呢?好吧,这个不多说了(感觉上面说了很多废话qwq),acm中用的是基于deque的queue和stack以及由vector衍生出来的priority_queue这三个顺序容器适配器

1.queue – 队列适配器

特性:先进先出

初始化:不一样了

初始化和之前的容器就不一样了,默认初始化依然支持,但是不支持直接赋值初始化的方式,就是这样是不可以的:

queue<int > q = {1, 2, 3}; // error!

这时候要说一下另外的一种初始化方式,采用构造函数初始化

队列支持使用deque来初始化:

queue<int > q1;

deque<int > tmpdq = {1, 2, 3};
queue<int > q2(tmpdq);

大家学过java,使用new创建一个类,但是C++中的类的声明不需要采用new的方式,直接在后面加上括号,然后给出参数即可

size()操作 – 不多说

#include <bits/stdc++.h>
using namespace std;

int main(){
    deque<int > dqtmp = {1, 2, 3, 4};
    queue<int > q(dqtmp);

    cout << q.size() << endl;
    

    return 0;
}
// 4

push操作

push操作就是满足队列的特性,从后进入,然后从前面出来,push就是将一个元素入队

#include <bits/stdc++.h>
using namespace std;

int main(){
    deque<int > dqtmp = {1, 2, 3, 4};
    queue<int > q(dqtmp);

    cout << q.size() << endl;

    q.push(5);

    cout << q.size() << endl;    

    return 0;
}
// 4
// 5

front操作 – 返回队首元素

#include <bits/stdc++.h>
using namespace std;

int main(){
    deque<int > dqtmp = {1, 2, 3, 4};
    queue<int > q(dqtmp);
 
    cout << q.front() << endl;

    return 0;
}
// 1

pop – 队首元素出队

#include <bits/stdc++.h>
using namespace std;

int main(){
    deque<int > dqtmp = {1, 2, 3, 4};
    queue<int > q(dqtmp);
 
    cout << q.front() << endl;
    q.pop();
    cout << q.front() << endl;

    return 0;
}
// 1
// 2

empty – 判空

#include <bits/stdc++.h>
using namespace std;

int main(){
    queue<int > q;
    if(q.empty()){
        cout << 1 << endl;
    }
 
    return 0;
}
// 1

总结一下:

  • 两种初始化
  • size – 返回有效元素数量
  • push – 入队
  • pop – 出队
  • front – 返回队首元素
  • empty – 判空

2.stack – 栈

特性:先进后出,和杯子一样

初始化:同样

 stack<int > st0;

 deque<int > dqtmp = {1, 2, 3};
 stack<int > st(dqtmp);

size – 返回元素数量

#include <bits/stdc++.h>
using namespace std;

int main(){
    deque<int > dqtmp = {1, 2, 3};
    stack<int > st(dqtmp);

    cout << st.size() << endl;


    return 0;
}
// 3

top – 返回栈顶元素

#include <bits/stdc++.h>
using namespace std;

int main(){
    deque<int > dqtmp = {1, 2, 3};
    stack<int > st(dqtmp);

    cout << st.top() << endl;

    return 0;
}
// 3

push – 入栈

#include <bits/stdc++.h>
using namespace std;

int main(){
    deque<int > dqtmp = {1, 2, 3};
    stack<int > st(dqtmp);

    cout << st.size() << endl;

    st.push(4);
    cout << st.size() << endl;


    return 0;
}
// 3
// 4

pop – 出栈

#include <bits/stdc++.h>
using namespace std;

int main(){
    deque<int > dqtmp = {1, 2, 3};
    stack<int > st(dqtmp);

    cout << st.size() << endl;

    st.push(4);
    cout << st.size() << endl;

    st.pop();
    cout << st.size() << endl;

    return 0;
}
// 3
// 4
// 3

empty – 判空

#include <bits/stdc++.h>
using namespace std;

int main(){
    stack<int > st;
    if(st.empty()){
        cout << "empty!" << endl;
    }

    return 0;
}
// empty!

总结一下:

  • 两种初始化
  • size – 栈内元素数量
  • top – 返回栈顶元素
  • push – 入栈
  • pop – 出栈
  • empty – 判空

3.priority_queue – 优先级队列

本质是队列,满足先进先出

只是永远保证当前队列中的元素满足一定的次序(默认降序

默认初始化

priority_queue<int > pq;

较为一般的初始化(可以改变默认排序)

 priority_queue<int > pq;
 priority_queue<int, vector<int >, greater<int > > pq1;
 priority_queue<int, vector<int >, less<int > > pq2;

greater是降序,less是升序,之后会演示,暂时先记住

size – 返回元素个数

#include <bits/stdc++.h>
using namespace std;

int main(){
    priority_queue<int > pq;
    cout << pq.size() << endl;

    return 0;
}
// 0

push – 入队,pop – 出队

#include <bits/stdc++.h>
using namespace std;

int main(){
    priority_queue<int > pq;
    cout << pq.size() << endl;

    pq.push(1), pq.push(2);
    cout << pq.size() << endl;

    pq.pop();

    cout << pq.size() << endl;

    return 0;
}
// 0
// 2
// 1

top – 返回队首元素

#include <bits/stdc++.h>
using namespace std;

int main(){
    priority_queue<int > pq;
    pq.push(1), pq.push(2);

    // 默认降序
    cout << pq.top() << endl;
    
    return 0;
}
// 2

一般化的:改变为升序

#include <bits/stdc++.h>
using namespace std;

int main(){
    priority_queue<int > pq;
    priority_queue<int, vector<int >, greater<int > > pq1;
    priority_queue<int, vector<int >, less<int > > pq2;

    pq1.push(1), pq1.push(2);
    pq2.push(1), pq2.push(2);

    cout << pq1.top() << endl;
    cout << pq2.top() << endl;

    return 0;
}
// 1
// 2

empty – 判空 – 不写代码了

总结一下:

  • 默认初始化
  • 一般化的初始化
  • size – 元素个数
  • push – 入队
  • pop – 出队
  • top – 返回队首元素
  • empty – 判空
0

2条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

20 + 9 =