上年跟学长学STL时写的博客，由于刚学很多不懂，很多地方解释不详细，现在来填一下坑，力求准确详细吧！——2020年 6 月1 日

1.C++输入与输出

1.1头文件：

#include <iostream>

1.2头文件与主函数之间：

using namespace std;

使用（using）名空间（namespace）std，std是名空间的名字，这是C++为了解决不同工程的变量，函数，类等命名冲突的问题，引入的名空间（namespace）的概念，相当于文件夹的目录和子文件的关系——不同的目录（namespce）下即使有相同子文件名/文件夹名（变量，函数，类）也不会产生冲突（记住别忘加就行！）

1.3输入cin：

1.3.1 cin输入的原理

程序的输入都建有一个缓冲区，即输入缓冲区。一次输入过程是这样的，当一次键盘输入结束时会将输入的数据存入输入缓冲区，而cin函数直接从输入缓冲区中取数据。正因为cin函数是直接从缓冲区取数据的，所以有时候当缓冲区中有残留数据时，cin函数会直接取得这些残留数据而不会请求键盘输入。
注意：cin>>和cin.get()都残留数据不会出错，但是cin.getline会报错，下面的示例中都有体现。

1.3.2 cin >>

存储变量类型：char,int,string都可以；
输入结束条件：遇到Enter、Space和Tab键。（如含有空格的字符串无法完全读取）
对结束符处理：丢弃缓冲区中使得输入结束的结束符（Enter、Space和Tab），但最后输入结束时不会丢弃结束字符（具体见代码）。
实例：

#include<iostream>
using namespace std;
int main()
{
    char c1,c2,c3;
    cin >> c1;
    cin >> c3;
    cin.get(c2);
    cout << c1 << endl;
    cout << c3 << endl;
    cout << c2 << 44 << endl;
    return 0;
}

解释：输入为1[Space]2[Enter]，cin >>先读取1存入c1 由于缓冲区还有数据,cin >> 先清除[Space] 然后读取2存入c3，后面没有数据了，结束读取并保留缓存区里剩下的数据（即换行符[Enter]），用cin.get()读取存入c2，依次输出可得图示结果。

1.3.3 cin.get()

存储变量类型：char。
输入结束条件：Enter键（因此可接受空格和Tab键）。
对结束符处理：不丢弃缓冲区中的Enter。
使用方法：

ch=cin.get() 或 cin.get(ch)
cin.get(数组名，长度，结束符):
结束符为可选参数，读入的字符个数最多为长度-1个，结束符规定结束字符串读取的字符，默认为enter。
输入结束条件：结束符或者输入大于指定长度-1时；
读取时对字符的处理：不跳过空格，tab，enter，读取长度小于指定长度-1的字符，直至遇到enter结束；
结束时不丢弃任何字符，故可用于带空格的字符串的输入。

1.3.4 cin.getline()

cin.getline(数组名，长度，结束符) 大体与 cin.get(数组名，长度，结束符)类似。
区别在于：
cin.get()当输入的字符串超长时，不会引起cin函数的错误，后面的cin操作会继续执行，只是直接从缓冲区中取数据。但是cin.getline()当输入超长时，会引起cin函数的错误，后面的cin操作将不再执行。 cin.getline()是以enter为结束标志的，同时丢弃了enter。

1.4输出：cout

cout << a << b << endl; //endl为换行符
推荐此博客，比较详细，特殊的输出个人觉得用printf比较方便（如保留小数输出）

2.C++的重载

2.1重载函数

C++允许在同一范围中声明几个功能类似的同名函数，但是这些同名函数的形式参数（指参数的个数、类型或者顺序）必须不同，即函数的参数列表不同，也就是说用同一个运算符完成不同的运算功能。这就是重载函数。重载函数常用来实现功能类似而所处理的数据类型不同的问题。重载函数通常用来命名一组功能相似的函数，这样做减少了函数名的数量，避免了名字空间的污染，对于程序的可读性有很大的好处。当函数的编写者充分考虑了不同情况下应该运行稍有不同的函数，函数的使用者就不必为这些小细节而烦恼了。

2.1.1例：

void print(int a)
void print(string a) //参数类型不一样
void print(int a ,string b); //参数个数不同
void print(string a ,int b);//参数顺序不同

2.2重载运算符

您可以重定义或重载大部分 C++ 内置的运算符。这样，您就能使用自定义类型的运算符。重载的运算符是带有特殊名称的函数，函数名是由关键字operator 和其后要重载的运算符符号构成的。与其他函数一样，重载运算符有一个返回类型和一个参数列表。

