C++STL笔记

本文主要内容如下：

1.vector

1.1vector的定义

1.2vector容器内元素的访问

1.3vector常用函数

2.set

2.1 set的定义

2.2set容器内元素的访问

2.3set常用函数

3.string

3.1 string 的定义

3.2string容器内元素的访问

3.3string 常用函数

4.map

4.1 map的定义

4.2 map容器内元素的访问

4.3 map常用函数

5. queue

5.1 queue的定义

5.2 queue 容器内元素的访问

5.3 queue 常用函数

5.4 queue常见用途

6.priority_queue

6.1 priority_queue的定义

6.2 priority_queue 容器内元素的访问

6.3 priority_queue 常用函数

6.4 priority_queue内元素优先级的设置

7. stack

7.1stack的定义

7.2stack容器内元素的访问

8. pair

8.1 pair的定义

8.2 pair中元素的访问

8.3 pair常用函数

8.4 pair常见用途

9. algorithm头文件

1.vector

向量，长度可变的数组

头文件

#include<vector>

1.1vector的定义

vector<typename> name;

例如：

vector<int> name;

如果typename是vector

vector<vector<int>>name;

相当于二维数组

vector<typename> ArrayName[arraySize];

例如：

vector<int> vi[100];

1.2vector容器内元素的访问

（1）通过下标访问

vi[index];

（2）通过迭代器访问

vector<typename>：：iterator  it;

例如：

vector<int>::iterator  it;

有上下文环境时，可以直接用 auto it=vi.begin();

例如：

for(auto it=vi.begin();it!=vi.end();it++)

printf(“%d”,*it);

注：vi.begin()和vi.end()左闭右开。

1.3vector常用函数

（1）push_back()

在末尾添加一个元素。

vi.push_back(i);

（2）pop_back()

删除一个尾元素。

  vi.pop_back();

（3）size()

返回vector元素的个数，注意是unsigned类型。

vi.size();

（4）clear()

清空vector中所有的元素。

vi.clear();

（5）insert()

insert(it,x)在迭代器it前插入一个元素x。

vi: 1 2 3 4 5

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

vi:1 2 -1 3 4 5

（6）erase()

1.删除单个元素

vi:5 6 7 8 9

vi.erase(vi.begin()+3)

vi:5 6 7 9

2.删除一个区间内的所有元素

erase[first,last); 左闭右开

vi:5 6 7 8 9

vi.erase(vi.begin()+1,vi.begin+4)

vi:5 9

2.set

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

头文件

#include<set>

2.1 set的定义

set<typename> name;

例如：

set<int> name;

set数组

set<typename>ArrayName[arraySize];

例如：

set<int> a[100];

2.2set容器内 元素的访问

set只能用迭代器访问

set<typename>::iterator it;

例如：

set<int>::iterator it;

set<int> st;

for(auto it=st.begin();it!=st.end();it++)

print(“%d”,*it);

st:2 3 5

set元素自动递增排序，且自动去除重复元素。

注意：不能用it<st.end();

除了vector和string容器外不能用*(it+i)

2.3set常用函数

（1）insert()

insert(x)将x插入set容器中，并自动递增排序和去重。

st.insert(x)

（2）find()

find(value)返回set中对应值为value的迭代器。

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

（3）erase()

1.删除单个元素

st.erase(it); //it 为迭代器

st.erase(find(100));

st.erase(value)，value 为所要删除元素的值。

st.erase(100);

2.删除区间内所有元素

erase[first,last); 左闭右开

st.erase(first,last);

st.erase(it,st.end());

（4）size()

返回set内元素的个数，unsigned类型

（5）clear()

清空set内所有的元素

3.string

字符串数组

3.1 string 的定义

string str=”abcd”;

3.2string容器内元素的访问

（1）通过下标访问

str[index];

输出str

cout<<str;

printf(“%s”,str.c_str());

（2）通过迭代器访问

string迭代器不需要参数

string::iterator it;

for(it=str.begin();it!=str.end();it++)

printf(“%c”,*it);

3.3string 常用函数

（1）operator+=

str1+=str2;

（2）compare operator

可直接使用 == ,!=,<=,<,>,>=比较大小，比较规则是字典序

（3）length()/size()

返回字符串长度，两者基本相同。

（4）insert()

1.insert(pos.string);

在pos号位置插入字符串string

string str1=”abcxyz”;

string str2=”opq”;

str1.insert(3,str2);

str1:abcopqxyz

2.insert(it,it2,it3); //it为原字符串待插入位置，it2，it3位待插入字符串首尾迭代器。[it2,it3) 左开右闭

string str1=”abcxyz”;

string str2=”opq”;

str1.insert(str1.begin()+3,str2.begin(),str2.end())

str1:abcopqxyz

（5）erase()

1.删除单个元素

str.erase(it) //it为所要删除元素位置的迭代器

2.删除一个区间内的所有元素

(1)str.erase(first,last); [first,last)左开右闭

string str=”abcdefg”;

str.erase(str.begin()+2,str.end()-1);

str:abg

(2)str.erase(pos,length);

pos为起始位置，删除后面长度为length的字符串。

string str=”abcdefg”;

