以下为个人学习笔记和习题整理
课程:计算机程序设计(C++)- 西安交通大学 @ 中国大学 MOOC
https://www.icourse163.org/course/XJTU-46006
# 课堂笔记
# 函数模板
函数重载是最佳方案吗?
假如设计一个求两参数最大值的函数,在实践中可能需要定义四个函数:
int max ( int a, int b ) { return ( a > b ) ? a , b; } | |
long max ( long a, long b ) { return ( a > b ) ? a , b;} | |
double max ( double a, double b ) { return ( a >b)? a , b; } | |
char max ( char a, char b ) { return ( a > b ) ? a , b; } |
这些函数几乎相同,唯一的区别就是形参类型不同
需要事先知道有哪些类型会使用这些函数,对于未知类型,比如 string
这些函数不起作用。
专家的解决方案
template < class T > //class 某种类型 | |
T max(T a , T b) | |
{ | |
return ( a > b ) ? a , b; | |
} |
T 是什么?
答:是可以比较大小的某种类型。这种抽象的东西是什么?
答:就像一个模板,所以叫函数模板
函数模板是用类型做参数,设计出的通用的函数。
template <class T1,class T2,,,> | |
函数返回类型 函数名(函数参数表) | |
{ | |
// 函数模板定义 | |
//T1,T2 等等,用在其中 | |
} |
其中 template
表示定义的是模板, < >
里是模板的类型参数,可以是一个或多个。
# 模板工作方式
- 函数模板只是一个抽象说明,不能直接执行,需要实例化为模板函数后才能执行。
- 在说明了一个函数模板后,当编译系统发现有一个对应的函数调用时,将根据实参中的类型来确认是否匹配函数模板中对应的形参,然后生成一个重载函数。
- 函数模板如下:
template <class T> | |
T Max(T a,T b) | |
{ | |
return a>b? a:b; | |
} |
- 编译时发现:
Max(6 , 7); |
- 编译系统生成:
int Max(int a, int b) | |
{ | |
return a>b? a:b; | |
} |
# 例子:求数组中的最小值
#include <iostream> | |
template <class T> | |
T min(T a[],int n) | |
{ | |
int i; | |
T minv=a[0]; | |
for( i=1; i<n; i++) | |
{ | |
if(minv>a[i]) | |
{ | |
minv=a[i]; | |
} | |
} | |
return minv; | |
} | |
void main() { | |
int a[]={1,3,0,2,7,6,4,5,2}; | |
double b[]={1.2,-3.4,6.8,9,8}; | |
cout<<"a数组的最小值为: "<<min(a,9)<< endl; | |
cout<<"b数组的最小值为: "<<min(b,4)<<endl; | |
} | |
//a 数组的最小值为:0 | |
//b 数组的最小值为:-3.4 |
# 类模板
从栈说起
栈是一种线性结构
栈限制在结构的一端进行插入和删除操作
允许插入和删除操作的一端称为栈顶,另一端称为栈底
⤵️进栈 出栈⤴️ | |
---|---|
栈顶 top ➡️ | a3 |
a2 | |
栈底 | a1 |
- 建立
int
型的栈类属性(数据成员):
int
型数组(存储)top
(栈顶位置)操作(成员函数):
进栈(插入)
出栈(删除)
class stack | |
{ | |
int dat[100]; // 设元素数 & lt;=100 | |
int top; | |
public: | |
void push(int e) { // 进栈 | |
将数据放入dat; | |
改top; // 向上移 | |
} | |
int pop() { // 出栈 | |
改top; // 向下移 | |
返回删除的值; | |
} | |
} |
- 建立抽象的栈类模板
template <class T> // 此处 class 指某种类型,不是 C++ 中的类 | |
class stack | |
{ | |
T dat[100]; | |
int top; | |
public: | |
// 进栈 | |
void push(T e) | |
{ …… } | |
// 出栈 | |
T pop( ) | |
{ …… } | |
} |
类是对问题空间的抽象,而类模板则是对类的抽象,是对一批仅仅成员数据类型不同的类的抽象。
程序中可以首先定义一个类模板,然后通过使用不同的实参生成不同的类。
template <class <类型参数>> | |
class <类名> | |
{ | |
…… | |
}; |
类模板名 <数据类型> 对象名; | |
// 例如 | |
stack <int> s1; // 定义一个整数类型栈 | |
stack <char> s2; // 定义一个字符类型栈 |
在 C++ 的标准模板库 (STL) 中,定义了大量类模板(其中也包括栈),使用这些优秀的类模板可以我们提高编程效率,提高程序可靠性。
# 标准模板库 STL
Standard Template Library,STL 是一个具有工业强度的,高效的 C++
程序库。
它实现了诸多在计算机科学领域里常用的基本数据结构和基本算法。
STL 主要包含了容器、算法、迭代器。
STL 系由 Alexander Stepanov 和 Meng Lee 等人创造于惠普实验室。
STL 于 1994 年 2 月年正式成为 ANSI/ISO C++
的一部份。
# 容器
是容纳、包含相同类型元素的对象,主要用类模板实现。
序列型容器:
容器中的元素按线性结构组织起来,可以逐个读写元素。
主要代表有vector
向量、deque
双端队列 、list
双向链表。关联型容器:
关联容器通过键key
存储和读取元素。
主要有map
映射、set
集合等。容器适配器:
是对前面提到的某些容器(如vector
)进行再包装,使其变为另一种容器。
典型的有栈stack
、队列queue
等。
# 迭代器
是用于确定元素位置的数据类型,可用来遍历容器中的元素。
通过迭代器可以读取、修改它指向的元素,它的用法和指针类似。
每一种容器都定义了一种迭代器。
定义一个容器类的迭代器的方法可以是:
容器类名<元素类型>::iterator 变量名; | |
vector<int>::iterator it; |
- 访问一个迭代器指向的元素:
*迭代器变量名 | |
*it=5; |
# 算法
由许多函数模版组成的集合,实现了大量通用算法,用于操控各种容器。
STL 中提供的算法涉及到:比较、交换、查找、遍历、复制、修改、移除、反转、排序、合并等。大约有 70 种标准算法。
算法通过迭代器来操纵容器中的元素。
算法可以处理容器,也可以处理 C 语言的数组。
# vector
容器
# 主要特征
vector
实际上就是对动态数组封装可以像数组一样可以使用下标访问元素
若vector
长度为n
,则其下标为0~n-1
,根据下标访问元素效率高vector
对象的空间随着插入删除操作自动调整
因为空间自动调整比较耗费时间,因此频繁插入删除的情况下,vector
效率稍差
# 对象创建
// 创建一个空向量 | |
vector<int> v1; //int 类型向量 | |
vector<string> s1; //string 类型向量 | |
// 从已有向量复制创建向量 | |
vector<int> v2(v1); // 拷贝 v1 内容到 v2(拷贝构造函数) | |
// 创建 10 个元素的向量 | |
vector<string> s2(10); | |
// 创建 10 个元素的向量,所有元素都是 1.5 | |
vector<double> v3(10, 1.5); | |
// 创建向量指针 | |
vector<int> *pvec = new vector<int>(10, -5); |
# 添加元素
# push_back()
尾部添加元素
使用 push_back()
函数向 vector
尾部添加元素
#include<iostream> | |
#include<vector> | |
using namespace std; | |
int main() | |
{ | |
vector<int> v1; | |
v1.push_back(1); | |
v1.push_back(2); | |
return 0; | |
} |
1 | |||
1 | 2 |
# insert()
任意位置插入元素
使用 insert()
函数向 vector
添加元素
#include<iostream> | |
#include<vector> // 使用 vector 必备 | |
using namespace std; | |
int main() | |
{ | |
vector<int> v1; | |
v1.push_back(1); | |
v1.push_back(2); | |
v1.insert(v1.begin(),0); // 头部插入 | |
v1.insert(v1.end(), 4); // 尾部插入 | |
v1.insert(v1.end()-1,3); // 倒数第二位置 | |
return 0; | |
} |
v1.begin()
,v1.end()
获取相应位置的迭代器
1 | |||||
1 | 2 | ||||
0 | 1 | 2 | |||
0 | 1 | 2 | 4 | ||
0 | 1 | 2 | 3 | 4 |
# 访问元素
使用 [下标]
可以获取元素值,修改元素
#include<iostream> | |
#include<vector> | |
using namespace std; | |
int main() | |
{ | |
vector<int> v1; | |
v1.insert(v1.end()-1,3); // 倒数第二位置 | |
v1[4]=10; //v1 [5]=6; 超界错误 | |
for(int i=0; i<v1.size(); i++) { | |
//v1.size () 为 5 | |
cout<<v1[i]<<" "; | |
} | |
return 0; | |
} |
1 | |||||
1 | 2 | ||||
0 | 1 | 2 | |||
0 | 1 | 2 | 4 | ||
0 | 1 | 2 | 3 | 10 |
# 删除元素
# pop_back()
删除最后一个元素
#include<iostream> | |
#include<vector> | |
using namespace std; | |
int main() { | |
vector<int> v1; | |
…… …… | |
v1[4]=10; | |
v1.pop_back(); // 删除 10 | |
return 0; | |
} |
1 | |||||
1 | 2 | ||||
0 | 1 | 2 | |||
0 | 1 | 2 | 4 | ||
0 | 1 | 2 | 3 | 10 | |
0 | 1 | 2 | 3 |
# erase()
删除任意位置元素
#include<iostream> | |
#include<vector> | |
using namespace std; | |
int main() { | |
vector<int> v1; | |
…… …… | |
v1.pop_back(); // 删除 10 | |
v1.erase(v1.begin()); // 删除 0 | |
v1.erase(v1.begin(), v1.end()); // 全删 | |
return 0; | |
} |
# clear()
删除全部元素
v1.clear()
1 | |||||
1 | 2 | ||||
0 | 1 | 2 | |||
0 | 1 | 2 | 4 | ||
0 | 1 | 2 | 3 | 10 | |
1 | 2 | 3 | |||
# 向量大小相关函数
v.size() | 返回向量的大小 |
v.max_size() | 返回向量可容纳的最大个数 |
v.empty() | 返回向量是否为空 |
v.resize(n) | 调整向量大小,使其可以容纳 n 个元素,如果 n<v.size() , 则删除多出来的元素;否则,添加新元素 |
v.resize(n,t) | 调整向量的大小,使其可以容纳 n 个元素,所有新添加的元素初始化为 t |
v.capacity() | 获取向量的容量,再分配内存空间之前所能容纳的元素个数 |
0 | 1 | 2 | ... | 23 | ... | ... | ||
⬆️ | ⬆️ |
# 迭代器
# 基本操作
vector<int>::iterator it; | |
*it = 5; |
vector
上迭代器支持随机访问:
- 提供读写操作
- 并能在数据中随机移动(前后,跳跃式)
用加、减操作移动迭代器:
it++; ++it; // 指向下一元素 | |
it--; --it; // 指向前一元素 | |
it + i // 返回指向 it 后面的第 i 个元素的迭代器 | |
it - i // 返回指向 it 前面的第 i 个元素的迭代器 |
用
<
,<=
,>
,>=
,==
,!=
判断迭代器前后、相等关系:
it1 < it2 // 表示 it1 在 it2 之前 |
# begin()
和 end()
函数
每种容器都定义了一对命名为 begin
和 end
的函数,用于返回迭代器。
如果容器中有元素,由 begin
返回的迭代器指向第一个元素:
it = v1.begin(); // 指向 v1 [0] |
由 end
返回的迭代器指向 vector
的末端元素的下一个。
通常称为超出末端迭代器,表明它指向了一个不存在的元素。
it = v1.end(); // 指向末端元素的下一个 |
如果 vector
为空, begin
返回的迭代器与 end
返回的迭代器相同
# 用迭代器读取元素
#include<iostream> | |
#include<vector> | |
using namespace std; | |
int main() { | |
vector<int> v1; | |
for(int i=1; i<10; i++) | |
{ | |
v1.push_back(i); // 添加 1~9 | |
} | |
vector<int>::iterator it; | |
for(it=v1.begin(); it<v1.end(); it++) { | |
if(*it%2==0) { | |
cout<<*it<<" "; | |
} | |
} | |
return 0; | |
} |
# 以迭代器为参数的插入删除函数
v.insert(p,t) | 在迭代器 p 所指向的元素前面插入值为 t 的元素 |
v.insert(p,n,t) | 在迭代器 p 所指向的元素前面插入 n 个值为 t 的新元素 |
v.insert(p,b,e) | 在迭代器 p 所指向的元素前面插入迭代器 b 和 e 标记的范围内的元素 |
v.erase(p) | 删除迭代器 p 指向的容器中的元素 |
v.erase(b,e) | 删除迭代器 b 和 e 所标记范围内的元素 |
vector<int> v2(3, 1); | |
vector<int> v1(4, 0); | |
// 在头部插入 5 | |
v1.insert(v1.begin(), 5); | |
// 在尾部插入 7 | |
v1.insert(v1.end(), 7 ); | |
// 在下标为 4 处插入 9 | |
vector<int>::iterator it = v1.begin() + 4; | |
v1.insert(it, 9 ); | |
// 删除偶数元素 | |
for(it=v1.begin(); it<v1.end(); ) { | |
if(*it%2==0) | |
{ | |
it=v1.erase(it); | |
} | |
else | |
{ | |
it++; | |
} | |
} | |
// 将 v1 的一部分拷贝到 v2 | |
v2.insert(v2.begin(),v1.begin(),v1.begin()+2); |
v2 | 1 | 1 | 1 | |||||
v1 | 0 | 0 | 0 | 0 | ||||
v1 | 5 | 0 | 0 | 0 | 0 | |||
v1 | 5 | 0 | 0 | 0 | 0 | 7 | ||
v1 | 5 | 0 | 0 | 0 | 9 | 0 | 7 | |
v1 | 5 | 9 | 7 | |||||
v2 | 5 | 9 | 1 | 1 | 1 |
# 用迭代器循环删除的一个问题
vecotr<int>::iterator it = vc.begin(); | |
for( ; it != vc.end(); it++ ) | |
{ | |
if( ***** ) { | |
vc.erase(it); | |
} | |
} |
原因:
erase()
删除元素后,it
失效,并不是指向下一个元素
for(it=v1.begin(); it<v1.end(); ) { | |
if(*******) | |
{ | |
it=v1.erase(it); | |
} | |
else | |
{ | |
it++; | |
} | |
} |
在
C++ 11
标准中,erase()
会返回一个iterator
,这个iterator
指向了 “当前删除元素的后继元素”。
# 算法应用
算法主要在头文件 <algorithm>
和 <numeric>
中定义
功能 | 常用算法 |
---|---|
排序 | sort() |
查找 | find() |
替换 | replace() |
合并 | merge() |
反序 | reverse() |
统计 | count() |
其他等等算法 |
许多算法往往以迭代器作参数。
比如排序和查找都需要两个迭代器参数(表示起始位置、终止位置)。有的算法返回一个迭代器。
比如find
算法,在容器中查找一个元素,并返回一个指向该元素的迭代器。
# 查找 find()
简化形式: find(first, last, val)
first
和last
这两个参数都是容器的迭代器,它们给出了容器中的查找区间起点和终点。
这个区间是个左闭右开的区间
[first,last)
,即区间的起点是位于查找范围之中的,而终点不是
val
参数是要查找的元素的值。函数返回值是一个迭代器。
如果找到,则该迭代器指向被找到的元素。
如果找不到,则该迭代器指向查找区间终点。
#include <vector> | |
#include <algorithm> // 算法头文件 | |
#include <iostream> | |
using namespace std; | |
int main() { | |
vector <int> v(5,3);// 一个容器,5 个 3 | |
vector <int>::iterator p; // 迭代器 | |
p = find(v.begin(),v.end(),3); | |
if( p!=v.end() ) | |
{ | |
cout<<*p<< endl; | |
} | |
// 3 | |
p = find(v.begin(),v.end(),5); | |
if( p==v.end() ) | |
{ | |
cout<<"not found\n"; | |
} | |
// not found | |
return 0; | |
} |
# 排序 sort()
简化形式: void sort( first, last )
first
和last
这两个参数都是容器的迭代器,它们给出了容器中的查找区间起点和终点。
#include <vector> | |
#include <algorithm> | |
#include <iostream> | |
#include <string> | |
using namespace std; | |
int main() { | |
vector <string> v; | |
v.push_back("food"); | |
v.push_back("candy"); | |
v.push_back("apple"); | |
// food candy apple | |
sort(v.begin(), v.end()); | |
vector <string>::iterator it; | |
for(it=v.begin(); it!=v.end();it++) { | |
cout<< *it <<" "; | |
} | |
// apple candy food | |
return 0; | |
} |
# 合并 merge()
形式: merge(f1, e1, f2, e2, p)
f1
、e1
、f2
、e2
、p
都是迭代器- 将有序序列
v1
中[f1, e1)
和有序序列v2
中[f2, e2)
合并成有序序列,存入p
的前面
#include <iostream> | |
#include <algorithm> | |
#include <vector> | |
using namespace std; | |
int main() { | |
int A[] = {5,10,15,20,25}; | |
int B[] = {50,40,30,20,10}; | |
vector<int> v(10); | |
vector<int>::iterator it; | |
sort(A, A+5); | |
sort(B, B+5); | |
merge(A, A+5, B, B+5, v.begin()); | |
for(it=v.begin(); it!=v.end(); ++it) | |
{ | |
cout<<*it<<" "; | |
} | |
// 5 10 10 15 20 20 25 30 40 50 | |
return 0; | |
} |
# 其他算法
replace(first, last, old, new)
first
,last
为迭代器
作用:将[first,last)
范围内的所有值为old
的替换为new
reverse(start, end)
start
,end
为迭代器
作用:将序列中[start, end)
范围反转排列顺序count(start, end, searchValue)
start
,end
为迭代器
作用:统计[start, end)
范围内等于searchValue
的元素个数accumulate(first, last, init)
first
,last
为迭代器
作用:将[first,last)
范围内的所有值相加,再加上init
后返回
# 序列型容器
# 类型
# vector
向量
定义在头文件 <vector>
实际上就是个动态数组。
随机存取任何元素都能在常数时间完成。
在尾端增删元素具有较佳的性能。
向量 vector
# deque
双端队列
定义于头文件 <deque>
也是个动态数组。
随机存取任何元素都能在常数时间完成,但性能次于 vector。
在两端增删元素具有较佳的性能。
双端队列 deque
# list
双向链表
定义于头文件 <list>
任意位置插入和删除元素的效率都很高
不支持随机存取
每个元素还有指针占用额外空间
双向链表 list
在序列容器中,元素的插入位置同元素的值无关
# 选用
如果程序要求随机访问元素,则应用
vector
或者deque
容器如果程序必须在容器中间位置插入或删除元素,则应采用
list
容器如果程序不是在容器的中间位置,而是在容器的首部或尾部插入或删除元素,则应采用
deque
容器
# 初始化
vector<int> vec; | |
list<string> list1; | |
deque<float> deq; |
vector<int> vec1; | |
vector<int> vec2(vec1); | |
list<string> list1; | |
list<string> list2(list1); | |
deque<float> deq1; | |
deque<float> deq2(deq1); |
vector<string> vec(10); | |
list<int> list1(10); | |
deque<string> deq(10); |
vector<string> vec(10,"hi"); | |
list<int> list1(10, 1); | |
deque<string> deq(10, "hi"); |
# 添加元素
c.push_back(t)
在容器c
的尾部添加值为t
的元素
返回void
类型c.push_front(t)
在容器c
的前端添加值为t
的元素
返回void
类型
只适用于list
和deque
c.insert(p,t)
在迭代器p
所指向的元素前面元素t
返回指向新添加元素的迭代器c.insert(p,n,t)
在迭代器p
所指向的元素前面插入n
个值为t
的新元素
返回void
类型c.insert(p,b,e)
在迭代器p
所指向的元素前面插入迭代器b
和e
标记的范围内的元素
返回void
类型
# 访问元素
c.back()
返回容器c
的最后一个元素的引用c.front()
返回容器 c 的第一个元素的引用c[n]
返回下标为n
的元素的引用(0 <= n < c.size()
)
只适用于vector
和deque
容器c.at[n]
返回下标为n
的元素的引用(0 <= n < c.size()
)
只适用于vector
和deque
容器
# 删除元素
c.pop_back()
删除容器c
的最后一个元素c.pop_front()
删除容器c
的第一个元素
只适用于deque
和list
容器c.erase(p)
删除迭代器p
指向的容器中的元素c.erase(b,e)
删除迭代器b
和e
所标记范围内的元素c.clear()
删除容器中所有的元素
# 关联型容器
# 特征
STL 提供了 4 个关联容器,包括: map
映射、 multimap
多重映射、 set
集合、 multiset
多重集合。
map
、 multimap
的元素由 key
, value
二元组构成,其中键必须是唯一的。
map
映射 & multimap
多重映射
set
、 multiset
相当于只有键 key
、没有对应值 value
的 map
和 mulitimap
。
set
支持通过键实现的快速读取,元素唯一。
A B C D E F
multiset
支持同一个键多次出现的 set
类型。
A A C C E E
# 与序列容器的差别
关联容器是通过键 key
存储和读取元素。
顺序容器则通过元素在容器中的位置顺序存储和访问元素。
map
和 set
的底层机制都是通过一种称为 “红黑树” 的数据结构存取数据,这使得它们的数据存取效率相当高。
“红黑树” 是一种常见的数据结构。
# map
容器
# pair
类型
pair
类定义在 <utility>
头文件中。pair
是一个类模板,它将两个值组织在一起,这两个值的类型可不同。
可以通过 first
和 second
公共数据成员来访问这两个值。pair
对象常常作为元素,被添加到 map
中。
pair<int, string> mypair(5 , "Jack"); // 调用构造函数 | |
pair<int, string> otherPair; // 直接赋值 | |
otherPair.first = 6; | |
otherPair.second = "Mike"; |
函数模板 make_pair()
能从两个变量构造一个 pair
pair<int, int > aPair = make_pair( 5, 10 ); |
# 创建及添加元素
map
类定义在 <map>
头文件中。
map<int, string> StuInfo; |
定义了一个用
int
作为键、相关联string
为值的map
pair<int, string> mypair(1, "Tom"); | |
StuInfo.insert(mypair); | |
StuInfo.insert(pair<int, string>(5, "Jack")); |
# 使用运算符 []
修改元素的值
键不可修改StuInfo[1] = "Jim";
因为键为
1
的元素存在,因此修改元素。添加元素
StuInfo[2] = "Lily";
先查找主键为
2
的项,没找到,因此添加这个键为2
的项。取得元素的值
cout<<StuInfo[5] ; // 输出键 5 对应的值
# find()
查找元素
用 find()
查找 map
中是否包含某个关键字
若查找成功则返回目标项的迭代器,否则返回 StuInfo.end()
迭代器。
int target = 3; | |
map<int,string>::iterator it; | |
it = StuInfo.find(target); // 查找关键字 target | |
if( it == StuInfo.end() ){ | |
cout<<"not existed!"; | |
}else{ | |
cout<<"find it!"<<endl; | |
} |
# 删除元素
- 通过
erase()
函数按照关键字删除
若删除成功,返回1
,否则返回0
// 删掉关键字 "1" 对应的条目
int r = StuInfo.erase(1);
- 用
clear()
清空map
StuInfo.clear();
# 迭代器
map<int,string> m; | |
map<int,string>::iterator it; | |
for(it = m.begin();it < m.end(); it++) | |
{ ***** } |
map<int,string> m; | |
map<int,string>::iterator it; | |
for(it = m.begin();it != m.end(); it++) | |
{ ***** } |
#include <iostream> | |
#include <string> | |
#include <utility> | |
#include <map> | |
using namespace std; | |
int main () { | |
map<int,string> StuInfo; | |
StuInfo.insert(pair<int, string>(1, "Tom")); | |
StuInfo.insert(pair<int, string>(5, "Jack")); | |
StuInfo[2]="Lily"; | |
map<int,string>::iterator it; | |
for(it = StuInfo.begin();it != StuInfo.end(); it++) | |
{ | |
cout<<(*it).first<<" "<<(*it).second<<endl; | |
} | |
return 0; | |
} | |
// 1 Tom | |
// 2 Lily | |
// 5 Jack |
# 迭代器
STL 中的迭代器按功能由弱到强分为 5 种:
- 输入:
Input iterators
提供对数据的只读访问。 - 输出:
Output iterators
提供对数据的只写访问。 - 正向:
Forward iterators
提供读写操作,并能一次一个地向前推进迭代器。 - 双向:
Bidirectional iterators
提供读写操作,并能一次一个地向前和向后移动。 - 随机访问:
Random access iterators
提供读写操作,并能在数据中随机移动。
- 输入:
编号大的迭代器拥有编号小的迭代器的所有功能,能当作编号小的迭代器使用。
# 不同迭代器能进行的操作
- 所有迭代器:
++p
,p++
- 输入迭代器:
*p
,p = p1
,p==p1
,p!=p1
- 输出迭代器:
*p
,p = p1
- 正向迭代器: 上面全部
- 双向迭代器: 上面全部,
--p
,p--
, - 随机访问迭代器: 上面全部,以及:
p += i
,p -= i
,p + i
返回指向p
后面的第i
个元素的迭代器p – i
返回指向p
前面的第i
个元素的迭代器p < p1
,p <= p1
,p > p1
,p >= p1
# 容器所支持的迭代器类别
容器 | 迭代器类别 |
---|---|
vector | 随机 |
deque | 随机 |
list | 双向 |
set/multiset | 双向 |
map/multimap | 双向 |
stack | 不支持迭代器 |
queue | 不支持迭代器 |
关联容器支持双向迭代器,它支持:
*
、++
、--
、=
、==
、!=
。
不支持:<
、<=
、>=
、>
# 容器适配器
容器适配器将其他容器加以包装、改造,变成新的容器。
实质上是一种受限容器。
典型容器适配器: stack
栈、 queue
队列
# stack
堆栈
栈是限制在结构的一端进行插入和删除操作。
允许进行插入和删除操作的一端称为栈顶,另一端称为栈底。
编程时加入下列语句:
#include<stack> |
栈的常用函数有:
push(elem) | 将元素 elem 入栈 |
pop() | 栈顶元素出栈 |
top() | 求栈顶元素 |
empty() | 判断栈是否空 |
size() | 求栈内元素个数 |
#include<iostream> | |
#include<stack> | |
using namespace std; | |
int main() | |
{ | |
// 定义栈 s | |
stack<int> s; | |
// 入栈 | |
s.push(1); | |
s.push(2); | |
s.push(3); | |
s.push(9); | |
// 读栈顶元素 | |
cout<<"栈顶元素:"<<s.top()<<endl; | |
// 返回元素个数 | |
cout<<"元素数量:"<<s.size()<<endl; | |
cout<<"出栈过程:"; | |
while(s.empty()!=true) // 栈非空 | |
{ | |
cout<<s.top()<<" "; // 读栈顶元素 | |
s.pop(); // 出栈,删除栈顶元素 | |
} | |
return 0; | |
} | |
// 栈顶元素:9 | |
// 元素数量:4 | |
// 出栈过程:9 3 2 1 |
# queue
队列
只能在一端进行插入、在另一端迚行删除操作的线性结构。
加入下列语句:
#include<queue> |
队列的常用函数有:
push() | 入队 |
pop() | 出队 |
front() | 读取队首元素 |
back() | 读取队尾元素 |
empty() | 判断队列是否空 |
size() | 求队列长度 |