2.2.1实现一个操作符重载的方式通常分为两种情况：

将操作符重载实现为类的成员函数；
操作符重载实现为非类的成员函数（即全局函数）。

2.2.1.1将操作符重载实现为类的成员函数

在类体中声明（定义）需要重载的操作符，声明方式跟普通的成员函数一样，只不过操作符重载函数的名字是“关键字 operator +以及紧跟其后的一个C++预定义的操作符”，代码如下:

struct node 
{
    int x,y;
    bool operator < (node t)//重载‘<’运算符，函数返回值为布尔类型（比较运算符只有是和否两种值）
    {
        return x<t.x;
    }
    node operator + (node t)//重载‘+’运算符，返回值为node类
    {
        x=x+t.x;
        return *this;//this是指向该类的指针，对其解引用*表示返回的是这个类
    }
};

点击看对this指针的解释

2.2.1.2操作符重载实现为非类的成员函数（即全局函数）

对于全局重载操作符，代表左操作数的参数必须被显式指定(即必须手动指定，用const变常量)，示例如下：

struct node
{
    int x,y;
}
bool operator==(node const& p1 ,node const& p2)
{
    if (p1.x == p2.x)
    {
        return true;
    }
    else
    {
        return false;
    }
}

““操作符的重载看这里

3.标准模板库STL

3.1`#include<algorithm>//推荐最后看这一块`

3.1.1包括函数：

max(); min(); swap(); abs(); sort();等

3.1.2sort函数：

int a[10];要排此数组需要写成sort(a,a+10);//第一个参数代表首地址，第二个代表最后一个数据的后一个
sort默认从小到大排，如果要从大到小需要写成这种形式：sort(a,a+10,greater<int>());
sort自定义排序（如对struct的排序）：
1.利用c++操作符重载
2.利用cmp函数，即第三参数，代码如下：

struct node 
{
    int x,y;
};
bool cmp(node a,node b)
{
    return a.x<b.x
};
node a[10];
sort(a,a+10,cmp);//写法是这样的，真正使用当然要放在具体的位置

3.1.3reserve()翻转

reverse(a.begin(),a.end());//翻转一个vector
reverse(a,a+n);//翻转一个下标0—n-1的数组

3.1.4 unique 去重

返回去重后的尾迭代器（指针），即去重后末尾元素的下一个位置。该函数常用于离散化，利用迭代器（指针）的减法，可计算出去重后元素的个数，当然也可以计算出重复元素的个数。

//m记录去重后元素个数，在unique函数里实现了去重并把去重后的数据存回原数组中。
int m = unique(a.begin(),a.end()) - a.begin();
int m = unique(a,a+n)-a;

3.1.5 lower_bound/upper_bound 二分查找

lower_bound的第三个参数传入一个元素x，在两个迭代器（或指针）指定的部分上执行二分查找，返回指向第一个大于等于x的元素的位置的迭代器（指针）。 upper_bound则是查找第一个大于x的元素。（当然数据一定保证有序）

3.1.6 next_permutation下一个排列

把两个迭代器（指针）指定的部分看作一个排列，求出这些元素构成全排列中，字典序排在下一个的排列，并直接在序列上更新。另外如果不存在排在更后面的排列，则返回false，否则返回true。同理有 prev_permutation函数。

//输出12345的全排列
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n=5;
    int a[100];
    for(int i=1;i<=n;i++) a[i]=i;
    while(next_permutation(a+1,a+n+1))
    {
        for(int i=1;i<=n;i++)
            cout <<a[i] <<' ';
        cout << endl;
    }
    return 0;
}

3.2 `#include <queue> & #include <stack>`

3.2.1包括函数：

    stack <int> s;//定义栈：stack<类型> 队列名称
    s.empty();//如果栈为空则返回true, 否则返回false;
    s.size();//返回栈中元素的个数
    s.top();//返回栈顶元素, 但不删除该元素
    s.pop();//弹出栈顶元素, 但不返回其值
    s.push();//将元素压入栈顶

    queue <int> q;//定义队列：queue<类型> 队列名称
    q.empty();//如果队列为空返回true, 否则返回false
    q.size();//返回队列中元素的个数
    q.front();//返回队首元素但不删除该元素
    q.pop();//弹出队首元素但不返回其值
    q.push();//将元素压入队列
    q.back();//返回队尾元素的值但不删除该元素

3.2.2优先队列

3.2.2.1 定义

优先队列和队列一样，只能从队尾插入元素，从队首删除元素。队列中最大的元素总是位于队首。可以通过重载<运算符来重新定义比较规则。

