C++常见的STL用法（机试向）

古即

写在前面

作为计算机相关专业的学生，无论是就业、考研复试、保研，机试都是一个很常见且重要的考核。其中一般OJ平台上C++、java是最常见的两种主流使用语言，考虑到性能运行速度的问题，我是主要使用C++作为主语言，下面结合自己平时刷acwing、PTA、蓝桥、力扣等平台程序设计算法题的一些经验，对C++中常见的STL 用法做一个大致的总结。本人小白，如果有问题欢迎大佬们批评指正!
常见STL

Vector

vector, 变长数组，倍增的思想，这个很常见，比一般数组好用很多！
常见函数如下：

size()          返回元素个数
empty()       返回是否为空
clear()      清空
front()/back()      返回第一个元素/返回最后一个元素
push_back()/pop_back()      在后面插入一个元素/删除最后一个元素
begin()/end()     返回数组开头的迭代器/返回数组结尾的迭代器
[]       支持像数组那样通过[]取元素
支持比较运算，按字典序

示例：
#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> res{1,2,3,4,5};
    vector<int> a{6,7,8,9,10};
    for(int i = 0;i < 5;i++)
    {
        cout<<res<<" ";
    }
    cout<<endl;
    cout<<res.size()<<endl; //size()返回元素个数
    cout<<res.empty()<<endl; //empty()返回是否为空
    res.clear();            //clear()清空数组
    cout<<res.empty()<<endl;
    for(int i = 1;i <= 5;i++)
    {
        res.push_back(i); //push_back()中加入元素
    }
    for(int i = 0;i < 5;i++)
    {
        cout<<res<<" ";
    }
    cout<<endl;
    int k = 5;
    while(k--)
    {
        res.pop_back(); //pop_bcak()中弹出元素
    }
    cout<<res.size();
    cout<<endl;
    vector<int>::iterator it;
    for(auto it = a.begin();it != a.end();it++)  //begin()得到数组的头指针
    {                                           //end()得到数组的尾指针+1
        cout<<*it<<" ";
    }
    cout<<endl;
    cout<<a.front()<<" "; //front()弹出首元素
    cout<<a.back();  //back()弹出元素
}

pair

    pair<int, int>
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

pair<T1, T2> p1;            //创建一个空的pair对象（使用默认构造），它的两个元素分别是T1和T2类型，采用值初始化。
pair<T1, T2> p1(v1, v2);    //创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2。
make_pair(v1, v2);          // 以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型。
p1 < p2;                    // 两个pair对象间的小于运算，其定义遵循字典次序：如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回true。
p1 == p2；                  // 如果两个对象的first和second依次相等，则这两个对象相等；该运算使用元素的==操作符。
p1.first;                   // 返回对象p1中名为first的公有数据成员
p1.second;                 // 返回对象p1中名为second的公有数据成员示例：
int a = 8;
string m = "James";
pair<int, string> newone;
newone = make_pair(a, m);
cout << newone.first << newone.second << endl;
//output: 8 James
string

size()/length()          返回字符串长度
empty()           判空
clear()          清空
substr(起始下标，(子串长度))       返回子串
c_str()          返回字符串所在字符数组的起始地址
reverse(s.begin(),s.end())             将字符串的[begin, end)的元素进行反转
append(),        用于向string的后面追加字符或字符串，在string后面添加多个相同字符，例str.append(3,'!');
字符数组char name[3]之间的赋值strcpy(a,b)

queue, 队列

先进先出

    size()     返回队列长度
    empty() 判空
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素

priority_queue, 优先队列，默认是大根堆

std::priority_queue:在优先队列中，优先级高的元素先出队列，并非按照先进先出的要求，类似一个堆(heap)。其模板声明带有三个参数，priority_queue<Type, Container, Functional>, 其中Type为数据类型，Container为保存数据的容器，Functional为元素比较方式。Container必须是用数组实现的容器，比如 vector, deque. STL里面默认用的是vector. 比较方式默认用operator< , 所以如果把后面两个参数缺省的话，优先队列就是大顶堆，队头元素最大。
**priority_queue()，默认按照从小到大排列。所以top()返回的是最大值而不是最小值！
使用greater<>后，数据从大到小排列，top()返回的就是最小值而不是最大值！
如果使用了第三个参数，那第二个参数不能省，用作保存数据的容器！！！！**

> priority_queue<int, greater<>> pq;//这是错误的
> priority_queue<int,vector< int > , greater<>> pq;//这是对的

    size()   返回大小
    empty()  判空
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
    优先队列的时间复杂度为O（logn），n为队列中元素的个数，其存取都需要时间。

>  产生原因：同样是为了提高数据处理的效率。试想，要实现优先队列对应的功能，若使用链表或者数组，那么要么先排序再插入，要么先插入再查找最大最小元素。这样一来，入队出队的时间复杂度至少为O(N)。

大根堆和小根堆的示例如下：
#include <bits/stdc++.h>
using namespace std;
int main()
{
        vector<int> aa = { 1,2,4,3,8,6,1,4 };
        priority_queue<int, vector<int>, greater<int>> pq;//小根堆, vector<int>
        priority_queue<int>pq2;    //大根堆
        for (int i = 0; i < aa.size(); i++) {
                pq.push(aa);
                pq2.push(aa);
        }
        for (int i = 0; i < aa.size(); i++){
                cout << pq.top();
                pq.pop();
        }
        cout<<endl;
        for(int i=0;i<aa.size();i++){
                cout<<pq2.top();
                pq2.pop();
        }
        //cout << pq << endl;
        system("pause");
        return 0;
}stack, 栈

    size()   返回栈的大小
    empty()   返回栈是否为空
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

