vector在竞赛中的应用

发表于 2021-04-21

vector在竞赛中的应用

优先队列（priority_queue)

特点

在队尾删除元素
在队头添加元素
每次取出的是具有最高优先权的元素（不一定先进先出）
访问最优元素：队列名.top

栈的应用

先进后出

特点

栈顶删除/加入

创建栈对象：stack<元素类型> 栈名；
栈顶==添加==元素：栈名.push(元素名)；
==删除==栈顶元素：栈名.pop();
==访问==栈顶元素：栈名.top();
判断是否为空：栈名.empty();
返回栈的大小：栈名.size();

栈和队列一样，没有clear之类的清空函数，只能循环调用==出栈函数==

vector的应用

vector(向量，==动态数组==)

1.向量的定义：vector< int > a;

2.向量初始化

vector< int > abc;//初始化一个size为0的vector

//初始化size，但每个元素为0

vector< int > abc(10);//初始化了10个默认值为0的元素

//初始化size，并设置初始值

vector< int > cde(10,1);//初始化10个为1的元素

基本用法

取向量==首元素的迭代器==：向量名.begin();
取向量==尾元素下一地址==:向量名.end ();
取向量==首元素的值==:向量名.front ();
取向量==尾元素的值==:向量名.back() ;
==下标==形式访问:int value0 =向量名[0];//类似普通数组的访问
往==尾部添加==一个元素:向量名.==push_back(value)==;//最常见操作
==删除尾部==第一个元素:向量名.pop_back() ;
判向量==是否为空==:向量名.empty();
求向量==元素个数==:向量名.size();//实际元素个数，不是容量
==翻转==向量: reverse(a.begin() , a.end () );

STL中vector的经典应用-==邻链表==

struct edge{int form,to,value;}//定义边

const int maxn =1e5+5;

vector< edge > Map[maxn];//一维向量相当于二维数组

若用普通二维数组存邻链表，需要1e10的空间开销，而如果图中实际变数只有1e6，无疑会造成空间浪费（超内存）。

set集合

set含义就是集合，他是一个==有序==的容器，里面的元素都是==排序好==的，支持插入，删除，查找等操作，所有的操作都是严格在log^n

时间内完成，效率高。

set的声明： set< int > s;
set的清空： s.clear();
插入一个元素x： s.insert();

//==如果集合中之前没有，则插入成功并自动排序，否则不插入==
查询是否有元素x： int hav=s.count(x);//返回0或1
查找x并返回迭代器：set< int >::iterator it=s.find(x);
判断是否为空集 bool isempty=s.empty();
求集合元素个数:int n=s.size();
删除元素x:s.erase(x);

set的基本用法

set的主要用途：自动==去重==并按==升序==排序

set只能通过迭代器（iterator）访问

string类

一、string对象声明

string str;
string str1=”wjdnkk”;

二、求string对象长度

string strTest=”test”;
strTest.length();//返回4
strTest.size();//返回4

三、string对象的链接

可以使用+和+=运算符对string对象执行字符串连接操作，（还有append成员函数实现字符串的连接）

四、string对象的比较

可以用<,<=,==,!=,>=,>运算符比较string对象，（患有compare成员函数用于比较字符串）

五、求string对象的子串

substr成员函数可以用于求字串（n,m)；

调用时，如果省略m或m超过字符串长度，则求出来的字串就是从下标n开始一直到字符串结束的部分

string s1=”this is ok”;
string s2=s1.substr(2,4);//s2=”is i”下标为2取4个
s2=s1.substr(2);//s2=”is is ok”从2到最后

六、插入字符串

insert成员函数可以在string对象中插入另一个字符串，返回值为对象自身的引用。

string s1(“Limitless”),s2(“00”);
s1.insert(2,”123”); //s1=”Lil23mitless”
s1.insert(3.s2); //s1=”Lil0023mitless”
s1.insert(3,5,’X’); //s1=”LilXXXXX0023mitless”

七、删除字串

erase成员函数可以删除string对象中的子串，返回值为对象自身的引用。

string s1(“Real Steel”);
s1.erase(1,3); //s1=”R Steel”
s1.erase(5); //s1=”R Ste”

八、交换两个string对象的内容

swap成员函数可以交换两个string对象的内容；

string s1(“West”),s2(“East”);
s1.swap(s2);

九、字符串的查找操作：

string str=”The apple thinks apple is delicious”;//长度34
string key=”apple”;
int pos1=str.find(key);//4
int pos2=str.find(key,10);//17

==//s.find(str) 查找字符串str在当前字符串s中第一次出现的位置==

==//s.find(str，pos) 查找字符串str在当前字符串s的[pos,end]中第一次出现的位置==

十、用STL算法操作string对象

string s(“afgcbed”);
sort(s.began(),s.end());
cout<<s<<endl; //输出abcdefg
==next_permutation==(s.began(),s.end());求下一个字符串
cout<<s<<endl; //输出abcdegf
reverse(s.began(),s.end());//翻转字符串
cout<<s<<endl;//

STL中的==迭代器==

迭代器：遍历容器中数据的对象。对储存于容器中的数据进行处理时，迭代器能==按预先定义的顺序==从一个成员移向另一个成员。
==通过迭代器可以在不了解容器内部原理的情况下遍历容器==

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> ivec;
    vector<int>::iterator iter;
    ivec.push_back(4);
    ivec.push_back(3);
    ivec.push_back(2);
    for(iter=ivec.begin();iter!=ivec.end();iter++)
    {
        cout<<*iter<<endl;
	}
}

STL–map(映射)

map是一个键值对（key/value)容器，对于迭代器来说可以修改value，而不能修改key。==Map会根据key自动排序==

map类型通常可以理解为关联数组：可使用==键作为下标==来获取一个值。关联的本质在于：元素的值与某个特定的键相关联，而并非通过元素在数组中的位置来获取。

map的基本用法

map<int,string> m;//定义一个空map m;
m.count(k);//返回m中键值等于k的元素的个数
m.find(k);//存在则返回指向该元素的迭代器，否则返回结束地址end（）；
m.erase(k);//删除m中==键为k==的元素，但会删除元素的个数（1或0）
m.erase(p);//从m中删除==迭代器p==所指向的元素
m.insert(e);//e是一个用在m上的value_type类型的值（一个pair）

next_permutation

==next_permutation通常用于生成序列的全排列==
int a[]={1,2,3};
do{
cout<<a[0]<<” “<<a[1]<<” “<<a[2]<<endl;
}while(next_permutation(a,a+3));
若当前调用已经到达最大字典序，比如321，则返回函数false