3.2.2.2访问

和队列不同，优先队列没有front() 和back() 函数，只能通过 top（）来访问队首元素（堆顶元素，优先级最高的函数）

3.2.2.3定义优先队列

priority_queue<int> q1;
priority_queue<double> q2;
priority_queue <int,vector<int> ,greater<int> > q;//使元素按照从小到大顺序出队 
priority_queue <int,vector<int> ,less<int> > q2;//降序排列 ，无需声明vector头文件

3.2.2.4常用函数

empty() 如果队列为空，则返回真

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

push() 加入一个元素

size() 返回队列的元素个数

top() 取队顶元素//使用top()函数之前，必须用empty() 判断队列是否为空

3.2.2.5 重载运算符“<”

int,string,等类型本身可以比较大小，若使用结构体等类型或者有特殊的需求，则需要重载运算符“<”。
例如下面的结构体保存了二维平面上的点的编号和左边，比较大小时有优先横坐标，其次纵坐标。

        struct poi
    {
        int id;
        int x,y;
    };
    bool operator < (const poi &a,const poi &b)
    {
        return a.x<b.x||a.x==b.x&&a.y<b.y;
    }

3.3`#include<vector>`

vector可理解为变长数组，它的内部实现基于倍增思想。按照下列思路可以大致实现一个vector:设n, m为vector的实际长度和最大长度。向vector加入元素前，若n=m,则在内存中申请2m的连续空间，并把内容转移到新的地址上(同时释放旧的空间)，再执行插入。从vector中删除元素后，若n≤m/4,则释放一半的空间。
vector支持随机访问，即对于任意的下标0≤i< n,可以像数组一样用[i] 取值。但它不是链表，不支持在任意位置0(1) 插入。为了保证效率，元素的增删一般应该在末尾进行。

3.3.1声明

vector <int>a;//相当于申请一个长度动态变化的int数组
vector <int> b[100];//相当于申请一个第一维长100，第二维动态变化的int数组
struct node;
vector <node> c;//结构体类型也可以保存在vector中

3.3.2 迭代器

迭代器就像STL容器的“指针”,可以用星号“*”操作符解除引用。一个保存 int的vector的选代器声明方法为:

vector<int>::iterator it;

vector的迭代器是“随机访问迭代器”，可以把vector的迭代器与一个整数相加减，其行为和指针的移动类似。可以把vector的两个迭代器相减，其结果也和指针相减类似，得到两个迭代器对应下标之间的距离。

3.3.3 常用函数

a.size();//返回vector实际长度（元素个数）
a.empty();//vector空返回 true 非空返回false
a.clear();//清空vector
a.begin();//返回指向vector中第一个元素的迭代器，如*a.begin()等价于a[0]
a.end();//返回指向vector中最后元素后面一位的迭代器，如*a.end()等价于a[n]都是越界访问，其中n=a.size();
a.front();//返回vector第一个元素等价于a[0]
a.back();//返回vector最后一个元素 等价于*--a.end()和a[a.size()-1]
a.push_back(x);//把元素x插入vector a的末尾
a.pop_back();//删除vector末尾的一个元素

3.3.4 典型应用（vector代替邻接表保存有向图）

const int maxn = 100010;
vector <int> ver[maxn],edge[maxn];
//建边
void add(int x,int y,int z)
{
    ver[x].push_back(y);
    edge[x].push_back(z);
}
//遍历从x开始的所有边
for(int i=0; i<ver[x].size(); i++)
{
    int y=ver[x][i],z=edge[x][i];
}

3.4 `include<depue>`

双端队列deque是一个支持在两端高效插入或删除元素的连续线性存储空间。它就像是vector和queue的结合。与vector相比，deque 在头部增删元素仅需要0(1)的时间;与queue相比，deque像数组-样支持随机访问。

    deque<int> dq;
    dq.begin();
    dq.end();
    dq.front();
    dq.back();
    dq.push_back();
    dq.pop_front();
    dq.pop_back();
    dq.pop_front();
    dq.clear();

3.5 `include<set>`

此头文件包含：set和multiset，分别为“有序集合”和“有序多重集合”，即前者的的元素不能重复，而后者可以包含若干个相等的元素。set和multiset的内部实现是一棵红黑树(平衡树的一种)，它们支持的函数基本相同。

3.5.1声明

    set<int>s;
    multiset<double> s2;
    struct node;
    set<node> s3;

set和multiset存的元素必须定义“小于号”。

3.5.2迭代器

