教程:关于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的引用

using namespace std;
#include <vector>

vector的定义

单独定义一个vector：
vector<typename> name;

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

vector<int> name;
vector<char> name;
vector<node> name;  //node是结构体的类型
vector<vector<int> > name;   //如果是STL的话定义时>>之间记得要加空格

vector<typename> Arrayname[arraySize];
vector<int> vi[100];    //这样Arrayname[0]~Arrayname[arraySize-1]中每一个都是vector容器。

vector容器内元素访问

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

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

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

(2)通过迭代器访问：

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

vector<typename>::iterator it;

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

vector<int>::iterator it;

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

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

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

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()作为迭代器末尾标准，不存储任何元素。

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

++it和it++
--it和it--

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

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

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

（2）pop_back()： pop_back()用以删除vector的尾元素，时间复杂度为O(1)。

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

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

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

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

vi.clear()

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

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

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

删除单个元素：
vi.erase(vi.begin()+3);

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

set

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

set的引用

using namespace std;
#include <set>

set的定义

单独定义一个set：
set<typename> name;

set<int> name;
set<char> name;
set<node> name;  //node是结构体的类型
set<vector<int> > name;   //如果是STL的话定义
set<vector<int> > name;   //如果是STL的话定义时>>之间记得要加空格

set容器内元素访问

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内的元素个数。

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

（3）eraser()：

删除单个元素：
st.eraser(it);   //it为所需要元素的迭代器
st.eraser(st.find(100));    //利用find查找并删除
st.eraser(100);   //删除set中值为100的元素

删除一个区间内所有元素：
st.eraser(first,last);
st.eraser(it,st.end());

（4）size()： size()用来获得set内元素个数，时间复杂度O(1)。

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

（5）clear： clear()用来清空set内所有元素，复杂度O(N)。

st.clear();

String

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

string的引用：

using namespace std;
#include <string>

string的定义：

string str;
string str="abcd";

string容器内元素访问：

（1）通过下标访问：

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）通过迭代器访问：

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拼接起来。

string str1="abc",str2="xyz",str3;
str3=str1+str2;
str1+=str2;

（2）computer operation：两个string类型可以直接用==、!=、<、<=、>、>=比较大小，比较规则是字典序。

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()基本相同。

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

（4）insert()：

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：

删除单个元素：
str.eraser(it);
str.eraser(str.begin()+4);

删除一个区间内所有元素：
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)。

str.clear();

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

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函数失配时的返回值。

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

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())。

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

Map

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

map的引用：

using namespace std;
#include <map>

map的定义：

单独定义一个set：
map<typename1,typename2> mp;
map的键和值也可以是STL容器：
map<set<int>,string> mp;

map容器内元素访问：

（1）通过下标访问：

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

（2）通过迭代器访问：

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

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

（2）eraser()：

删除单个元素：
mp.erase(it);
//it为需要删除的元素的迭代器。
mp.erase(key);
//key为欲删除的映射的键。

删除一个区间内的所有元素：
mp.erase(first,last);
//first为需要删除的区间的起始迭代器，last为需要删除的区间的末尾迭代器的下一个地址。
mp.erase(it,mp.end());
//删除it之后的所有映射。

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

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

（4）clear()： clear()用来清空map中所有的元素，复杂度为O(N)。

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

queue

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

queue的引用：

using namespace std;
#include <queue>

queue的定义：

queue<typename> name;

queue容器内元素访问：

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

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

q.push(i);

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

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

（3）pop()： pop()令队首元素出队，时间复杂度为O(1)。

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

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

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

（5）size： size()返回queue内元素的个数，时间复杂度为O(1)。

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

未完待续

@本地磁盘姬

ohayou.aimo.moe

微博：@本地磁盘姬碟酱

Twitter：本地磁盘姬改二

知乎：本地磁盘姬

2020年07月13日

本地磁盤小日記ヾ(≧▽≦*)ゝ

世界無限大.且行且珍惜w;
計算機科學視覺與美術在學｜跨女｜程序媛｜創作者｜中日英OK｜公主w;

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

vector

set

String

Map

queue

未完待续

Comments