str.erase(3,2);

str:abcfg

（6）clear()

str.clear(); 清空字符串

（7）substr()

substr(pos,len); 返回从pos号位开始、长度为len的子串。

string str=”Thank you for your smile”;

str.substr(0,5);

Thank

str.substr(14,4);

your

str.substr(19,5);

smile

（8）string::npos

 string::npos是一个常数，其本身值为-1，unsigned_int类型，作为find函数失配时的返回值。

（9）find()

str1.find(str2); 当str2是str1的子串时，返回str2在str1中第一次出现的位置；如果str2不是str1的子串，返回string：：npos。

str1.find(str2,pos); 从str1的pos号位开始匹配str2，返回值与上文相同。

string str1=”Thank you for your smile”;

string str2=”you”;

string str3=”me”;

cout<<str1.find(str2);

6

cout<<str1.find(str2,7);

14

（10）replace()

1.str1.replace(pos,len,str2);  把str1从pos号位开始、长度为len的子串替换为str2.

2.str1.replace(it1,it2,str2);  把str1的迭代器[it1,it2)范围的子串替换成str2.

string str1=”Maybe you will turn around”;

string str2=”will not”;

striing str3=”surely”;

cout<<str1.replace(10,4,str2);

Maybe you will not turn around

cout<<str1.replace(str1.begin(),str1.begin()+5,str3);

surely you will not turn around

4.map

映射，map可以将任何基本类型（包括STL容器）映射到任何基本类型（包括STL容器）。

例如：

字符串-->页码。

头文件

#include<map>

4.1 map的定义

map<typename1,typename2> mp;

map<key,value> mp;

map<int,int> mp 相当于普通的int型数组。

如果是字符串到整型的映射，必须用string，不能用char数组。

map<string,int>  mp;

map的键和值也可以是STL容器。

例如:

map<set<int>,string> mp;

4.2 map容器内元素的访问

1.通过下标访问

与访问普通数组一样，例如

map<char,int> mp;

mp[‘c’]来访问它对应的整数。

mp[‘c’]=20;

注：map的键值是唯一的。

2.通过迭代器访问

map<typename1,typename2>::iterator it;

用it->first访问键

用it->second访问值

map<char,int>mp;

mp[‘m’]=20;

mp[‘r’]=30;

mp[‘a’]=40;

for(auto it=mp.begin();it!=mp.end();it++)

printf(“%c %d\n”,it->first,it->second);

map会按键值从小到大自动排序。

4.3 map常用函数

（1）find()

find(key)返回键值为key的映射的迭代器。

auto it = mp.find(‘c’);

（2）erase()

1.删除单个元素。

mp.erase(it);  it为迭代器。

mp.erase(key); key为欲删除的映射的键。

2.删除一个区间内的所有元素。

map.erase(first，last)  [first,last) 删除迭代器区间，左闭右开。

（3）size()

返回map中映射的对数。

（4）clear()

清空map中所有的元素。

5.queue

队列，一个先进先出的容器。

头文件

#include<queue>

5.1 queue的定义

queue<typename> name;

5.2 queue 容器内元素的访问

queue是一种先进先出的限制访问的数据结构。

只能front()访问队首元素，back()访问队尾元素。

queue<int> q;

q.front();

q.back();

5.3 queue 常用函数

（1）push()

q.push(x)将x进行入队

（2）front() / back()

访问队首和队尾元素。

（3）pop()

q.pop()令队首元素出队。

（4）empty()

检测queue是否为空，返回true为空，返回false则非空。

（5）size()

返回queue内元素的个数。

5.4 queue常见用途

例如广度优先搜索。

6.priority_queue

优先队列，底层用堆来实现。在优先队列中，队首元素是当前队列中优先级最高的一个。

头文件

#include<queue>

6.1 priority_queue的定义

priority_queue<typename> name;

6.2 priority_queue 容器内元素的访问

只能用q.top()函数访问。

6.3 priority_queue 常用函数

（1）push()

q.push(x)将x入队。

（2）top()

q.top()可以获得队首元素。

（3）pop()

令队首元素（堆顶元素）出队。

q.pop();

（4）empty()

检测优先队列是否为空，为空则返回true，返回false为空。

（5）size()

返回优先队列内元素的个数。

6.4 priority_queue内元素优先级的设置

1.基本数据类型的优先级设置

基本数据类型指int、double、char型等数据类型。

下面两种优先队列的定义是等价的。

priority_queue<int> q;

priority_queue<int,vector<int>,less<int> > q;

vector<int> 是来承载底层数据结构堆（heap）的容器，而less<int>是比较类。

less<int> 表示数字大的优先级越大，而greater<int>表示数字小的优先级越大。char类型按字典序。

2.结构体的优先级设置

需要重载比较符号。

例如：

struct fruit{

string name;

int price;

friend bool operator<(fruit f1,fruit f2){

return f1.price<f2.price;
}

};

判断f1==f2,则相当于!(f1<f2)&&!(f2<f1)。

所以 priority_queue<fruit> q; 内部以价格高的水果优先级高。

同理，如果想以价格低的水果为优先级高，那么把<改成>。

