C++标准库（PAT算法笔记）

C++标准库 (PAT算法笔记)

1. Vecotr 变长数组

1.1 vector定义

vector<typename> name;

vector<int> name;
vector<double> name;
vector<node> name;     //结构体

vector<vector<int> > name;   //> > 之间要加空格
//可以当作两个维都可变长的二维数组

vector<int> vi[100];   //其中一维已经固定，另一维可变长

1.2 vector容器内元素的访问

//通过下标访问
vi[index];

//通过迭代器访问
vector<int>::iterator it;
vector<double>::iterator it;
//迭代器可以理解为一种类似指针的东西

//可以通过*it来访问vector里的元素
#include <stdio.h>
#include <vector>

using namespaced std;

int main(){
    vector<int> vi;
    for(int i = 1; i <= 5; i++){
        vi.push_back(i);  //循环完毕后，vi中元素为1 2 3 4 5
    }
    //vi.begin()为取vi的首元素地址，而it指向这个地址
    vector<int>::iterator it = vi.begin();
    for(int i = 0; i < 5; i++){
        printf("%d ", *(it + i));    //输出vi[i]
    }
    return 0;
}

//这里可以看出vi[i] 和 *(vi.begin()+i) 是等价的

//begin()函数取vi的首元素地址，end()函数取尾元素地址的下一个地址
//end()作为迭代器末尾标志，不储存任何元素

//另一种遍历vector中元素的写法
#include <stdio.h>
#include <vector>

using namespace std;

int main(){
    vector<int> vi;
    for(int i = 0; i <= 5; i++){
        vi.push_back(i);
    }
    //vector的迭代器不支持it < vi.end()的写法
    //循环条件只能用it != vi.end()
    for(vector<int>::iterator it = vi.begin(); it != vi.end(); it++){
        printf("%d ", *it);
    }
    return 0;
}

//在常用STL容器中，只有vector和string中，才允许使用vi.begin()+i这种写法

1.3 vector常用函数

//push_back()
//在vector后面添加一个元素, 时间复杂度为O(1)
vi.push_back(x);

//pop_back()
//用以删除vector的尾元素，时间复杂度为O(1)
vi.pop_back(x);

//size()
//用来获取vector中元素的个数，时间复杂度为O(1)
vi.size();

//clear()
//用来清空vector中的所有元素，时间复杂度为O(N),N为vector中元素的个数
vi.clear();

//insert()
//用来向vector的任意迭代器it处插入一个元素x， 时间复杂度为O(N)
vi.insert(it, x);

#include <stdio.h>
#include <vector>

using namespace std;

int main(){
    vector<int> vi;
    for(int i = 1; i <= 5; i++){
        vi.push_back(i);
    }
    //1 2 3 4 5
    vi.insert(vi.begin() + 2, -1);   //将-1插入vi[2]的位置
    for(int i = 0; i < vi.size(); i++){
        printf("%d ", vi[i]);
        //1 2 -1 3 4 5
    }
}

//erase()
//1.删除单个元素
vi.erase(vi.begin()+3);

//2.删除一个区间内的所有元素
//erase(first, last)删除[first, last)内的所有元素
vi.erase(vi.begin() + 1, vi.begin() + 4);   //删除vi[1] vi[2] vi[3]
//删除vector内所有元素可以用vi.erase(vi.begin(), vi.end())

1.4 vector常见用途

1. 本身可以用作数组使用，在元素个数不确定的场合可以节省空间
2. 使用vector实现邻接表

2. Set 集合

set是一个内部有序且不含重复元素的容器

2.1 set的定义

set<typename> name;

set<int> name;
set<node> name;

set<typename> Arrayname[arraySize];
set<int> a[100];

2.2 set容器内元素的访问

//set只能通过迭代器访问
set<typename>::iterator it;
set<char>::iterator it;

//不支持*(it+i)的访问方式
//只能按如下方式枚举
#include <stdio.h>
#include <set>

using namespace std;

int main(){
    set<int> st;
    st.insert(3);
    st.insert(5);
    st.insert(2);
    st,insert(3);
    for(set<int>::iterator it = st.begin(); it != st.end();it++){
        printf("%d ", *it);
    }
    return 0;
}

2.3 set常用函数

