Top

本地磁盘小日记ヾ(≧▽≦*)ゝ

世界无限大.且行且珍惜w~
编码.计算机科学与视觉.语言.美术在学/MTF/喜爱创作/不良公主w;

教程:关于C++标准模板库STL的快速上手(1);

在C语言中当我们需要实现一些功能(例如一些排序等算法或迭代器之类的)都是需要自己想办法去实现。为惹解决这一不便之处,C++为使用者提供惹一套强大的标准模板库(StandardTemplateLibrary),把一些容器(Containers)、算法(Algorithms)、迭代器(iterators)等实用功能通过模板来进行封装成容器,提供惹通用的模板类和函数可以直接拿来用。

本篇(1)为大家介绍:vector、set、string、map、queue。


C++标准模板库的三大核心组件;

容器(Containers):
用来管理某一类对象的集合。C++ 提供了各种不同类型的容器,比如 deque、list、vector、map 等。

算法(Algorithms):
算法是作用于容器的。它们提供了执行各种操作的方式,包括对容器内容执行初始化、排序、搜索和转换等操作。

迭代器(iterators):
用于遍历对象集合的元素。这些集合可能是容器,也可能是容器的子集。


vector

vector是可变长数组,顾名思义,它是那种长度可以根据需要而自动改变的数组。它可以避免普通数组可能会超内存的问题,而且它还可以用来以邻接表方式存储图,免去惹使用指针实现邻接表比较麻烦的烦恼。

  • vector的引用
1
2
using namespace std;
#include <vector>
  • vector的定义
1
2
单独定义一个vector:
vector<typename> name;

和一维数组一样,这里的typename可以是任何基本类型(如int、double、char、结构体等),也可以是STL的标准容器(如vector、set、queue等)。不过需要注意的是,如果是STL标准容器的话定义的时候要记得在>>符号之间加上空格。因为一些使用C++11之前标准的编译器会把它视为移位操作。例如:

1
2
3
4
vector<int> name;
vector<char> name;
vector<node> name;  //node是结构体的类型
vector<vector<int> > name;   //如果是STL的话定义时>>之间记得要加空格
1
2
vector<typename> Arrayname[arraySize];
vector<int> vi[100];    //这样Arrayname[0]~Arrayname[arraySize-1]中每一个都是vector容器。
  • vector容器内元素访问

(1)通过下标访问: 和访问普通数组一样,例如:

1
2
vector<typename> vi;
vi[index];  //如vi[0]这样访问即可

下标为从0到vi.size()-1。

(2)通过迭代器访问:

迭代器可以理解为一种类似指针的东西:

1
vector<typename>::iterator it;

这样it就是一个迭代器变量,typename就是定义vector时填写的类型:

1
vector<int>::iterator it;

这样就得到了迭代器it,并且可以通过*it来访问vector里的数组。 例如有这样一个vector容器:

1
2
3
for(int i1;i<=5;i++){
    vi.push_back(i);
}

可以通过类似下标和指针访问数组的方式来访问容器内的元素:

1
2
3
4
vector<int>::iterator it=vi.begin();
for(int i=0;i<5;i++){
    printf("%d",*(it+i));
}

输出结果:1 2 3 4 5 从这里看出vi[i]和*(vi.begin()+i)是等价的。

begin()函数的作用是去vi首元素的地址,end()函数是取尾元素地址的下一个地址。end()作为迭代器末尾标准,不存储任何元素。

除此之外,迭代器还实现了两种自加自减操作:

1
2
++it和it++
--it和it--

于是有了另一种遍历vector中元素的写法:

1
2
3
for(vector<int>)::iterator it=vi.begin();it!=vi.end();it++){
    printf("%d",*it);
}

最后需要指出,在常用STL容器中,只有在vector和string中,才允许使用vi.begin()+3这种迭代器加上整数的写法。

  • vector的常用函数实例解析

(1)push_back(): 顾名思义,push_back(x)就是在vector后面添加一个元素x,时间复杂度为O(1)。

1
vi.push_back(i);    //将1、2、3依次插入vi末尾

(2)pop_back(): pop_back()用以删除vector的尾元素,时间复杂度为O(1)。

1
vi.pop_back();  //删除vi的尾元素3

(3)size(): size()用来获得vector中元素的数组,时间复杂度为O(1)。size()返回的是unsigned类型,不过一般来说用%d不会出很大的问题,这一点对所有STL容器都是一样的。

1
printf("%d",vi.size());

(4)clear(): clear()用来清空vector中的所有数组,时间复杂度为O(N),其中N为vector中元素的个数。

1
vi.clear()

(5)insert(): insert(it,x)用来向vector的任意迭代器it处插入一个元素x,时间复杂度O(N)。