struct fruit{

string name;

int price;

friend bool operator<(fruit f1,fruit f2){

return f1.price>f2.price;
}

};

注：只能重载<,重载>会编译错误。

不用greater<typename>,不重载<,不用friend函数

用cmp。

#include<iostream>

#include<queue>

#include<string>

using namespace std;

struct fruit{

string name;

int price;

}f1,f2,f3;

struct cmp{

bool operator () (fruit f1,fruit f2){

return f1.price>f2.price;

}

};

int main()

{

priority_queue<fruit,vector<fruit>,cmp> q;

f1.name="a";

f1.price=3;

f2.name="b";

f2.price=2;

f3.name="c";

f3.price=1;

q.push(f1);

q.push(f2);

q.push(f3);

cout<<q.top().name<<" "<<q.top().price;

return 0;

}

结果： c  1

即便是基本数据类型或其他STL容器（如set），也可以用同样的方式定义优先级。如果结构体内数据较庞大，前面加const & 引用来提高效率。

friend bool operator<(const & fruit f1,const & fruit f2){

return f1.price>f2.price;

}

struct cmp{

bool operator () (const & fruit f1,const & fruit f2){

return f1.price>f2.price;

}

};

priority_queue的本质是堆。

7.stack

栈，一个后进先出的容器。

头文件

#include<stack>

7.1stack的定义

stack<typename> name;

7.2stack容器内元素的访问

由于栈是一种后进先出的数据结构，所以只能用top()来访问栈顶元素。

st.top();

7.3 stack常用函数

（1）push()

st.push(x)将x入栈

（2）top()

st.top()访问栈顶元素。

（3）pop()

st.pop()删除栈顶元素。

（4）empty()

st.empty()检测是否为空，为空返回true，否则返回false。

（5）size()

st.size()返回栈中元素的个数。

8.pair

当想要将两个元素绑在一起作为一个合成元素，又不想定义结构体时，可以使用pair。

头文件

#include<utility>

map实现用了pair，所以#include<map>包含#include<utility>，用map不需要再包含utility头文件。

pair 相当于

struct pair{

typeName1 first;

typeName2 second;

};

8.1 pair的定义

pair<typeName1,typeName2> name;

例如：

pair<string ,int> p;

初始化：

pair<string ,int> p(“haha”,5);

pair<string,int> p=make_pair(“haha”,5);

8.2 pair中元素的访问

用p.first和p.second访问。

8.3 pair常用函数

（1）比较操作数，pair可以直接使用==,!=,<,<=,>,>=比较大 小。

       比较规则是先以first的大小作为标准，只有当first相等时才 去比较second的大小。

8.4 pair常见用途

例如：

#include<iostream>

#include<map>

using namespace std;

int main(){

map<string,int>mp;

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

mp.insert(pair<string,int>("haha",10));

//auto it ==map<string,int>::iterator it

for(auto it = mp.begin();it!=mp.end();it++)

cout<<it->first<<" "<<it->second<<endl;

return 0;

}

9.algorithm头文件

（1）max() /min()/abs()

max和min返回两个数x、y中的最大最小值。abs(x)中x必须为整数，浮点数用math头文件下的fabs()。

（2）swap()

  swap(x,y)交换x和y的值。

（3）reverse()

reverse(it,it2)可以将数组指针在[it1,it2)之间的元素或容器的迭代器[it1,it2)范围内的元素进行反转。

例如：

int a[10]={10,11,12,13,14,15};

reverse(a,a+4); //将a[0]~a[3} 4个元素反转。

13 12 11 10 14 15

string str =“abcdefghi”

reverse(str.begin()+2,str.begin()+6);

abfedcghi

（4）next_permutation()

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

例如：

n=3的全排列为

123 132 213 231 312 321

231的下一个序列为312。

int a[10]={1,2,3};

do{

cout<<a[0]<<a[1]<<a[2]<<” ”;

}while(next_permutation(a,a+3));

输出：123 132 213 231 312 321

（5）fill()

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

int a[5];

fill(a,a+5,233);

（6）sort()

sort(a,a+4); //默认递增排序

cmp函数

bool cmp(int a,int b){
return a>b; //从大到小排序 与priority_queue相反。

}

结构体

struct node{

int x;

int y;

}

bool cmp(node a,node b){

    if(a.x!=b.x)
return a.x>b.x; //按x从大到小排序 与priority_queue相反。

 else

return a.y<b.y; //若x相等，则按y从小到大排序。

}

STL中，只有vector，string，deque是可以用sort的，像set、map容器是用红黑树实现的，元素本身有序，不允许用sort排序。

（7）lower_bound()/upper_bound()

  lower_bound(first,last,val)用来寻找在数组或容器中的[first,last)范围内第一个值大于等于val的元素的位置，如果是数组，返回该位置指针；如果是容器，返回该位置的迭代器。

upper_bound(first,last,val)用来寻找数组或容器的[first，last)范围第一个值大于val的元素的位置，如果是数组，返回该位置指针；如果是容器，返回该位置的迭代器。

如果数组或容器中没有寻找到该元素，则lower_bound()和upper_bound()返回可以插入该元素的位置的指针或迭代器。