weownthenight的博客

C++ STL中的常用函数

2021/02/10 C++ 备忘 共 7971 字，约 23 分钟

C／C++函数大全.chm

🔗：https://zh.cppreference.com/w/cpp/header

头文件：algorithm

#include<algorithm>
using namespace std;

  1. lower_bound和upper_bound

    说明：作用在有序数组或容器中，返回指针或迭代器。其中lower_bound返回第一个值大于等于val的元素位置，upper_bound返回第一个值大于val的元素位置。

    应用：PAT A1085/B1030 《机试指南》P167

    lower_bound(first,last,val)

    upper_bound(first,last,val)

    用法举例：

    class MyCalendar {
    set<pair<int, int>> booked;
   
public:
    bool book(int start, int end) {
        auto it = booked.lower_bound({end, 0});
        if (it == booked.begin() || (--it)->second <= start) {
            booked.emplace(start, end);
            return true;
        }
        return false;
    }
};

  2. sort

    sort(A,A+n,cmp)，具体用法解释可见《算法笔记》。

    sort(A.begin(),A.end())，其中A为vector或者string。

  3. min和max

  4. swap

  5. reverse

    reverse(it,it2)可以将数组指针在[it,it2)之间的元素或容器的迭代器在[it,it2)范围内的元素进行反转。也可对string反转。例如：reverse(a.begin(),a.end())

  6. abs

    abs(x)返回绝对值，x为整数。

  7. next_permutation

    给出一个序列在全排列中的下一个序列。在到达全排列的最后一个时会返回false。

  8. fill

    可以把数组或容器中的某一段区间赋为某个相同的值。

头文件：math.h

  1. fabs()

    fabs(x)返回绝对值，其中x是浮点数。

头文件：string.h

  • memset

头文件：vector

#include<vector>
using namespace std;

  1. 定义

    vector<typename> name;
//举例：
vector<int> name;
vector<node> name;
vector<vector<int> >name;
vector<int> vi[100];
//一种非常简洁的定义方法：
vector<vector<int>> left(m,vector<int>(n,0));

  2. 访问

    （1）通过下标访问

    （2）通过迭代器访问

    vector<int>::iterator it=vi.begin();
*(it+i);
for(vector<int>::iterator it=vi.begin();it!=vi.end();it++)
	printf("%d ",*it);
//倒序访问
for(auto it=vi.end()-1;it>=vi.begin();it--)
	printf("%d ",*it);

  3. 常见函数

    1. push_back()

      在vector后面添加一个元素。当添加的元素同样是vector时，可以用以下方式表示：

      vector<vector<int>> res;
res.push_back({left, right})

    2. pop_back()

      删除vector的尾元素。

    3. size()

      获得元素个数

    4. clear()

      清空vector中的元素

    5. insert()

      insert(it,x)向vector任意迭代器it前插入一个元素x.

    6. erase()

      erase(it)删除迭代器为it处的元素

      erase(first,last)删除[first,last)内的所有元素。

      需要注意的是所有erase的做法会使得iterator无效，除非删除的元素在首尾。

    7. resize()

      定义好后设置size，如v.resize(n+1)

    8. back()

      直接得到最后一个元素，可以不用写nums[nums.size()-1]

头文件：list

一般由双向链表实现，插入和删除都是O(1)，但是不能随机访问。

  1. 定义

    与vector类似。

  2. 访问

    和vector类似。

  3. 常见函数

    1. push_front()
    2. push_back()
    3. erase()
    4. pop_front()
    5. pop_back()
    6. front()

头文件：set

#include<set>
using namespace std;

  1. 定义

    与vector相同，大部分STL都是如此定义。

  2. 访问

    除开vector和string之外的STL容器都不支持*(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;
}

    set自动去除重复元素且自动递增排序。

  3. 常见函数

    1. insert()

    2. find()

      set<string> visited;
if(visited.find(cur)==visited.end())
	.......

    3. erase()

    4. size()

    5. clear()

    6. contains() C++20标准才支持

    7. count()

  4. 其他

    multiset解决不需去重的情况，unordered_set解决去重不排序的情况，需要支持C++ 11标准。

  5. 迭代器输出注意的问题：

    #include<set>
set<int> s;
for(auto it=s.begin();it!=s.end();it++){
	if(it!=s.begin())
		printf(" ");
	printf("%d",*it);
}

头文件：string

#include<iostream>     //string类型只能用cin，cout输入输出
#include<string>
using namespace std;

