变长数组,还可以以邻接表的方式存储图.
重庆分公司
重庆分公司
#includeusing namespace std;
vectorname;
例子
vectorname;
vectorname;
//二维数组
vector>name;
vectorvi[100]; 普通访问,通过下标访问即可
通过迭代器访问
iterator 类似指针,可以实现++it和it++.
vector::iterator it;
//我们有了迭代器it,可以用*it来访问vector里面的元素
vectorvi;
vector::iterator it =vi.begin();
//这里 *(it+i)=vi[i] 除了begin还有end,取的是末尾元素地址的下一位
set翻译为集合，是一个内部自动有序且不含重复元素的容器
setname;
seta[100]; set只能通过迭代器(iterator)访问,由于除开 vector和 string之外的STL容器都不支持*(it+i)的访问方式，因此只能按如下方式枚举：
#include;
using namespase std;
setst;
set.insert(3);
for(set:: iterator it=st.begin();it!=st.end();it++){printf("%d",*it);
} st.insert(x),可将x插入set容器中，并自动递增排序和去重，时间复杂度O(log n)
st.find(value),回set中对应值为value的迭代器，间复杂度O(log n)
set :: iterator it=st.find(3);
st.erase(it)删除it处的元素,it为迭代器,st.erase(value),也可以传入某个值进行删除. st.erase(first,last) 删除[first,last)内的所有元素,注意左开右闭.
st.size() 返回的是st的长度 O(1)
st.clear() 清空st的所有元素,O(n)
set最主要的作用是自动去重并按升序排序，因此碰到需要去重但是却不方便直接开数组的情况，可以尝试用set解决。
3. string 的常见用法详解 3.1 定义用之前记得#include using namespace std
tips
3.2 访问C++要兼容C的标准库，而C的标准库里碰巧也已经有一个名字叫做“string.h”的头文件，包含一些常用的C字符串处理函数，比如strcmp。 这个头文件跟C++的string类半点关系也没有，所以并非
的“升级版本”，他们是毫无关系的两个头文件。 #include
#include
usingnamespace std;
是旧的C 头文件，对应的是基于char*的字符串处理函数；是包装了std 的C++头文件，对应的是新的string 类
1.通过下标访问
如果要读入和输出整个字符串，则只能用cin和cout,也可用 c_str()将 string类型转换为字符数组进行printf输出
2.通过迭代器访问
string::iterator it =str.begin();使用*it访问
3.3 常用函数将两个string直接拼接起来:+ eg: str1=str2+str3;
比较大小可以直接用==, != ,< ,<= ,>,>= 按照字典序排列
返回长度 length()或者size() O(1)
insert() O(N)
erase()
clear() 清空 O(1)
substr(pos, len) 返回从pos号位开始,长度为len的子串
string::npos 是一个常数,本身的值为-1,用来作为find函数失败的返回值
str.find(str2) 当str2是str的子串时,返回其在str中第一次出现的位置.如果str2不是,则返回-1 str.find(str2,pos) 从pos开始匹配
str.replace(pos, len,str2) 把str从pos号位开始,长度为len的子串替换成str2. str.replace(it1,it2,str2) 把str[it1,it2)的子串替换成str2
习题 A1060 转换成科学记数法
map可以将任何基本类型（包括STL容器）映射到任何基本类型（包括STL容器），也就可以建立 string型到int型的映射。
第一个键的类型,第二个是值得类型,字符串到整型的映射必须使用string而不是char数组.
mapmp; 1.通过下标访问
和访问普通的数组是一样的，例如对一个定义为map
2.通过迭代器访问
for(map::iterator it = mp . begin() ; it ! = mp.end();it++){printf("%c %d\n",it->first,it->second);
} map迭代器的使用方式和其他STL容器的迭代器不同，因为map的每一对映射都有两个typename，这决定了必须能通过一个it来同时访问键和值。事实上，map可以使用it->first来访问键，使用it->second来访问值。
map会以键从小到大的顺序自动排序，这是由于map内部是使用红黑树实现的（set也是），在建立映射的过程中会自动实现从小到大的排序功能。
4.3 常用函数1.find(key) 返回键为key的映射迭代器,时间复杂度为O(logN)
2.erase()
3.size()用来获取映射的对数.O(1)
4.clear() 清空元素 O(N)
4.4 常见用途①需要建立字符（或字符串）与整数之间映射的题目，使用map可以减少代码
②判断大整数或者其他类型数据是否存在的题目，可以把map当bool数组用。
③字符串和字符串的映射也有可能会遇到。
延伸：map的键和值是唯一的，而如果一个键需要对应多个值，就只能用 multimap另外，C++11标准中还增加了 unordered_map，以散列代替map内部的红黑树实现，使其可以用来处理只映射而不按key排序的需求，速度比map要快得多
5. queue的常见用法详解 5.1 定义先进先出 的队列
#include
using namespace std;
queue name;
5.2 queue容器内元素访问由于队列(queue)本身就是一种先进先出的限制性数据结构，因此在STL中只能通过front()来访问队首元素，或是通过 back()来访问队尾元素。
5.3 常用函数1.push(x),将x进入队列,时间复杂度O(1)
2.front()来访问队首元素，或是通过 back()来访问队尾元素 O(1)
3.pop() 令队首元素出队,O(1)
4.empty() 检测queue是否为空,返回true则为空,false则非空,O(1)
5.size() 返回个数O(1)
5.4 用途当需要实现广度优先搜索时，可以不用自己手动实现一个队列，而是用 queue作为代替以提高程序的准确性。
另外有一点注意的是，使用 front()和pop()函数前，必须用 empty判断队列是否为空，否则可能因为队空而出现错误。
priority_queue又称为优先队列，其底层是用堆来进行实现的。在优先队列中，队首元素定是当前队列中优先级最高的那一个。当然，可以在任何时候往优先队列里面加入（push）元素，而优先队列底层的数据结构堆（heap）会随时调整结构，使得每次的队首元素都是优先级大的
#include
using namespace std;
priority_queue name;
6.2 容器内元素访问和队列不一样的是，优先队列没有front()函数与 back0函数，而只能通过top()函数来访问队首元素（也可以称为堆顶元素），也就是优先级最高的元素。
6.3 常用函数解析1.push(x),x入队,O(logN)
2.top(),获得队首元素.(堆顶元素),O(1)
3.pop(),令队首元素(堆顶元素)出队,O(logN)
4.empty() 检测queue是否为空,返回true则为空,false则非空,O(1)
5.size() 返回个数O(1)
6.4元素优先级设置1.基本数据类型的优先级设置
此处指的基本数据类型就是int型、 double型、char型等可以直接使用的数据类型，优先队列对它们的优先级设置一般是数字大的优先级越高，因此队首元素就是优先队列内元素大的那个（如果char型，则是字典序大的）。对基本数据类型来说，下面两种优先队列的定义是等价的（以int型为例，注意最后两个>之间有一个空格）
大顶堆
priority_queueq;
priority_queue, less>q; 可以发现，第二种定义方式的尖括号内多出了两个参数：一个是 vector，另一个是less。其中 vector（也就是第二个参数）填写的是来承载底层数据结构堆(heap)的容器，如果第一个参数是 double型或char型，则此处只需要填写 vector< double>或 vector；而第三个参数 less则是对第一个参数的比较类， less表示数字大的优先级越大，而greater表示数字小的优先级越大.
让最小的元素放在队首
小顶堆
priority_queue, greater>q; 2.结构体的优先设置
希望按水果的价格高优先级高,需要重载小于号<.
优先队列的这个函数与sort中的cmp函数的效果是相反的。
struct fruit{string name;
int price;
friend bool operator< (fruit &f1, fruit &f2){//建议引用
return f1.priceq; 定义在外面也可以
6.5 用途可以解决贪心问题,也可以对dijkstra进行优化.
7. stack 的常见用法详解 7.1 定义#include
using namespace std;
stack name;
7.2 元素访问只能通过top()来访问栈顶元素.因为他是先进后出的数据结构
7.3 常用函数解析1.push(x)入栈 O(1)
2.pop() 出栈 O(1)
3.top()获得栈顶元素,O(1)
4.empty() 检测stack是否为空,返回true则为空,false则非空,O(1)
5.size() 返回元素个数 O(1)
7.4 常见用途stack用来模拟实现一些递归，防止程序对栈内存的限制而导致程序运行出错。
8.pair的常见用法详解 8.1 定义pair,当想要将两个元素绑在一起作为一个合成元素、又不想此定义结构体时，使用pair可以很方便地作为一个代替品。也就是说，par实际上可以看作一个内部有两个元素的结构体，且这两个元素的类型是可以指定的，如下面的短代码所示
struct pair{typename1 first;
typename2 second;
};#includeusing namespace std;
pairp;
pairp;
pairp("haha",5);
pair("haha",5);
make_pair("haha",5); 用p.first和p.second访问
8.3 常用函数解析比较操作数
两个pai类型数据可以直接使用=、!=、<、<、>>比较大小，比较规则是先以frst的大小作为标准，只有当frst相等时才去判别 second的大小
8.4 常见用途①用来代替二元结构体及其构造函数，可以节省编码时间
②作为map的键值对来进行插入
mp.insert(make_pair("haha",5));max（x,y）和min（x,y）分别返回x和y中的大值和最小值，且参数必须是两个（可以是浮点数）。如果想要返回三个数x、y、z的大值，可以使用max（x,max（y,z）的写法。
abs(x)返回x的绝对值。注意：x必须是整数，浮点型的绝对值请用math头文件下的fabs.
swap() 交换两个数
reverse(): reverse（it, it2）可以将数组指针在**[it,it2)**之间的元素或容器的迭代器在[it,i2)范围内的元素进行反转。
int a[10]={10,11,12,13,14,15};
reverse(a,a+4);
//输出 13 12 11 10 14 1next_permutation() 给出一个序列在全排列中的下一个序列。
fill() fill()可以把数组或容器中的某一段区间赋为某个相同的值。和 memset不同，这里的赋值可以是数组类型对应范围中的任意值。
sort() 排序 前面讲过了
lower_bound() 和upper_bound()
lower_bound（ first, last，val）用来寻找在数组或容器的[first,last)范围内第一个值大于等于val的元素的位置，如果是数组，则返回该位置的指针；如果是容器，则返回该位置的迭代器。upper_bound() 返回第一个大于val.如果没找到,则返回可以插入该元素的位置的指针或迭代器.
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