//insert()
//可将x插入set容器中，并自动递增排序和去重，时间复杂度O(logN).

//find()
//find(value)返回set中对应值为value的迭代器，时间复杂度为O(logN)
set<int>::iterator it = st.find(2);
printf("%d\n", *it);
//or
printf("%d\n", *(st.find(2)));

//erase()
//1.删除单个元素
st.erase(st.find(100));    //利用find()找到100,然后用erase删除  O(1)
st.erase(100);    //O(logN)
//2.删除一个区间元素
st.erase(first, last);  //删除[first, last)     O(last-first)

//size()
//用来获得set内元素的个数  O(1)

//clear()
//O(N)

2.4 set常见用途

set主要作用是自动去重并按升序排序

3. String

3.1 string的定义

#include <string>   //和string.h是两个不同的头文件

string str;
string str = "abcd";

3.2 string中内容的访问

//通过下标访问
//一般来说可以像字符数组那样去访问string
for(int i = 0; i < str.length(); i++){
    printf("%c",str[i]);
}

//如果要读入和输出整个字符串，则只能用cin 和 cout
cin >> str;
cout << str;
//用c_str()将string类型转化为字符数组后可以用printf来输出
string str = "abcd";
printf("%s", str.c_str());

//通过迭代器访问
string::iterator it;
for(string::iterator it = str.begin(); it != str.end(); it++){
    printf("%c", *it);
}

3.3 string常用函数

//operator+=
string str1 = "abc", str2 = "xyz", str3;
str3 = str1 + str2;    //赋给str3
str1 += str2;       //拼接到str1

//compare operator
//两个string类型可以直接用==, !=, <, <=, >, >=比较大小，比较规则是字典序

//length()/size()
//返回string的长度

//insert()
string str = "abcxyz", str2 = opq;
str.insert(3, str2);   //往str[3]处插入opq
//insert(it,it2,it3)  串[it2,it3)插在it位置上
str.insert(str.begin() + 3, str2.begin(), str2.end());

//erase()
//1.删除单个元素
str.erase(str.begin() + 4);    //删除4号位
//删除一个区间内所有元素
//str.erase(first, last)   删除[first,last)
str.erase(str.begin() + 2, str.end() - 1);
//str.erase(pos, length)  //从pos位置删除length长度
str.erase(3, 2);

//clear()

//substr()
//substr(pos, len)  返回从pos号位开始，长度为len的子串   O(len)
string str = "Thank you for your smile.";
cout << str.substr(0, 5) << endl;

//string::npos
//这是一个常数， 本身是-1， 也可认为是unsigned_int类型的最大值
//用以作为find函数失配时的返回值
#include <string>

using namespace std;

int main(){
    if(string::npos == -1){
        cout << "-1 is true." <<endl;
    }
    if(string::npos == 4294967295){
        cout << "4294967295 is also true." << endl;
    }
}
//两个数都会输出

//find()
//str.find(str2), 当str2是str的子串时， 返回其在str中第一次出现的位置；
//如果str2不是str的子串，那么返回string::npos.
//str.find(str2, pos)   从str的pos号开始匹配str2    
//时间复杂度 O(nm)  nm分别为str 和 str2 的长度

//replace()
str.replace(pos, len, str2);  //把str从pos位开始，长度为len的子串替换为str2
str.replace(it1, it2, str2);  //把str的迭代器[it1, it2)范围的子串替换为str2
//O(str.length())

4. Map映射

map可以将任何基本类型（包括STL容器）映射到任何基本类型

4.1 map定义

map<typename1, typename2> mp;

//如果是字符串到整型的映射，必须使用string而不能用char数组
map<string, int> mp;

map<set<int>, string> mp;

4.2 map容器内元素的访问

//通过下标访问
#include <stdio.h>
#include <map>

using namespace std;

int main(){
    map<char, int> mp;
    mp['c'] = 20;
    mp['c'] = 30;  //20被覆盖
    printf("%d\n", mp['c']);    //输出30
    return 0;
}

//通过迭代器访问
map<typename1, typename2>::iterator it;
//因为map的每一对映射都有两个typename，这决定了必须能通过一个it来同时访问键和值
//map可以通过it->first来访问键， 通过it->second来访问值
#include <stdio.h>
#include <map>

using namespace std;