1
vi.insert(vi.begin()+2,-1);

(6)erase(): erase()有两种用法:删除单个元素、删除一个区间内所有有元素。时间复杂度为O(N)。

1
2
删除单个元素:
vi.erase(vi.begin()+3);
1
2
删除一个区间内的所有元素:
vi.erase(vi.begin()+1,vi.begin()+4);

set

set是一个内部自动有序且不含重复元素的容器。加入set后可以实现去掉重复元素,还可以用set来保留元素本身而不考虑它的个数。所谓关联容器就是通过键(key)来读取和修改元素。与map关联容器不同,它只是单纯键的集合。

  • set的引用
1
2
using namespace std;
#include <set>
  • set的定义
1
2
单独定义一个set:
set<typename> name;
1
2
3
4
5
set<int> name;
set<char> name;
set<node> name;  //node是结构体的类型
set<vector<int> > name;   //如果是STL的话定义
set<vector<int> > name;   //如果是STL的话定义时>>之间记得要加空格
  • set容器内元素访问
1
2
3
4
5
6
7
8
9
10
set只能通过迭代器访问:
set<typename>::iterator it;

例如:
set<int>::iterator it;
set<char>::iterator it;

这样就得到了迭代器it,并可通过*it来访问set里元素:
for(set<int>::iterator it=st.begin(); it!=st.end(); it++)
{ printf("%d",*it); }
  • set的常用函数实例解析

(1)insert(): insert(x)可将x插入set容器中,并自动递增排序和去重,时间复杂度O(logN),其中N为set内的元素个数。

(2)find(): find(value)返回set中对应值为value的迭代器,时间复杂度O(logN),N为set内的元素个数。

1
set<int>::iterator it=st.find(2);

(3)eraser():

1
2
3
4
删除单个元素:
st.eraser(it);   //it为所需要元素的迭代器
st.eraser(st.find(100));    //利用find查找并删除
st.eraser(100);   //删除set中值为100的元素
1
2
3
删除一个区间内所有元素:
st.eraser(first,last);
st.eraser(it,st.end());

(4)size(): size()用来获得set内元素个数,时间复杂度O(1)。

1
printf("%d/n",st.size());

(5)clear: clear()用来清空set内所有元素,复杂度O(N)。

1
st.clear();

String

C++相对于C在STL中加入惹string类型,对字符串常用的需求功能进行了封装,是的操作起来更方便,且不易出错。

  • string的引用:
1
2
using namespace std;
#include <string>
  • string的定义:
1
2
string str;
string str="abcd";
  • string容器内元素访问:

(1)通过下标访问:

1
2
3
4
5
6
7
8
9
10
11
12
13
string str="abcd";
for(int i=0;i<str.length();i++){
    printf("%c",str[i]);
}

如果要读入和输出整个字符串,只能用cin和cout:
string str;
cin>>str;
cout<<str;

或用c_str()将sting类型转换为字符串数组类型:
string str="abcd";
printf("%s\n",str.c_str());

(2)通过迭代器访问:

1
2
3
4
5
6
7
string::iterator it;

这样就可以通过*it来访问string的每一位:
for(string::iterator it=str.begin();it!=str.end();it++){
    printf("%c",*it);
}
string也支持对迭代器进行加减某个数字,如str.begin()+3。
  • String常用函数实例解析:

(1)operator+=: 这是string的加法,可以讲两个string拼接起来。

1
2
3
string str1="abc",str2="xyz",str3;
str3=str1+str2;
str1+=str2;

(2)computer operation: 两个string类型可以直接用==、!=、<、<=、>、>=比较大小,比较规则是字典序。

1
2
3
if(str1<str2)   printf("ok1\n");
if(str1!=str3)  printf("ok2\n");
if(str4>=str3)  printf("ok3\n");

(3)length()/size(): length()返回string长度,即存放字符数,时间复杂度O(1)。size()与length()基本相同。

1
2
string str="abcdxzy";
printf("%d %d\n",str.length(),str.size());

(4)insert():

1
2
3
4
5
insert(pos,string);  //在pos号位置插入字符串string。
str.insert(3,str2);

insert(it1,it2,it3);    //it为原字符串的欲插入位置,it2和it3为代插字符串的首尾迭代器,用来表示串[it2,it3)将被插在it的位置上。
str.insert(str.begin()+3,str2.begin(),str2.end());

(5)eraser:

1
2
3
删除单个元素:
str.eraser(it);
str.eraser(str.begin()+4);
1
2
3
4
5
6
删除一个区间内所有元素:
str.eraser(first,last);
str.eraser(str.begin()+2,str.end()-1);

str.eraser(pos,length);
str.eraser(3,2);