deque, 双端队列

双端队列(deque)是一种随机访问的数据类型,提供了在序列两端快速插入和删除的功能,deque类似于vector。

    size()  返回deque的大小
    empty()   返回deque是否为空
    clear()    返回是否为空
    front()/back()    获取双端队列中第一个/最后一个元素
    begin()/end()   双端队列中第一个元素/最后一个元素的引用
    push_back()/pop_back()   在双端队列的后面增加/删除最后一个元素
    push_front()/pop_front()     在双端队列的前面增加/删除第一个元素     
    []

set, map, multiset, multimap,

基于平衡二叉树（红黑树），动态维护有序序列.

    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)

set/multiset

        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器

set的定义方式
set<int> s1; //构造int类型的空容器
set<int> s2(s1); //拷贝构造int类型s1容器的复制品
string str("abcdef");
set<char> s3(str.begin(), str.end()); //构造string对象某段区间的复制品
set < int, greater<int>> s4; //构造int类型的空容器，比较方式指定为大于
//set中的元素默认按照小于来比较set中的元素不可以重复(因此可以使用set进行去重)。
  multiset容器与set容器的底层实现一样，都是平衡搜索树（红黑树），其次，multiset容器和set容器所提供的成员函数的接口都是基本一致的，multiset容器和set容器的唯一区别就是，multiset允许键值冗余，即multiset容器当中存储的元素是可以重复的。
关于set
set是按照一定次序存储元素的容器，在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但 在底层实际存放的是由<value, value>构成的键值对。set中查找某个元素，时间复杂度为：log2 n。set中的元素不允许修改。
由于multiset容器允许键值冗余，因此两个容器中成员函数find和count的意义也有所不同：

• 成员函数find
  
• set对象 返回值为val的元素的迭代器
  
• multiset对象 返回底层搜索树中序的第一个值为val的元素的迭代器
  
• 成员函数count
  
• set对象 值为val的元素存在则返回1，不存在则返回0（find成员函数可代替）
  
• multiset对象 返回值为val的元素个数（find成员函数不可代替）
  

关于multiset
使用迭代器对multiset中的元素进行遍历，可以得到有序的序列；multiset中的元素不能修改；在multiset中找某个元素，时间复杂度为O(log2 n)。
map/multimap

insert()  插入的数是一个pair
{
map<int ,string> mapstudent;
Mapstudent.insert(make_pair(1,”student_one”);
}
erase()  输入的参数是pair或者迭代器
find()
[]  注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表

用法基本同上面类似，但是底层实现不同，增删改查的时间复杂度是 O(1)
        不支持 lower_bound()/upper_bound()， 迭代器的++，--

树形结构与哈希结构

据应用场景的不同，C++STL总共实现了两种不同结构的关联式容器：树型结构和哈希结构


高频易错问题

Scanf（）输入string类型引发的问题

写在前面，一般不建议使用scanf（）输入string类型，但是这个东西很容易出错，关键是使用scanf输入string类型时，且并没有开辟空间。所以简单介绍一下。
下面是一定正确的版本。
#include<bits/stdc++.h>
using namespace std;
int main(){
        string a;
        a.resize(6); //需要预先分配空间，超出空间会被截取
        scanf("%s",&a[0]);
        cout<<a;//用printf("%s",a.c_str())也可以输出
        return 0;
}下面是会出一些奇奇怪怪的问题的版本。
#include<bits/stdc++.h>
using namespace std;
int main(){
        string a;
        scanf("%s",a.c_str());
        printf("%s",a.c_str());
}分析：上述如果没有预先开辟空间，我们从运行结果上看是正常的，但是如果我们将        printf("%s",a.c_str());改为cout<<a;则输出为空。
在一些情况下我们用scanf)利用刚才上述的方法输入string类型时(scanf("%o",a.c_str())，且并没有开辟空间，如果将输入的sting赋值给其他string类型时，则会出现赋值为空。但仅可以通过Printf(“%s”，A.C_str())；进行输出(cout<a不行)，仅此而已，a实际上仍为空)。因此在对字符串用scanf()进行输入时一定要进行开辟空间。具体底层原因请看下面的常见c_str()常见问题介绍。
printf输出string类型及c_str()函数部分要点

printf只能输出C语言内置的数据，而string不是内置的，只是一个扩展的类，直接输出肯定是错误的！

string test = "测试代码段";
printf("%s",test.c_str());

调用c_str()函数即可进行输出，同时使用cout也可以输出。
1.c_str()函数返回一个指向正规c字符串的指针,内容和string类的本身对象是一样的,通过string类的c_str()函数能够把string对象转换成c中的字符串的样式;
2.c_str()函数返回一个指向正规c字符串的指针, 内容与本string串相同.
这是为了与c语言兼容，在c语言中没有string类型，故必须通过string类对象的成员函数c_str()把string 对象转换成c中的字符串样式。
注意：一定要使用strcpy()函数 等来操作方法c_str()返回的指针

char p[20];
string test="test";
strcpy(p,test.c_str());

独孤客

[赞同][赞同][赞同]

梦想改变生活

最近有这方面的课设，真的有帮助，谢谢楼主[爱]

京博萨斯

hhhh

水公子

[爱]