int main(){
    map<char, int> mp;
    mp['m'] = 20;
    mp['r'] = 30;
    mp['a'] = 40;
    for(map<char, int>::iterator it = mp.begin(); it != mp.end(); it++){
        printf("%c %d\n", it->first, it->second);
    }
    return 0;
}
//map会以键从小到大的顺序自动排序
//map和set内部都是使用红黑树实现的

4.3 map常用函数

//find()
//find(key)返回键为key的映射的迭代器   O(logN)
#include <stdio.h>
#include <map>

using namespace std;

int main(){
    map<char, int> mp;
    mp['a'] = 1;
    mp['b'] = 2;
    ma['3'] = 3;
    map<char, int>::iterator it = mp.find('b');
    printf("%c %d\n", it->first, it->second);
    return 0;
}

//erase()
//1.删除单个元素    
mp.erase(it);     //O(1)
mp.erase('b');    //O(logN)
//2.删除一个区间内所有元素
mp.erase(first, last);   //删除[first, last)

//size()
//用来获取map中映射的对数     O(1)

//clear()     O(N)

4.4 map的常见用途

1. 需要建立字符（或字符串）与整数之间映射的题目，使用map可以减少代码量
2. 判断大整数或者其他类型数据是否存在的题目，可以把map当bool数组用

5. Queue队列

5.1 queue的定义

//先进先出的容器
#include <queue>
using namespace std;
queue<typename> name;

5.2 queue容器内元素的访问

//由于队列本身就是一种先进先出的限制性数据结构
//只能通过front()来访问队首元素，或是通过back()来访问队尾元素
#include <stdio.h>
#include <queue>

using namespace std;

int main(){
    queue<int> q;
    for(int i = 1; i <= 5; i++){
        q.push(i);
    }
    printf("%d %d\n", q.front(), q.back());
    return 0;
}

5.3 queue常用函数

//push() 入队

//front()

//back()

//pop()  出队

//empty()   检测queue是否为空  空->true 

//size()

5.4 queue常见用途

1. 广度优先搜索
2. 使用 pop() 和 front() 函数前，必须用empty() 判断队列是否为空

6. Priority_queue优先队列

6.1 priority_queue的定义

//priority_queue底层是用堆来实现的
//在优先队列中，队首元素一定是当前队列中优先级最高的那个
//可以在任何时候往优先队列中加入元素，其底层数据结构堆会随时调整结构，使得每次队首元素都是优先级最大的
#include <queue>

using namespace std;

priority_queue<typename> name;

6.2 priority_queue容器内元素的访问

//只能通过top()函数来访问队首元素（也可称为堆顶元素）
printf("%d\n", q.top());

6.3 priority_queue常用函数

//push()   O(logN)

//top()    O(1)

//pop()    O(logN)

//empty()  O(1)

//size()   O(1)

6.4 priority_queue内元素优先级的设置

//基本数据类型的优先级设置
//int char double 等

priority_queue<int> q;
priority_queue<int, vector<int>, less<int> > q;
//其中vector<int>填写的是来承载底层数据结构堆的容器
//less<int>是对第一个参数的比较类
//less表示数字大优先级越大，greater表示数字小的优先级越大

//结构体的优先级设置
struct fruit{
    string name;
    int price;
    //对 < 进行重载
    friend bool operator < (fruit f1, fruit f2){
        return f1.price < f2.price;
    }
    //重载后内部以价格高的水果为优先级高
}
priority_queue<fruit> q;

//or
struct cmp{
    bool operator () (fruit f1, fruit f2){
        return f1.price > f2.price
    }
}
priority_queue<fruit, vector<fruit>, cmp> q;

//如果结构体内数据较为庞大，建议使用引用来提高效率
friend bool operator < (const fruit &f1, const fruit &f2){
    return f1.price > f2.price;
}
bool operator () (const fruit &f1, const fruit &f2){
    return f1.price > f2.price;
}

6.5 priority_queue常见用途

1. 解决贪心问题
2. 对Dijkstra算法进行优化
3. 使用 top() 前，必须用empty()判断优先队列是否为空

7. Stack堆

7.1 stack的定义

//后进先出
#include <stack>

using namespace std;

stack<typename> name;

7.2 stack容器内元素的访问

//只能通过top()来访问栈顶元素

