【技术创作101训练营】不学STL 怎么做算法题？

讲两句

在座的可能都是 大一大二的 学弟学妹，可能对于算法的学习还比较陌生

还停留在 C语言学习的初期

或是学习了数据结构，也经过了一番练习，

对学习有了一些自己的看法，

今天我作为训练营的负责人，想向到场的同学，解释一下 为什么 咱们要学习使用 C++ 并且 要学会 STL 的使用。

为何要用C++

首先是为何要使用C++ ，因为

竞赛不是做工程

不会用到很多c++面向对象的特性

基本的语法会写能做题就够了

主要学下STL标准模板库

边做OJ上的题边学

不用特意去学c++

C++ 的运行速度 一般情况下更快，做题时，不易超时 超内存

代码也很简洁易懂，

在我看来 更重要的是有丰富的 往届题解可以用来参考

最最基础的hello world

C++这么好用 代码写的简洁优美 《C++ primer plus》 长的要死 听我讲完 就上手C++ 吧

C++ 常用的 工具 其实就那么几个

C++ 向下兼容 C

所以对于学过 C语言 的小萌新 也不要太畏惧

半个小时 就能完全上手

只要 引入头文件

 #include<iostream>

再加上命名空间

using namespace std;

后面就可以 和C语言一样正常写了

还有更好使的 cin 和 cout

直接 用 cin>> a 还有 cout<<a 就可以 替换掉原来的 scanf("%d",&a); 和 printf("%d",a);

不需要注明类型了 ， c++ 可以自动的识别输出了，但是格式化输出 就麻烦了，还是 printf 更好

不过呢，好用虽好用，但是可是会让速度变慢哦，如果超时了 就老老实实 换回 scanf("%d",&a); 和 printf("%d",a); 吧

来个例子 看看吧

#include<iostream>
using namespace std;
int main(){
    string s;
    cin>>s;
    cout<<"Hello "<<s<<endl;
}

常用容器

vector

（Vector）是一个封装了动态大小数组的顺序容器。

1.初始化(构造函数)

vector():创建一个空vector

vector(int nSize):创建一个vector,元素个数为nSize

vector(int nSize,const t& t):创建一个vector，元素个数为nSize,且值均为t

2.增加元素

void push_back(const T& x):向量尾部增加一个元素X

3.删除函数

void pop_back();删除向量中最后一个元素

4.循环遍历

iterator begin():返回向量头指针，指向第一个元素

iterator end():返回向量尾指针，指向向量最后一个元素的下一个位置

vector<int>::iterator

5.判断函数

bool empty() const:判断向量是否为空，若为空，则向量中无元素

6.大小函数

int size() const:返回向量中元素的个数

set

set是集合，set不存在重复的元素，会按照从小到大进行排序

set集合中没有重复的元素

set中的元素都是排好序的

头文件引入

#include<set>

增加元素

insert()--在集合中插入元素

循环遍历

iterator begin()--指向第一个元素的位置

iterator end()--指向最后一个元素的下一个位置

for(set<int>::iterator it; it != s.end(); it++){

cout << *it << endl;

}

查询数目

size()--集合中元素的数目

删除数据

erase()--删除集合中的元素

void clear()--删除所有的数据

查找数据

find()--查找值对应的位置

注意

如果元素存在那么返回其对应的位置

否则返回end指针

所以如果查找某个元素是否存在要做的条件判断

if(s.find(233)!=s.end()){

cout << "是的元素存在" << endl;

}

例题::set 集合的“交”与“并”

ios::sync_with_stdio(false);可以提高效率

map

第一个可以称为关键字(key)，每个关键字只能在map中出现一次

key － value的对应

以map<string , int> mp;举例

增加元素

mp"hx" = 20;

mp"h3zh1" = 21;

cout << mp"hx" << endl;

cout << mp"h3zh1" << endl;

