C++模板库STL介绍——浅显理解-创新互联

1. vector的常见用法详解 1.1定义

变长数组,还可以以邻接表的方式存储图.

创新互联公司是一家专注于成都网站建设、网站制作与策划设计,临夏州网站建设哪家好?创新互联公司做网站,专注于网站建设10多年,网设计领域的专业建站公司;建站业务涵盖:临夏州等地区。临夏州做网站价格咨询:18982081108

#includeusing namespace std;
vectorname;

例子

vectorname;
vectorname;
//二维数组
vector>name;
vectorvi[100];

1.2 vector容器内元素的访问

1. 普通访问,通过下标访问即可

2. 通过迭代器访问

   iterator 类似指针,可以实现++it和it++.

   vector::iterator it;
   //我们有了迭代器it,可以用*it来访问vector里面的元素
   vectorvi;
   vector::iterator it =vi.begin();
   //这里  *(it+i)=vi[i]

   除了begin还有end,取的是末尾元素地址的下一位

1.3 常用函数

1. vi.push_back(i) 在vector后面添加一个元素i,O(1)
2. vi.pop_back(i) 删除vector的尾元素 O(1)
3. vi.size() 返回的是vi的长度 O(1)
4. vi.clear() 清空vi的所有元素,O(n)
5. vi.insert(it,x) 在迭代器it处插入一个元素x,O(n)
6. vi.erase(it) 删除it处的元素,vi.erase(first,last) 删除[first,last)内的所有元素,注意左开右闭

1.4 常见用途

1. vector本身可以作为数组使用，而且在一些元素个数不确定的场合可以很好地节省空间
2. 有些场合需要根据一些条件把部分数据输出在同一行，数据中间用空格隔开。由于输出数据的个数是不确定的，为了更方便地处理最后一个满足条件的数据后面不输出额外的空格，可以先用 vector记录所有需要输出的数据，然后一次性输出。

2. set的常见用法详解 2.1 set的定义

set翻译为集合，是一个内部自动有序且不含重复元素的容器

setname;
seta[100];

2.2 set容器内元素访问

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);
}

2.3 set常用函数

1. st.insert(x),可将x插入set容器中，并自动递增排序和去重，时间复杂度O(log n)

2. st.find(value),回set中对应值为value的迭代器，间复杂度O(log n)

   set :: iterator it=st.find(3);

3. st.erase(it)删除it处的元素,it为迭代器,st.erase(value),也可以传入某个值进行删除. st.erase(first,last) 删除[first,last)内的所有元素,注意左开右闭.

4. st.size() 返回的是st的长度 O(1)

5. st.clear() 清空st的所有元素,O(n)

set最主要的作用是自动去重并按升序排序，因此碰到需要去重但是却不方便直接开数组的情况，可以尝试用set解决。

3. string 的常见用法详解 3.1 定义

用之前记得#include using namespace std

tips

C++要兼容C的标准库，而C的标准库里碰巧也已经有一个名字叫做“string.h”的头文件，包含一些常用的C字符串处理函数，比如strcmp。 这个头文件跟C++的string类半点关系也没有，所以并非的“升级版本”，他们是毫无关系的两个头文件。

#include
#include
usingnamespace std;

是旧的C 头文件，对应的是基于char*的字符串处理函数；是包装了std 的C++头文件，对应的是新的string 类

3.2 访问

1.通过下标访问

如果要读入和输出整个字符串，则只能用cin和cout,也可用 c_str()将 string类型转换为字符数组进行printf输出

2.通过迭代器访问

string::iterator it =str.begin();使用*it访问

3.3 常用函数

1. 将两个string直接拼接起来:+ eg: str1=str2+str3;

2. 比较大小可以直接用==, != ,< ,<= ,>,>= 按照字典序排列

3. 返回长度 length()或者size() O(1)

4. insert() O(N)

   • insert(pos,string) 在pos位置插入string
   • insert(it, it2,it3) it为原字符串欲插入位置,it2和it3为待插入字符串的收尾迭代器,用来表示串[it2,it3)将插在it的位置上

5. erase()

   • 删除单个元素erase(it) it为迭代器
   • 删除一个区间的 erase(pos,length) pos为起始位置,length为字符个数

6. clear() 清空 O(1)

7. substr(pos, len) 返回从pos号位开始,长度为len的子串

8. string::npos 是一个常数,本身的值为-1,用来作为find函数失败的返回值

9. str.find(str2) 当str2是str的子串时,返回其在str中第一次出现的位置.如果str2不是,则返回-1 str.find(str2,pos) 从pos开始匹配

10. str.replace(pos, len,str2) 把str从pos号位开始,长度为len的子串替换成str2. str.replace(it1,it2,str2) 把str[it1,it2)的子串替换成str2

    习题 A1060 转换成科学记数法

4. map的常用用法详解 4.1 定义

map可以将任何基本类型（包括STL容器）映射到任何基本类型（包括STL容器），也就可以建立 string型到int型的映射。

第一个键的类型,第二个是值得类型,字符串到整型的映射必须使用string而不是char数组.

mapmp;

4.2 容器内元素的访问

1.通过下标访问

和访问普通的数组是一样的，例如对一个定义为mapmp的map来说，就可以直接使用mp[‘c’]的方式来访问它对应的整数。于是，当建立映射时，就可以直接使用mp[‘c’]=[20]这样和普通数组一样的方式。但是要注意的是，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()

• 删除单个元素 mp.erase(it) ,it为需要删除的元素的迭代器,时间复杂度O(1),或者mp.erase(key) ,key为欲删除的映射的键,复杂度为O(logN)
• 删除区间内的元素 mp.erase(first,last)删除的是[first,last).

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判断队列是否为空，否则可能因为队空而出现错误。

6 优先队列priority_queue 常见用法详解 6.1 定义

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);

8.2 元素访问

用p.first和p.second访问

8.3 常用函数解析

比较操作数

两个pai类型数据可以直接使用=、!=、<、<、>>比较大小，比较规则是先以frst的大小作为标准，只有当frst相等时才去判别 second的大小

8.4 常见用途

①用来代替二元结构体及其构造函数，可以节省编码时间
②作为map的键值对来进行插入

mp.insert(make_pair("haha",5));

9. algorithm 头文件下的常用函数

1. max(),min(),abs()

max（x,y）和min（x,y）分别返回x和y中的大值和最小值，且参数必须是两个（可以是浮点数）。如果想要返回三个数x、y、z的大值，可以使用max（x,max（y,z）的写法。
abs(x)返回x的绝对值。注意：x必须是整数，浮点型的绝对值请用math头文件下的fabs.

2. swap() 交换两个数

3. 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 1

4. next_permutation() 给出一个序列在全排列中的下一个序列。

5. fill() fill()可以把数组或容器中的某一段区间赋为某个相同的值。和 memset不同，这里的赋值可以是数组类型对应范围中的任意值。

6. sort() 排序 前面讲过了

7. lower_bound() 和upper_bound()

   lower_bound（ first, last，val）用来寻找在数组或容器的[first,last)范围内第一个值大于等于val的元素的位置，如果是数组，则返回该位置的指针；如果是容器，则返回该位置的迭代器。upper_bound() 返回第一个大于val.如果没找到,则返回可以插入该元素的位置的指针或迭代器.

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文名称：C++模板库STL介绍——浅显理解-创新互联
分享网址：http://6mz.cn/article/jpjei.html