常用函数

  1. insert()

    insert(pos,string)：在pos后插入字符串string

    insert(it,it2,it3)：it为原字符串欲插入的位置，it2和it3为待插字符串的首尾迭代器，用来表示串[it2,it3)将被插在it的位置上。

  2. erase()

    str.erase(it)：用于删除单个元素，it为需要删除的元素的迭代器。

    str.erase(first,last)：其中first为需要删除的区间的起始迭代器，而last则为需要删除的区间的末尾迭代器的下一个地址，也即删除[first,last)。

    str.erase(pos,length)：其中pos为需要开始删除的起始位置，length为删除的字符个数。

    在字符串开头去零：

    while(s.length()!=0&&s[0]=='0')
	s.erase(s.begin());

  3. substr()

    substr(pos,len)返回从pos号位开始、长度为len的子串。也可以用substr(pos),会返回pos开始的字符串。

  4. string::npos

    string::npos是一个常数，其本身的值为-1，但由于是unsigned_int类型，因此实际上也可以认为是unsigned_int类型的最大值。string::npos用以作为find函数失配时的返回值。

  5. find()

    str.find(str2)：当str2是str的子串时，返回其在str中第一次出现的位置；如果str2不是str的子串，那么返回string::npos。

    str.find(str2,pos)：从str的pos号位开始匹配str2，返回值与上相同。

  6. replace()

    str.replace(pos,len,str2)：把str从pos号位开始、长度为len的子串替换为str2。

    str.replace(it1,it2,str2)：把str的迭代器[it1,it2)范围的子串替换为str2.

  7. clear()

    将string清空

  8. c_str()

    用c_str将string转换为char*

  9. to_string()

    string to_string (int val);

    string to_string (long val);

    string to_string (long long val);

    string to_string (unsigned val);

    string to_string (unsigned long val);

    string to_string (unsigned long long val);

    string to_string (float val);

    string to_string (double val);

    string to_string (long double val);

  10. string转int: stoi(string)

  11. 构造函数

    //将string对象初始化为C风格字符串
string one("First constructor!");
//创建一个包含n个元素的string对象，其中每个元素都被初始化为字符c
string two(20,'$');
//将string对象初始化为对象str中从位置pos开始到结尾的字符，或从位置pos开始的n个字符
string three(one,2);
string three(one,2,3);
//将string对象初始化为s指向的NBTS中的前n个字符,即使超过了NBTS结尾
char str[] = "How are you?"
string five(str,5);
strinf five(str,15);
//将string对象初始化为区间[begin,end)内的字符
string six(str+2,str+5)
//如何将一个字符转换为string
string tmp(1, 's')

头文件：map

#include<map>
using namespace std;

  1. 定义

    map<typename1,typename2> mp;

  2. 访问

    map对应映射的值是唯一的，后设的值会覆盖之前的值。

    map会按键值从小到大排序，it→first指当前映射的键，it→second指当前映射的值。

    for(auto it=mp.begin();it!=mp.end();it++){
	cout<<it->first<<" "<<it->second<<endl;
}

  3. 函数

    1. find()

      if(mp.find(str)==mp.end())
		mp[str]=1;

    2. erase()

      mp.erase(it) :it为需要删除的元素的迭代器。

      mp.erase(key)：删除键为key的映射。

      mp.erase(first,last)：删除[first,last)区间的所有元素。

    3. clear()

    4. size()

    5. count()：返回key的个数，实际不是1就是0。可以看作Python中的in来用。

  4. 其他

    map的键和值是唯一的，而如果一个键需要对应多个值，就只能用multimap。C++11标准还增加了unordered_map，比map速度快很多，unordered_map的键值顺序不是按照字典序也不是按照压入顺序存储的，需要注意。

头文件：cctype

#include<unordered_map>
unordered_map<string,int> mp;

  1. isalnum()：

    判断字符是否是数字或者字母

  2. tolower()

    string str="ABC";
for(int i=0;i<str.length();i++)
	str[i]=tolower(str[i]);

头文件：queue

#include<queue>
using namespace std;

  1. 访问

    只能通过front()访问队首元素，通过back()访问队尾元素。对于优先队列，每次队首元素都是优先级最大的，只能通过top()来访问队首元素，即优先级最高的元素。

  2. 常见函数

    1. push()
    2. pop()
    3. empty()
    4. size()
    5. emplace()：原地构造一个元素并插入队列
    6. 清空队列：q=queue();

  3. priority_queue内元素优先级的设置

    1. 基本数据类型的优先级设置

      priority_queue<int> q;       //默认是大根堆