set和multiset的迭代器称为“双向访问迭代器”，不支持“随机访问”，支持星号(*)解除引用，仅支持“++”和“–”两个与算术相关的操作。

set<int>::iterator it;

若把it++,则it将会指向“下一个”元素。这里的“下一个”是指在元素从小至大排序的结果中，排在it下一名的元素。同理，若把it-,则it将会指向排在“上个”的元素。
请注意，执行“++”和–”操作的时间复杂度都是0(logn)。执行操作前后，必仔细检查，避免迭代器指向的位置超出首、尾迭代器之间的范围。

3.5.3主要函数

    set<int>s;
    s.size();
    s.empty();
    s.clear();
    s.begin();
    s.end();
    s.insert(x); //把x插入s中，s有序且不重复，时间复杂度O(logn)
    s.find(x);//s中查找x 返回迭代器，若不存在返回s.end();
    s.lower_bound(x);//返回大于等于x的元素最小的一个的返回迭代器
    s.upper_bound(x);//返回大于x的元素最小的一个的迭代器
    s.erase(it);//it为迭代器，从s中删除  it指向的元素
    s.count(x);//返回集合中等于x的个数，用于multiset

3.6 `include<map>`

map容器是一个键值对key-value的映射。内部实现是一棵以key为关键码的红黑树。map的key和value可以是任意类型，其中key必须定义“小于号”运算符。
声明方法：

map<key_tpye,value_type>;

很多时候map被当作Hash表使用，建立起从复杂信息key（如字符串）导简单信息value（如一定范围内的整数）的映射，大部分操作时间复杂度为O(logn)。

3.6.1迭代器

map的迭代器与set一样，也是“双向访问迭代器”。对 map的迭代器解除引用后，将得到一个二元组pair<key. type, value type>。

3.6.2 基本函数

//Insert 的参数类型是pair，erase参数可以是迭代器或者pair
    map<int,int> h;
    h.insert(make_pair(1,2));
    map<int,int> :: iterator it = h.begin();
    pair<int,int> p=*it;
    h.erase(it),h.erase(make_pair(2,3));
    //查找key为x的二元组，返回二元组的迭代器，不存在返回h.end();时间复杂度O(logn)
    h.find(x);

3.6.3 []操作符

[]操作符返回key映射到的value的引用，时间复杂度为O(logn)。
[]操作符是map最吸引人的地方，我们可以很方便地通过h[key]得key对应的value,还可以对key进行赋值操作，改变key对应的value
需要特别注意的是，若查找的key不存在，则执行h[key]后，h会自动新建一个二元组(e,zero),并返回zero的引用。这里zero表示一个广义“零值”，如整数0、空字符串等。如果查找之后不对h[key]进行赋值，那么时间一长，h会包含很多无用的“零值二元组”，白白地占用了空间，降低了程序运行效率。强烈建议读者在用[]操作符查询之前，先用find方法检查key的存在性。

3.6.4 例子

用map统计字符串出现的次数
给定n个字符串，m个问题，每个问题询问一个字符串出现的次数。n≤20000，m < 20000，每个字符串的长度都不超过20。

map<string,int> h;
    char str[25];
    for(int i=1;i<=n;i++)
    {
        scanf("%s",str);h[str]++;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%s",str);
        if(h.find(str)==h.end()) puts("0");
        else printf("%d\n",h[str]);
    }
    return 0;

3.7 `include<bitset>`

bitset可看作一个多位二进制数，每8位占用1个字节，相当于采用了状态压缩的进制数想，并支持基本的位运算，在估算程序运行的时间时，我们一般以32位整数型的运算次数为基准，因此n位bitset执行一次位运算的复杂度可视为n/32，效率高。

3.7.1 声明

bitset<10000> s;
表示一个10000位的二进制数，<>里填位数

3.7.2 位运算操作符

~s：返回对s按位取反的结果
&，|，^：返回对两个位数相同的bitset执行按位与、或、异或运算的结果
“<<” “>>”：返回把一个bitset右移、左移若干位的结果
“” “!=”比较两个bitset代表的二进制数是否相等

3.7.3[]操作符号

s[k]表示s的第k位，可取值，可赋值

3.7.4 基本函数

s.count();//返回有几个1
s.any();//至少一位为1返回true
s.none();//所有为0 返回true
s.set();//所有为变为1
s.set(k,v);//即k[k]=v
s.reset();//所有位变为0
s.reset(k);//即s[k]=0
s.flip();//所有位取反
s.flip(k);//即s[k]^=1;

参考资料《算法竞赛进阶指南》——李煜东著