(6)clear: clear()用以清空string中的数据,时间复杂度一般为O(1)。

1
str.clear();

(7)substr(): substr(pos,len)返回从pos号位开始、长度为len的字串,时间复杂度为O(len)。

1
2
3
cout<<str.substr(0,5)<<endl;
cout<<str.substr(14,4)<<endl;
cout<<str.substr(19,5)<<endl;

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

1
2
3
4
5
6
if(string::npos==-1){
    cout<<"-1 is true."<<endl;
}
if(string::npos==4294967295){
    cout<<"4294967295 is also true."<<endl;
}

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

str.find(str2,pos),从str2的pos号位开始匹配str2,返回值与上相同。时间复杂度为O(nm)。

1
2
3
if(str.find(str2)!=string::npos){
    cout<<str.find(str2)<<endl;
}

(10)replace(): str.replace(pos,len,str2)把str从pos号位开始、长度为len的子串替换为str2。 str.replace(it1,it2,str2)把str的迭代器[it1,it2)范围的子串替换为str2。时间复杂度O(str.length())。

1
cout<<str.replace(10,4,str2)<<endl;

Map

map翻译为映射。在定义数组时,其实是定义了一个从int型到int型的映射。一个double型数组则是将int型映射到double型。无论是什么类型,它总是将int型映射到其他类型。当需要以其它类型作为关键字来做映射时,会显得不太方便。但通过map可以将任何基本类型(包括STL容器)映射到任何基本类型(包括STL容器),也就可以建立string型到int型的映射。

  • map的引用:
1
2
using namespace std;
#include <map>
  • map的定义:
1
2
3
4
单独定义一个set:
map<typename1,typename2> mp;
map的键和值也可以是STL容器:
map<set<int>,string> mp;
  • map容器内元素访问:

(1)通过下标访问:

1
2
map<char,int> mp;
mp['c']=20;

(2)通过迭代器访问:

1
2
3
4
5
map<typename1,typename2>::iterator it;

for(map<char,int>::iterator it=mp.begin();it!=mp.end();it++){
    printf("%c %d\n",it->first,it->second); //it->first访问键,it->second访问值
}

map会以键从小到大的顺序自动排序,这是由于map内部是使用红黑树实现的(set也是)。

  • Map常用函数实例解析:

(1)find(); find(key)返回键为key的映射的迭代器,时间复杂度为O(logN)。

1
2
map<char,int>::iterator it=mp.find('b');
printf("%c %d\n",it->first,it->second);

(2)eraser():

1
2
3
4
5
删除单个元素:
mp.erase(it);
//it为需要删除的元素的迭代器。
mp.erase(key);
//key为欲删除的映射的键。
1
2
3
4
5
删除一个区间内的所有元素:
mp.erase(first,last);
//first为需要删除的区间的起始迭代器,last为需要删除的区间的末尾迭代器的下一个地址。
mp.erase(it,mp.end());
//删除it之后的所有映射。

(3)size(): size()用来获得map中映射的对数,时间复杂度为O(1)。

1
2
mp['a']=10;
printf("%d\n",mp.size());

(4)clear(): clear()用来清空map中所有的元素,复杂度为O(N)。

1
2
mp['a']=1;
mp.clear();

queue

queue翻译为队列,是一个先进先出的容器。

  • queue的引用:
1
2
using namespace std;
#include <queue>
  • queue的定义:
1
2
queue<typename> name;
  • queue容器内元素访问:

由于queue是一种先进先出的限制性数据结构,因此在STL中只能通过front()访问队首元素,或通过back()访问队尾元素:

1
2
3
4
5
queue<int> q;
for(int i=1;i<=5;i++){
    q.push(i);
}
printf("%d %d\n",q.front(),q.back());
  • Map常用函数实例解析:

(1)push: push(x)将x进行入队,时间复杂度为O(1)。

1
q.push(i);

(2)front()、back(): 两者可以分别获得队首元素和队尾元素,时间复杂度为O(1)。

1
printf("%d %d\n",q.front(),q.back());

(3)pop(): pop()令队首元素出队,时间复杂度为O(1)。

1
2
3
for(int i=1;i<=3;i++){
    q.pop();
}

(4)empty(): empty()检测queue是否为空,返回true则空,返回false则非空。时间复杂度为O(1)。

1
2
3
4
queue<int> q;
if(q.empty()==true){
    printf("Empty\n");
}

(5)size: size()返回queue内元素的个数,时间复杂度为O(1)。

1
printf("%d\n",q.size());

未完待续


@本地磁盘姬

ohayou.aimo.moe

微博:@本地磁盘姬碟酱

Twitter:本地磁盘姬改二

知乎:本地磁盘姬

2020年07月13日