cout << mp"wow" << endl; //注意在键没有对应值时，会返回默认值，比如int就返回0，string返回空字符串

循环遍历

iterator begin()--指向第一个元素的位置

iterator end()--指向最后一个元素的下一个位置

查找函数

find()--查找值对应的位置

同set的find，如果找不到则返回最后一个元素的下一个位置

删除函数

erase()---根据键删除元素

clear()--清处所有的元素

stack

称为栈(或者堆栈)，堆栈是一个不容忽视的概念。堆栈都是一种数据项按序排列的数据结构，只能在一端( 称为栈顶(top) )对数据项进行插入和删除.

特点: 先进后出

头文件

#include <stack>

增加元素

push() 在栈顶增加元素

删除元素

pop() 移除栈顶元素

返回栈中元素数目

size()

返回栈顶元素

top()

判断是否为空

empty()

queue

队列是一种特殊的 线性表 ，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

特点: 先进先出

头文件

#include <queue>

增加元素

push()----将元素加入到队尾

删除

pop()---删除队列的第一个元素

获取第一个元素

front()：返回 queue 中第一个元素的引用

获取最后一个元素

back()：返回 queue 中最后一个元素的引用

C++ 引用 & 与传值的区别

c++ & 被称为引用符号(函数参数列表使用)

c语言 & 被称为取地址运算符

函数传参 int a 是传递a的值 进行函数运算

使用引用变量 int &a 是直接对变量本身进行操作

##　引用＆　例子

引用

void func(int &a) {

// 传⼊入的是n的引⽤用，相当于直接对n进⾏行行了了操作，只不不过在func函数中换了了个名 字叫a

a = 99; 

}

int main() {

int n = 0;

func(n); // n由0变成了99

}

传值

void func(int a) {

// 传入的是0这个值，并不会改变main函数中n的值

a = 99; 

}

int main() {

int n = 0;

func(n);// 并不会改变n的值，n还是0 

}

C++ struct

c++ 和 c 语言一样，但是 c++ 可以 可以省略 struct 关键字 直接使用

代码样例

struct stu {

int grade;

float score;

};

struct stu arr110;// C语⾔兼容

stu arr210;// C++ 特有省略

C++ sort

头文件 #include<algorithm>

c++ 的默认计算相关的类集合

sort

swap

max

min

sort使用时

一般使用在结构体 容器向量排序

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

万能文件头 #include<bits/stdc++.h>

一次调用 全部引用 但是学习期间还是推荐 单独引用

sort使用

语法

Sort(start,end,cmp);

参数

（1）start 表示要排序数组的起始地址；

（2）end 表示数组结束地址的下一位；

（3）cmp 用于规定排序的方法，可不填，默认升序。

学习方法吧

说了这么多，最后还是想总结一下，大家应该如何学习吧。

首先学习知识肯定是最最重要的，大家在学校努力学习 数据结构课程 和算法设计课程的同时，可以在MOOC 上 Bilibili 上搜索相关视频课程，也可以看一看 云+社区的博客，去各大博客平台搜一搜教程都是不错的学习方法

其次，学习了基础知识一定要通过敲代码来巩固学习， 可以在各大知名 ACM 的 OJ 平台去练习 也可以 上 LeetCode 感受下面试题，也可以上 PAT 练习天梯赛 的比赛真题 去 CCF 官网 刷 CSP 的真题等，都可以进行练习，

最后需要总结 归纳自己学习的知识和练习的内容，从而达到升华，完成一整套学习正向循环

可以以博客的方式 发到 云加社区， 也可以录制成分享视频，代码讲解等等 各种形式进行归纳总结

既方便了他人，能够给学弟学妹做参考，也可以丰富自己的知识体系

达到知识的内化和提升

总之是没有任何坏处的。

听到这里可能大家都想跃跃欲试了，等下大家就可以 拿出自己的电脑 学起来了。

谢谢大家，大家赶紧操练起来吧~