7.3 stack常用函数

//push()

//pop()

//top()

//empty()

//size()

//以上复杂度均为O(1)

7.4 stack常见用途

1. 模拟递归

8. Pair

8.1 pair的定义

//将两个元素绑在一起合成一个元素
#include <utility>

using namespace std;

pair<typename1, typename2> name;
//等同于以下结构体
struct pair{
    typename1 first;
    typename2 second;
};

pair<string, int> p;
pair<string, int> p("haha", 5);  //定义
pair<string, int>("haha", 5);
make_pair("haha", 5);

8.2 pair中元素的访问

//pair中只有两个元素：first和second
//只需按正常结构体的方式去访问即可
pair<string, int> p;
p.first = "haha";       //另一种赋值方式
p.second = 5;
cout << p.first << " " << p.second << endl;

8.3 pair常用函数

//比较操作数
//可以直接使用==, !=, <, <=, >, >= 比较大小
//先以first的大小作为标准，只有当first相等时才去判别second的大小

8.4 pair常见用途

1. 代替二元结构体
2. 作为map的键值对来进行插入

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main(){
    map<string, int> mp;
    mp.insert(make_pair("heihei", 5));
    mp.insert(pair<string, int>("ahh", 10));
    for(map<string, int>::iterator it = mp.begin(); it != mp.end(); it++){
        cout << it->first << " " << it->second << endl;
    }
    return 0;
}

9. algorithm头文件下常用函数

9.1 max(), min(), abs()

最大值，最小值，绝对值

9.2 swap()

交换 x 和 y 的值

9.3 reverse()

#include <stdio.h>
#include <algorithm>

using namespace std;

int main(){
    int a[10] = {10, 11, 12, 13, 14, 15};
    reverse(a, a + 4);
    for(int i = 0; i < 6; i++){
        printf("%d ", a[i]);
    }
    return 0;
}
//result:13 12 11 10 14 15
//也可对字符串某一段进行反转

9.4 next_permutation()

//给出一个序列在全排列中的下一个序列

//n == 3时全排列为
123
132
213
231
312
321
    
#include <stdio.h>
#include <algorithm>
    
using namespace std;

int main(){
    int a[10] = {1, 2, 3};
    do{
        printf("%d%d%d\n", a[0], a[1], a[2]);
    }while(next_permutation(a, a + 3));
    return 0;
}
//输出上述全排列
//next_permutation在已经到达全排列的最后一个时会返回false

9.5 fill()

//可以把数组或容器中某一区间赋值为某一相同的值
//和memset不同，这里的赋值可以是数组类型对应范围中的任意值
#include <stdio.h>
#include <algorithm>

using namespace std;

int main(){
    int a[5] = {1, 2, 3, 4, 5};
    fill(a, a + 5, 111);
    for(int i = 0; i < 5; i++){
        printf("%d ", a[i]);
    }
    return 0;
}

//result:111 111 111 111 111

9.6 sort()

//排序

int a[6] = {9, 4, 5, 2, -6, -1};
sort(a, a + 4);

//char型数组默认按字典序进行排序

//实现比较函数cmp
//若比较函数不填，则默认按从小到大排序
bool cmp(int a, int b){
    return a > b;
}
sort(a, a + 4, cmp);   //从大到小

//结构体数组排序
struct node{
    int x, y;
}ssd[10];

bool cmp(node a, node b){
    return a.x > b.x;     //按x排序
}

bool cmp(node a, node b){
    if(a.x != b.x)
        return a.x > b.x;
    else
        return a.y < b.y;
}

//容器的排序
//只有vector, string, deque是可以使用sort的

9.7 lower_bound(), upper_bound()

lower_bound(first, last, val) 用来寻找在数组或容器的[first, last)范围内第一个值大于等于val的元素的位置，如果时数组，则返回该位置的指针； 如果是容器，则返回该位置的迭代器。

upper_bound(first, last, val) 用来寻找在数组或容器的[first, last)范围内第一个值大于val的元素的位置，如果时数组，则返回该位置的指针； 如果是容器，则返回该位置的迭代器。

如果数组或容器中没有需要寻找的元素，则二者均返回可以插入该元素位置的指针或迭代器（即假设存在该元素时，元素应当在的位置）。

复杂度均为O(log(last - first))