C++ 算法

STL专题

C++

Posted by beansugar on March 6, 2024

pair

pair<T1,T2> p(a,b)//赋值
p = make_pair(a,b)//赋值

作用，当遇到简单的双关键字的排序时，直接用pair实现比较方便,就不用定义结构体了
例如pair<int,string>data
三关键字也可以这么写(不建议这么写，有点臃肿） pair<int,pair<int ,int > sample(1,pair<int ,int >(1,1))
访问也是套娃： cout<< sample.first << sample.second.first << sample.second.second<< endl;

array

比vector快

array<T,5> //类型为T，长度为5的定长数组
auto [p,q,r] = b;//意思为b[0] = r, b[1] = q , b[2] = r

stack(栈)

stack<int > s;
s.top();//查询当亲栈顶元素
s.push(1);//将1压入栈顶
s.pop();//将栈顶元素弹出
s.size();//输出栈中的元素个数
s.empty();//栈为空时返回true

//若想将栈中元素全部弹出可以这么写
while(!s.empty()){
	s.pop();
}

queue(队列)

queue<T> q;
q.push(1);//将1压入队列
p.pop();//队首出队
q.front();//查询队首元素
q.back();//查询队尾元素
q.size();//查询队列中元素个数
q.empty();//若队列为空返回true

//bfs
int main(){
	queue<int> q;
	q.push(s);
	while(q.empty()){
		int x = q.front;
		q.pop();
		for(int y : adj[x]){
			q.push(y);
		}
	}
	
}

优先队列（大根堆）

默认大根堆
小根堆： priority_queue<T ,vector < T >,greater < T > > v;

priority_queue<T> v;
v.push(1);//大根堆中加入1
v.pop();//删除堆顶元素
v.top();//返回堆顶元素

deque双端队列

  • 包含头文件:
    #include <deque>

  • 创建双端队列对象：
    std::deque<T> myDeque;

  • 在队尾插入元素:
    myDeque.push_back(element);

  • 在队头插入元素：
    myDeque.push_front(element);

  • 访问队头和队尾元素： 
    myDeque.front(); // 访问队头元素
myDeque.back();  // 访问队尾元素
  • 删除队头和队尾元素:
myDeque.pop_front(); // 删除队头元素
myDeque.pop_back();  // 删除队尾元素

  • 检查双端队列是否为空:
    myDeque.empty();//为空返回true

  • 获取双端队列的大小：
    myDeque.size();

vector

用于使用动态数组，即 vector 容器

  • 包含头文件：
    #include <vector>

  • 创建vetor对象：
    std::vector<T> myVector;

  • 初始化 vector:
    使用列表初始化：std::vector<int> myVector = {1, 2, 3, 4, 5};
    使用构造函数:std::vector<int> myVector(5, 10); // 创建包含 5 个元素，每个元素的值为 10

  • 访问元素：

使用下标：
int value = myVector[2]; // 获取索引为 2 的元素

重新设置大小：myVector.resize(10);//将该vevtor大小设置为10

使用迭代器：

for (auto it = myVector.begin(); it != myVector.end(); ++it) {
    std::cout << *it << " ";
}

  • 插入元素：
    myVector.push_back(42); // 在 vector 的末尾插入元素

  • 删除元素：
    myVector.pop_back(); // 删除 vector 的末尾元素

  • 获取 vector 的大小：
    std::size_t size = myVector.size();

  • 清空 vector：
    myVector.clear();

  • 判断 vector 是否为空：
    bool isEmpty = myVector.empty();//为空返回true

  • 其他操作：

myVector.front()：获取 vector 的第一个元素。
myVector.end()：寻访地址值-1才是最后一个元素。
//遍历整个指针
for(vector<int>::itrator it = v.begin();it!=v.end();it++){
	printf("%d",x);//irtator为迭代器，也可写成(auto it = v.begin();it!=v.end();it++)
}
//用sort排序
sort(v.begin(),v.end());
myVector.back();//获取 vector 的最后一个元素。
myVector.erase(iterator);//删除指定位置iterator的元素。
myVector.insert(iterator, value);//在指定位置iterator插入元素value。O(n)

//存图
int main()
{
	cin>>n;
	for(int i=1 ; i<=n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
}

//返回大于等于1000的第一个位置,本质上时一个二分查找，该vector需要有序，且不能下标越界
//迭代器访问的时地址，所以需要加上*表示值
auto it = lower_bound(v.begin(),v.end(),1000);
printf("%d",*it);
//返回大于1000的第一个位置,本质上时一个二分查找

set(集合)

独立性，从小到大存
时间复杂度O(logn)

set<int> s;//初始化
vector<int> v{100,1001,3};
set<int> s(v.begin(),v.end());//初始化

s.insert(x);//往集合中插入一个元素x
s.erase(x);//在集合中去除一个元素x
s.count(x);//查询一个数是否存在，若存在返回1.不存在返回0
//另一种判断存不存在
//s.find()方法，若不存在，返回s.end()
auto it = s.find(4);
if(it == s.end()){
	printf("不存在")
}else{
	printf("存在");
}

s.lower_bound(x);//返回key大于等于x的第一个元素的迭代器，若不存在，返回s.end()

//代替堆操作
s.insert(x);//在堆中插入一个元素
*prev(s.end());//访问最大元素
s.erase(prev(s.end()));//删除最大元素

map

map<T1,T2> v;//T1表示下标的类型,T2表示值的类型

map<int,int>v ;

void printm(map<int,int> &s){
	for(auto x: s){
		cout<< x.first << ":" << x.second << endl;
	}
}

int main(){
	v[4239] = 12490;
	v[32590] = 35892;
	v[1000] = 358295;
	printm(v);
	//会按v的下标从小到大输出，即V[1000] : 358295 v[4239] : 12490 v[32590] : 35892
}

v[x] = y;//判断v[x]是不是等于y，若不等于，则新建一个
v.insert(make_pair(x,y));//不常用，有就无法insert
v.erase(x);//erase不存在的元素就会RE
v.count(x);//查询是否存在
v.find(x);//找不到返回v.end()

multiset(元素可重复)

multiset<int> s
v.erase(x)//把所有==x的元素都删除
v.erase(v.find());//删除迭代器
v.count(x)时间复杂度和x的个数有关，慎用

string

string s;//相当于vector<char>s
string s = "123";
int a = stoi(s);//将字符串"123"转成int类型的

int a = 123;
string s = to_string(a);//将int类型的a转化成string类型的

string s = "12345";
s += "67890";//s变成"1234567890"

s.c_str;//将string转化成c的字符串类型

string t = s.substr(1,5);//截取从"1"开始，长度为5的子串

algorithm

int a[] = {1,2,3,4,5};
reverse(a.begin(),a.end())
reverse(a,a+5);//将数组反转a[]={5,4,3,2,1}

rotate(a.begin,a.begin+k,a.end())
rotate(a,a+3,a+5);//将a+3上的数换到a上来

random_shuffle(a.begin,a.end())//c++17后被删除
random_shuffle(a,a + 5);//将数组进行随机打乱

sort(a.begin(),a.end())
sort(a,a+5);//将数组进行排序，本质是快排


a[] = {2, 3, 1, 4, 5};
min_element(a.begin(),a.end())
auto it = min_element(a,a+5);//返回最小元素迭代器的位置
printf("%d %d", *it, it - a);//1 2

max_element(a.begin(),a.end())//返回最大元素迭代器的位置

merge(a.begin(), a.end(), b.begin(), b.end(), c.begin())//将ab归并到c中，前提是ab有序

inplace_merge(a.begin(), a.begin + k, a.end());//a数组内部归并排序

//归并排序
int a[] = {2, 3, 1, 4, 5};
int ms(int l, int r){
	if(l + 1 == r) return;
	mid = (l + r) / 2;
	ms(l, mid);
	ms(mid, r);
	inplace_merge(a, a + mid, a+r);
}

int main(){
	ms(0,5);
	for(int i = 0; i < 5; i++){
		printf("%d", a[i]);
	}
}

nth_element(a.begin(),a.begin()+k,a.end());//表示在数组a中k的位置上，左边都比a[k]小,右边都比a[k]大


bool next_permutation(a.begin(), a.end());//全排列直接改变这个集合，而不是返回一个集合，如果存在这样的“下一个排列”，返回true并执行排列，否则返回false。
//全排列
int a[10];

int main(){
	n = 5;
	for(int i = 0; i < n; i++) a[i] = i + 1;
	while(true){
		for(int i = 0; i < n; i++) printf("%d", a[i]);
		if(!next_permutation(a,a + n)) break;
	}
}
CATALOG
    FEATURED TAGS
    Data Structure