刚开学这段时间比较水吧,一周时间都没干什么,天天在寝室制毒打游戏,专业学习也没有太过明确的方向,周五晚上看xcxdg写了个maze深有感触,决定把自己以前的东西捡一捡。毕竟三年的青春,从零到零实在对不起自己,决定用一段时间把紫书再预习一遍,如果有能力再看蓝书吧。也算是一种能力的提升。


从第五章开始看,这里就涉及到一个库函数的问题,xcxdg的maze里引用的cstring库,然后我把他的源码粘贴下来编译失败,大体看一下可能就是因为string类没有声明(xcxdg的mazeGitHub链接),在声明里多声明一个string库就可以了。查阅开发文档可以发现,其实string类型声明在string库里,而cstring只是对字符串的一些操作函数。
lrj很巧妙的避开了对象:“本书只使用struct而不使用class。”看来面对对象需要另学了2333///算法竞赛可能更多的是一种面向过程的编程(但这和不打acm的我又有什么关系呢2333)

结构体

struct Point{
int x,y;
Point(int x=0,y=0):x(x),y(y) {}
};

这里在结构体中声明了一个Point函数,没有返回值。这种函数称为构造函数,在声明变量的时候调用,这里0为默认值,:x(x),y(y)是一种简写,代表将成员变量初始化为参数变量,也可写作如下这种形式(this方法)

Point(int x=0,y=0){this->x=x;this->y=y;}

定义结构体“加法”和流输出:

Point operator + (const Point &A, const Point &B){
return Point(A.x+B.x, A.y+B.y);
}
ostream& operator << (ostream &out, const Point& p) {
out<<"("<<p.x<<","<<p.y<<")";
}

模板

我看到的唯一对我来说有用的就是下面这行代码了

template <typename T>
//说多没有用,我只知道对我有用的就行了
//正常情况下如果需要不同的类型可能需要声明多次
int mmax(int,int);
float mmax(float,float);
double mmax(double,double);
//然而有了这行我只需要声明一次
template <typename T>
T mmax(T,T);
//在下面使用的时候就可以使用任何类型

STL初步

sort函数跳过好了,在<algorithm>库中(因为我总拼错这个库才打了一遍)

不定长数组vector

vector<int> a;
a.size()//读取a的大小
a.resize()//改变a的大小
a.push_back()//在尾部添加一个元素
a.pop_back()//弹出尾部的元素
a.clear()//清空
a.empty()//检查是否为空

vector<int> a;类似于int a[];
数据结构底层的坑在学的过程中跟着填好了
vector的用途举例见:UVa101木块问题

集合:set

UVa10815 安迪的第一个字典
题目描述:输入一个文本,找出不同的单词,字典序输出

#include<iostream>
#include<string>
#include<sstream>
#include<set>
using namespace std;
set<string> w;
int main(){
string s,rem;
while(cin>>s){
for(int i=0;i<s.length();i++)
if(isalpha(s[i]))s[i]=tolower(s[i]);else s[i]=' ';
stringstream ss(s);
while(ss>>rem)w.insert(rem);//set中不包含重复元素
}
for(set<string>::iterator it=w.begin();it!=w.end();++it)
cout<<*it<<endl;
return 0;
} 

紫书中例题使用了stringstream这个类型,查了之后发现是一个很牛*的类型:https://blog.csdn.net/liitdar/article/details/82598039
对于迭代器的使用,姑且理解为指针吧,或者说指针是一种迭代器
s.empty(); 如果s 为空返回true,否则false。
s.size(); 返回s 的大小。
s.insert(x); 把x 加入s。
s.erase(x); 把值为x 的元素删除。
s.erase(it); 把迭代器it 所指的元素删除。
s.clear(); 清空s。
it=s.find(x); 返回x 元素的迭代器。
s.lower_bound(x); 返回大于等于x 的第一个元素的迭代器。
s.upper_bound(x); 返回大于x 的第一个元素的迭代器。
it=s.begin(); 得到s 中最小元素的迭代器。
it=s.end(); 得到s 中最大元素
++it;-–it; 得到it 的下一个、上一个元素。
set中元素不重复,从小到大排序

映射:map

提到map之前先看一下pair
这是一个STL中将两个变量打包的方法
调用x=make_pair<a,b>,得到pair<type,Type>类型的变量x,x.first;访问a,x.second;访问b
map类型实际上就相当于set<pair>
map<int,int>
重载[]运算符
m[a]=b; 可以这样进行赋值。
m[a]; 以及这样读取某个位置的值。
map[a]=b;如果不存在first=a,创建一个,如果存在则修改

栈,队列和优先队列

stack 是STL 中后进先出的栈。
需要#include<stack>。
stack<int> s; 来声明。
s.empty(); s.size(); 同上面。
s.top(); 返回栈顶元素。
s.pop(); 弹出栈顶。
s.push(x); 将元素x 压入栈中。

queue符合先进先出(FIFO)原则
声明方式同上
q.empty(); q.size(); 同vector
q.push(x); 向队尾添加元素x。
q.front(); 返回队首元素。
q.back(); 返回队尾元素。
q.pop(); 删除队首。
无iterator 操作。

priority_queue 是STL 中的优先队列,可以查询元素中值最大的元素
和删除值最大的元素。
priority_queue<int,vector<int>,greater<int> > pq; 来声明一个元素值最小的优先级最高的priority_queue。

template<class _Ty = void>
struct greater
{ // functor for operator>
typedef _Ty first_argument_type;
typedef _Ty second_argument_type;
typedef bool result_type;

constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const
{ // apply operator> to operands
return (_Left > _Right);
}
};

自己定义的struct 只要定义了operator <,就可以使用
priority_queue。

struct N{
int id,w;
friend bool operator < (N a,N b){
return a.w<b.w;
}
N(int a=0,int b=0){
id=a;w=b;
}
};
priority_queue<N> pq;

pq.empty(); pq.size(); pq.push(); 同queue。
pq.top(); 返回优先级最高(值最小)的元素。
pq.pop(); 删除优先级最高的元素。


人们还能笑的时候,是不容易被打败的。