priority_queue<int,vector<int>,less<int> > q;  //数字大的优先级越大
priority_queue<int,vector<int>,greater<int> >q;   //数字小的优先级越大
priority_queue<int,vector<int> ,decltype(&cmp)> q(cmp); //cmp可以自己定义,并且为static

    2. 结构体的优先级设置

      struct fruit{
	string name;
	int price;
	friend bool operator < (fruit& f1,fruit& f2){
			return f1.price>f2.price;         //与sort中的cmp相反，表达的意思是价格低的水果优先级高。
	}
};

    3. 当cmp需要用到外部的数组时，可以利用C++ lambda表达式：

      [ capture-list ] ( params ) -> ret { body }

      其中( params ) -> ret定义了这个匿名函数的参数和返回类型， { body }定义了这个匿名函数的功能，捕捉列表[ capture-list ]是做什么的呢？概括地讲，它使这个匿名函数可以访问外部（父作用域）变量。

      以leetcode上的一个答案代码为例:

      // 这里定义相反，表示的不是优先级，结果应当是小根堆
auto cmp = [&nums1, &nums2](pair<int, int> a, pair<int, int> b) { 
    return nums1[a.first] + nums2[a.second] > 
             nums1[b.first] + nums2[b.second];
};
priority_queue<pair<int, int>, vector<pair<int, int>>, 
    decltype(cmp)> min_heap(cmp);

  4. emplace

    emplace可以实现存储二元组。比如：

    为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组(num,index)，表示元素num在数组中的下标为index。

    class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
				//因为存储的二元组，所以这里的定义是pair
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; ++i) {
						//存储二元组
            q.emplace(nums[i], i);
        }
        vector<int> ans = {q.top().first};
        for (int i = k; i < n; ++i) {
            q.emplace(nums[i], i);
						//q.top().second取出二元组中的第二个元素，用来判断位置
            while (q.top().second <= i - k) {
                q.pop();
            }
            ans.push_back(q.top().first);
        }
        return ans;
    }
};

    使用emplace_back可以将二元组插入到最末尾。

  5. 其他

    实现广度优先搜索时可以用到队列。另外还有双端队列：deuqe与优先队列：priority_queue。优先队列的本质是堆，可以解决一些贪心问题或对Dijkstra算法进行优化。

头文件：deque

deque指双向队列，支持两端的插入和删除元素，并且可以实现随机存取，并且扩展空间比vector的效率更高，不需要复制元素。

  1. 定义

  2. 常用函数

    1. push_back()
    2. push_front()
    3. pop_back()
    4. pop_front()

  3. element access

    可以随机存取。

    1. front()
    2. back()
    3. []

头文件：stack

#include<stack>
using namespace std;

  1. 访问

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

  2. 常用函数

    1. push()
    2. pop()
    3. empty()
    4. size()

  3. 用途

    模拟实现一些递归。

头文件：utility

#include<utility>
using namespace std;

pair

当想要将两个元素绑在一起作为一个合成元素又不想因此定义结构体时可以使用pair。pair只有两个元素：first和second，两个pair类型数据可以直接比较大小，先以first大小为标准，当first相等时就比较second的大小。

  1. pair的创建和初始化

    // pair需要提供两个类型名，类型名不一定相同
pair<string,int> wordcount;
//可以在定义时初始化
pair<string,int> name_age("Tom",18)

  2. 访问pair

    wordcount.first
wordcount.second

  3. make_pair

    pair<int,string> newone;
newone = make_pair(a,m);
//在vector中使用pair
vector<pair<int,int>> p;
p.push_back(make_pair(1,2));

C/C++标准库

  1. auto

需要满足的条件：支持C++11标准

  1. sscanf

sscanf和sprintf的输入和输出都是面向字符串的。

如果sscanf的对象不匹配，只会匹配部分。

例如：想要将str匹配为小数，而样例为aaa，则结果为0.

若样例为1aa，则结果为1；若样例为1.2.3，则结果为1.000.

int n;
char str[100]="123";
sscanf(str,"%d",&n);

int n;
double db;
char str[100]="2048:3.14,hello",str2[100];
sscanf(str,"%d:%lf,%s",&n,&db,str2);
  1. ssprintf
int n=233;
char str[100];
sprintf(str,"%d",n);

int n=12;
double db=3.1415;
char str[100],str2[100]="good";
sprintf(str,"%d:%.2f,%s",n,db,str2);

文档信息

Search

    Table of Contents