C++学习之二叉树

1.树的基本概念

树的定义：

由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树。

树的结构特点
1. 非线性结构，有一个直接前驱，但可能有多个直接后继（1:n）
2. 树的定义具有递归性，树中还有树。
3. 树可以为空，即节点个数为0。

若干术语
1. 根 à 即根结点(没有前驱)
2. 叶子 à 即终端结点(没有后继)
3. 森林 à 指m棵不相交的树的集合(例如删除A后的子树个数)
4. 有序树 à 结点各子树从左至右有序，不能互换（左为第一）
5. 无序树 à 结点各子树可互换位置。
6. 双亲 à 即上层的那个结点(直接前驱) parent
7. 孩子 à 即下层结点的子树 (直接后继) child
8. 兄弟 à 同一双亲下的同层结点（孩子之间互称兄弟）sibling
9. 堂兄弟 à 即双亲位于同一层的结点（但并非同一双亲）cousin
10. 祖先 à 即从根到该结点所经分支的所有结点
11. 子孙 à 即该结点下层子树中的任一结点

2.二叉树的性质

定义：

n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。

逻辑结构：

一对二（1：2）

基本特征:
1. 每个结点最多只有两棵子树（不存在度大于2的结点）；
2. 左子树和右子树次序不能颠倒（有序树）。

基本形态:

二叉树性质
1. 性质1: 在二叉树的第i层上至多有2i-1个结点（i>0）
2. 性质2: 深度为k的二叉树至多有2k-1个结点（k>0）
3. 性质3: 对于任何一棵二叉树，若度为2的结点数有n2个，则叶子数（n0）必定为n2＋1 （即n0=n2+1）

满二叉树

一棵深度为k 且有2k -1个结点的二叉树。

特点：每层都“充满”了结点

3.二叉树递归遍历思路

遍历定义

指按某条搜索路线遍访每个结点且不重复（又称周游）。

遍历用途

它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。

遍历方法

牢记一种约定，对每个结点的查看都是“先左后右” 。

限定先左后右，树的遍历有三种实现方案：

DLR LDR LRD

先 (根)序遍历中 (根)序遍历后(根)序遍历

1. DLR — 先序遍历，即先根再左再右
2. LDR — 中序遍历，即先左再根再右
3. LRD — 后序遍历，即先左再右再根

注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。

从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。

4.二叉树递归遍历代码实现

STL_day02
知识点1【作业】
01.#define _CRT_SECURE_NO_WARNINGS
02.#include<iostream>
03.#include<vector>
04.#include<deque>
05.#include<string>
06.#include<algorithm>
07.#include<numeric>
08.using namespace std;
09.class Person
10.
了
11.public:
12.string name;
13.int score;
14.
Person(string name,int score)
15.
了
16.
this->name =name;
17.
this->score =score;
18.
?
19.
};
20.
21.
22.
void createPersonVector(vector<Person>&v
)
23.
{
24.string nameSeed ="ABCDE";
25.
for(size_t i =0;i<5;i++)
26.
{
27.
string name ="选手";
28.
name +=nameSeed[i];
29.
30.int score =0;
31.
32.Person p(name,score);33.v.push_back(p);34.}}35.36.37.void setScore(vector<Person>&v)38.{//逐个选手参加比赛39.40.for(vector<Person>::iterator it=v.begin();it!=v.end();it++)41.{42.//*it带表的是每个选手43.//10个评委给每个选手打分分数放在deque容器44.deque<int>d;45.for(size_t i=0;i<10;i++)46.{47.int score =rand()%41+60;//60~10048.d.push_back(score);}49.50.//排序51.52.sort(d.begin(),d.end());53.54.//去掉最高与最低分55.d.pop_back();56.d.pop_front();57.//求总成绩58.59.int sum=0;60.sum =accumulate(d.begin(),d.end(),0);61.//求平均值62.63.int avg =sum /d.size();64.65.//将平均值放入选手容器中(*it).score =avg;66.}67.68.}69.void showPerson(vector<Person>&v)70.{
71.
for(vector<Person>::iterator it=v.begin();it!=v.end();it++)
72.
{
73.cout <<"name ="<<it->name <<",score ="<<it->score <<endl;74.}75.}76.int main(int *argc,char *argv[])77.{78.//创建一个vector<Person>容器来存放选手79.vector<Person>v;80.createPersonVector(v);81.82.//参加比赛83.setScore(v);84.//显示成绩85.
86.
87.
88.
89.
showPerson(v);system("pause");return EXIT_SUCCESS;
}
运行结果：
选手A,=78Score =Iname =越请按仕意键继续.. ·
知识点2【stack容器】
stack容器叫栈容器不存在遍历行为。
stack没有迭代器。
push()入栈
pop()出栈
01.
3.4.3.1 stack构造函数02.
03.stack<T> stkT;//stack采用模板类实现，stack对象的默认构造形式：
stack(const stack &stk);//拷贝构造函数04.
3.4.3.2 stack赋值操作05.
stack& operator=(const stack &stk);//重载06.等号操作符
3.4.3.3 stack数据存取操作07.
push(elem);//向栈顶添加元素08.
09.pop();//从栈顶移除第一个元素
top();//返回栈顶元素10.
11.3.4.3.4 stack大小操作
12.empty();//判断堆栈是否为空
size();//返回堆栈的大小13.
14.
*/
15.
16.
void test01()
17.
{
18.
stack<int> s;
19.
s.push(10);
20.
s.push(20);
21.
s.push(30);
22.
s.push(40);
23.
s.push(50);
24.
cout <<"siz ="<< s.size()<< endl;25.
26.
//遍历栈27.
28.while(!s.empty())
29.
{
30.
cout <<"top ="<< s.top()<< en
dl;
31.
//出栈
32.
s.pop();
33.
}
34.}
运行结果：
D.\wUIK\stuuenUJ_c++_33(2U1siz =5top =50top =40top =30top =20top =10请按任意键继续..
知识点3【queue队列容器】queue队列容器不能遍历不提供迭代器。
01.
3.5.3.1 queue构造函数02.
03.queue<T>queT;//queue采用模板类实现，queue对象的默认构造形式：
queue(const queue &que);//拷贝构造函数04.
05.3.5.3.2 queue存取、插入和删除操作push(elem);//往队尾添加元素06.
07.pop();//从队头移除第一个元素
back();//返回最后一个元素08.
09.front();//返回第一个元素
10.
3.5.3.3 queue赋值操作11.
queue&operator=(const queue &que);//重载12.等号操作符
13.3.5.3.4 queue大小操作
empty();//判断队列是否为空14.
15.size();//返回队列的大小
16.*/
17.
18.class Person
19.{
20.public:
21.string name;
22.int age;
23.Person(string name,int age)
24.25.this->name =name;26.this->age =age;27.}28.29.30.};31.32.void test02()33.34.Person p¹("name¹",20);35.Person p2("name2",30);36.Person p3("name3",40);37.Person p4("name4",50);38.Person p5("name 5",60);39.//队列容器40.41.queue<Person>q;42.43.q.push(p¹);44.q.push(p2)q.push(p3);45.46.q.push(p4);47.q.push(p5);48.
49.
50.
51.
52.53.
54.
55.
56.
57.
58.
59.
cout <<"front.name ="<<q.front().name <<",front.age ="<<q.front().age<<endl;
cout <<"back.name ="<<q.back().nam
e <<",back.age ="<<q.back().age <<e
ndl;
//遍历
while(!q.empty())
{
cout <<"front.name ="<<q.front
().name <<",front.age ="<<q.front().
age <<endl;//出队
q·pop();
}
}
运行结果：
front.name =namel,front.age =20back.name =name5,back.age =60front.name =namel,front.age =20front.name =name2,front.age =30front.name =name3,front.age =40front.name =name4,front.age =50front.name =name5,front.age =60请按任意键继续...
知识点4【list链表容器】push_font()push_back)front()链表节点back()datadatadatadatapop_back()null prevprevprevprev→nullnextnextnextnextpop_front()begin()insert()end()
01.|/*02.3.6.4.1 list构造函数03.list<T>1stT;//list采用采用模板类实现，对象的默认构造形式：
list(beg,end);//构造函数将(beg,end)区间中的04.元素拷贝给本身。
05.list(n,elem);//构造函数将n个elem拷贝给本身。
06.list(const list &lst);//拷贝构造函数。
07.|3.6.4.2 list数据元素插入和删除操作
push_back(elem);//在容器尾部加入一个元素08.09.pop-back();//删除容器中最后一个元素push_front(elem);//在容器开头插入一个元素10.
pop-front();//从容器开头移除第一个元素11.insert(pos,elem);//在pos位置插elem元素的拷12.贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数13.据，无返回值。insert(pos,beg,end);//在pos位置插入14.(beg,end)区间的数据，无返回值。
clear();//移除容器的所有数据15.erase(beg,end);//删除[beg,end]区间的数据，返16.回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据17.的位置。
18.remove(elem);//删除容器中所有与elem值匹配的元素。
19.*/
20.void printListInt(list<int>&L)21.
{
22.for(list<int>::iterator it=L.begin();it!=L.end();it++)23.{24.cout <<*it<<"";25.}26.cout <<end1;27.}28.void test01()29.{30.list<int>L1(5,10);31.list<int>L2 =L1;32.33.printListInt(L2);34.35.list<int>L3;36.L3.push_back(10);37.L3.push_back(20);38.L3.push_back(10);39.L3.push_back(40);40.
41.
L3.push_front(50);
42.
L3.push_front(10);
43.
L3.push_front(70);
44.
printListInt(L3).
45.
46.
//insert:L3.begin()+3失败是因为list的迭代器是双向迭代器而不是随机迭代器
47.
48.
49.
50.
51.
L3.insert(++L3.begin(),3,1000);printListInt(L3);L3.erase(--L3.end());printListInt(L3);
52.
L3.remove(10);//删除所有元素值为10的节53.点printListInt(L3);54.55.}
运行结果：
10101010107010501020104070100010001000105010201040701000100010001050102010701000100010005020请按任意键继续..·
2、链表的排序
01. /*
02.3.6.4.3 list大小操作
03.size();//返回容器中元素的个数
04.empty();//判断容器是否为空
05.resize(num);//重新指定容器的长度为num,
06.若容器变长，则以默认值填充新位置。
如果容器变短，则末尾超出容器长度的元素被删除。07.
resize(num,elem);//重新指定容器的长度为08.num,
若容器变长，则以elem值填充新位置。09.
如果容器变短，则末尾超出容器长度的元素被删除。10.
11.
3.6.4.4 list赋值操作12.
13.assign(beg,end);//将(beg,end)区间中的数据拷贝赋值给本身。
assign(n,elem);//将n个elem拷贝赋值给本身。14.list&operator=(const list &lst);//重载等15.号操作符
swap(Ist);//将1st与本身的元素互换。16.
3.6.4.5 list数据的存取17.
front();//返回第一个元素。18.
back();//返回最后一个元素。19.
20.*/
21.class myGreater//函数对象
22.{
23.public:
bool operator()(int v1,int v2)24.
{25.
26.return v1>v2;
27.
了
28.};
29.void test02()
30.
{
31.
list<int>L1(5,10);
32.
cout <<"size ="<<L1.size()<<end
1;
33.
list<int>L2(5,1000);
34.printListInt(L1);
35.printListInt(L2);
36.
37.L1.swap(L2);
printListInt(L1);38.
39.printListInt(T2)
40.
41.
//链表的反转
42.list<int>L3;L3.push_back(10);43.44.L3.push_back(20);L3.push_back(30);45.46.L3.push_back(40);47.printListInt(L3);48.L3.reverse();49.printListInt(L3);
50.
51.
//链表排序
list<int>L4;52.L4.push_back(10);53.54.L4.push_back(40);55.L4.push_back(30);56.L4.push_back(20);printListInt(L4);57.
58.
59.
//不识别系统算法sort系统算法只用于随机迭代器而链表的迭代器是双向迭代器
60.
61.
//sort(L4.begin(),L4.end());//L4.sort(greater<>());//greater<>()
系统的函数对象(内建函数对
象)#include<functional>
62.
L4.sort(myGreater());
//更改排序规则(函数对象，提供策略)63.
64.
65.printListInt(L4);
66.
}
运行结果：
isize=5-1010101010:100010001000100010001000100010001000100010101010104102030404030201071040302040302010请按任意键继续..·
3、链表对自定义数据的删除排序(注重载==以及自定义排序规则)
01./*
3.6.4.3 list大小操作02.
03.size();//返回容器中元素的个数
04.empty();//判断容器是否为空
05.resize(num);//重新指定容器的长度为num,
若容器变长，则以默认值填充新位置。06.
07.如果容器变短，则末尾超出容器长度的元素被删除。
08.resize(num,elem);//重新指定容器的长度为num,
若容器变长，则以elem值填充新位置。09.
如果容器变短，则末尾超出容器长度的元素被删除。10.
11.
12.3.6.4.4 list赋值操作
assign(beg,end);//将[beg,end]区间中的数据13.拷贝赋值给本身。
assign(n,elem);//将n个elem拷贝赋值给本身。14.
list&operator=(const list&lst);//重载等15.号操作符
swap(1st);//将1st与本身的元素互换。16.
17.3.6.4.5 list数据的存取
18.front();//返回第一个元素。
19.back();//返回最后一个元素。
20.
*/
21.//链表存放自定义数据类型22.23.class Person {24.25.public:26.string name;27.int age;28.int score;29.Person(string name,int age,int score30.31.this->name =name;32.this->age =age;33.this->score =score;34.}35.//重载==形参加const修饰bool operator==(const Person &ob)36.37.38.if((this->name ==ob.name)&&(this->age ==ob.age)&&(this->score ==ob.score))39.{40.return true;41.}return false;42.43.}44.};45.void printListPerson(list<Person>&L)46.{47.for(list<Person>::iterator it=L.begin();it!=L.end();it++)48.49.|cout <<"name ="<<(*it).name <<",age ="<<(*it).age <<",score="<<(*it).score <<endl;50.}51.}52.class myComapre53.54.public:55.bool operator()
(Person &ob1,Person &ob2)
56.
57.
return ob1.age>ob2.age;
58.}59.60.61.};62.bool myComapre2(Person &ob1,Person &ob2)63.64.if(ob1.age ==ob2.age)65.return ob1.score>ob2.score;66.return ob1.age >ob2.age;67.}68.void test03()69.70.Person p1("name1",20,88);71.Person p2("name2",10,99);72.Person p3("name3",30,77);73.Person p4("name4",40,86);74.Person p5("name5",30,55);75.Person p6("name6",90,75);76.Person p7("name7",30,65);77.Person p8("name8"50,95);78.79.list<Person>L;80.L.push_back(p1);81.L.push_back(p2);82.L.push_back(p3);83.L.push_back(p4);84.L.push_back(p5);85.L.push_back(p6);86.L.push_back(p7);87.L.push_back(p8);88.
89.
printListPerson(L);
90.
91.
//排序：自定义数据必须实现排序规则
92.
//L.sort(myComapre());//myComapre()函数对象+()
93.
94.
95.
96.
97.
98.
//L.sort(myComapre2);//myComapre2普通函数不加()cout <<"---------------"<<endl;printListPerson(L);<<end1;cout <<"//删除自定义数据：重载==运算符L.remove(p6);
99.printListPerson(L);100.
运行结果：
,score=88Iname =namel,age =20,score=99name =name2,age =10,score=77ageEname =name3,score=86name =name4,agescore=55name =name5,agescore=75name =name6,score=65name =name7,30,age二score=95ename =name8,=50,age而score=75name =name6,age =90,score=9550,'name =name8,agescore=86name=name4,40,agescore=77name =name3,age30,score=55name =name5, agescore=65是name =name7,agescore=8820,name =namel,agescore=99=10,yname =name2,age请按任意键继续...
Ⅲ严
序列式容器：vector单端数组deque双端数组stack栈queue队列list链表关联式容器：set/multisetmap/multimap
知识点5【set容器】
set容器不允许有相同的元素对插入的数据自动排序
set容器的元素就是键值键值(唯一不变)
set容器的迭代器是只读迭代器(不允许修改元素)
01. /*
02.3.7.2.1 set构造函数
03.set<T>st;//set默认构造函数：
04.mulitset<T>mst;//multiset默认构造函数：
05. set(const set &st);//拷贝构造函数
06. 3.7.2.2 set赋值操作
07. set&operator=(const set &st);//重载等号操作符
08. swap(st);//交换两个集合容器
09.3.7.2.3 set大小操作
10.size();//返回容器中元素的数目
11. empty();//判断容器是否为空
12.
13. 3.7.2.4 set插入和删除操作
14.insert(elem);//在容器中插入元素。
15.clear();//清除所有元素
16.erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg,end);//删除区间(beg,end)的所有元17.素,返回下一个元素的迭代器。
erase(elem);//删除容器中值为elem的元素。18.
19.*/
20.void printSetInt(set<int>&s)
21.
22.for(set<int>::const_iterator it=s.begin();it!=s.end();it++)23.{24.cout <<*it <<"";25.}26.cout <<endl;27.}28.void test01()29.30.set<int>s1;31.s1.insert(3);
32.s1.insert(5);33.s1.insert(2);34.s1.insert(1);35.s1.insert(4);36.37.printSetInt(s1);38.set<int>s2;39.s2.insert(10);40.s2.insert(30);41.s2.insert(20);42.printSetInt(s2);43.44.s1.swap(s2);45.printSetInt(s1);46.printSetInt(s2);47.s2.erase(5);48.printSetInt(s2);49.}
运行结果：
.wOIK\stuue J_C++_33(2U12345102030102030123451234请按任意键继续..·
set容器的查找find
01. /*
3.7.2.5 set查找操作02.
03.find(key);//查找键key是否存在，若存在，返回该键的元素的迭代器；若不存在，返回set.end();04.count(key);//查找键key的元素个数
05. lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个06.key>keyE]em元素的迭代器
equal_range(keyElem);//返回容器中key与07.keyElem相等的上下限的两个迭代器。
08.*/
09.void test021
10.
{
11.
set<int>s1;
12.
s1.insert(3);
13.
s1.insert(5);
14.
s1.insert(2);
15.
s1.insert(1);
16.
s1.insert(4);
17.
18.
set<int>::iterator ret;
19.
ret = s1.find(4).
20.
if(ret ==s1.end())//失败返回的end()
21.
{
22.
cout <<“未找到相关数据”<<endl;
23.
}
24.
else
25.
{
26.
cout <<"找到相关数
据："<<*ret<<end1;
27.
}
28.
29.
//count统计元素的个数对于set容器来说结
果只有0或1因为set的元素唯一
30.
cout <<"cout(4)="<<s1.count(4)<
<end1;
31.
cout <<"cout(4)="<<s1.count(40)
<<endl;
32.
33.//lower_bound(keyElem);//返回第一个34.key>=keyE7em元素的迭代器
//s1 12345
35.
ret =s1.lower_bound(3);//返回3的迭代
器if(ret ==s1.end())//失败返回的end(){cout <<“未找到相关数据”<<endl;}else{cout <<"找到相关数据："<<*ret <<end1;}//upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。//s112345ret =s1.upper_bound(3);if(ret ==s1.end())//失败返回的end(){cout <<“未找到相关数据”<<endl;}else{cout <<"找到相关数据："<<*ret <<end1;}//equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。//s112345//pair对组pair<set<int>::iterator,set<int>::iterator>p1;p1 =s1.equal_range(3);if(p1.first !=s1.end())cout <<"找到3的lower_bound ="<<*(p1.first)<<end1;}if(p1.second !=s1.end()){cout <<"找到3的upper_bound = " <<
(p1.second)<<end1;
}
36.37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.70.71.
运行结果：
找到相关数据：4cout(4)=1cout(4)=0找到相关数据：3找到相关数据：4找到3的lower_bound =3找到3的upper_bound =4请按任意键继续...
2、详解对组
曰void test03(//用pair定义对组//对组定义方式1:pair<string,int>pl("namel",200);//对组定义方式2:pair<string,int>p2=make_pair("name2",300);cout <<p1.first <<","<<p1.second <<endl;cout <<p2.first <<","<<p2.second <<endl;
□ D:workstudentbi_c++33(201
请按任意键继续.·
3、通过insert推出multiset
01.void test04()02.03.set<int>s;04.pair<set<int>::iterator,bool>ret;05.ret =s.insert(10);if(ret.second ==true)06.07.{08.cout <<"第一次插入成功"<<end1;09.}10.else11.{cout <<"第一次插入失败"<<endl;12.13.14.15.ret=s.insert(10);
16.if(ret.second ==true)17.{18.cout <<"第二次插入成功"<<endl;19.}20.else21.{cout <<"第二次插入失败"<<endl;22.23.}24.
//就要插入两个相同的数25.multiset<int>s2;26.27.s2.insert(20);28.s2.insert(20);29.s2.insert(20);30.for(multiset<int>::iterator it=s2.begin();it!=s2.end();it++)31.{32.cout <<*it <<"";33.?34.cout <<endl;35.36.}
运行结果：
第一次插入成功第二次插入失败
202020
请按任意键继续..·
4、修改set容器的排序规则
01.
class myCompare
02.{
03.public:
04.
bool operator()(int val1,int va12)
05.
了
06.
return val1>val2;
07.
飞
08.
09.
};
10.
void test05()
11.
了
12.
//修改set容器的排序规则必须在insert之前确
定
13.
set<int,myCompare>s1;
14.
15.
s1.insert(3);
16.
s1.insert(5);
17.
s1.insert(2);
18.
s1.insert(1);
19.
s1.insert(4);
20.
21.//sort(s1.begin(),s1.end());//不识
别 set的元素一定确定不允许修改
22.for(set<int,myCompare>::iterator it=s1.begin();it!=s1.end();it++)23.{24.cout <<*it <<"";飞25.26.cout <<endl;27. }
运行结果：
54321请按任意键继续.
5、set存放自定义数据必须实现排序规则
01.class Person02.{03.public:04.string name;05.int age;06.Person(string name,int age)07.{08.this->name =name;09.this->age =age;}10.11.};12.class myComparePerson13.{14.public:15.bool operator()(const Person &ob1,const Person &ob2)16.了17.return ob1.age>ob2.age;18.}19.};20.21.void test06()22.{23.set<Person,myComparePerson>s;24.25.s.insert(Person("name1",30));26.s.insert(Person("name2",10));27.s.insert(Person("name3",50));28.s.insert(Person("name4",20));29.s.insert(Person("name5",40));30.31.for(set<Person,myComparePerson>::iterator it=s.begin();it!=s.end();it++)32.{33.cout <<"name ="<<(*it).name <",age ="<<(*it).age <<endl;34.}35.}
运行结果：D:\work\student\bJ_c++_33(20181name =name3,age=50name =name5,age =40name =namel,age =30
*iname =name4,age =20name =name2,age =10请按任意键继续. . .
知识点6【map】
01./*
3.8.2.1 map构造函数02.
03.map<T1,T2>mapTT;//map默认构造函数：
map(const map &mp);//拷贝构造函数04.
05.
06.3.8.2.2 map赋值操作
map&operator=(const map &mp);//重载等号操07.作符
08. swap(mp);//交换两个集合容器
09.
10. 3.8.2.3 map大小操作
11. size();//返回容器中元素的数目
12. empty();//判断容器是否为空
13. 3.8.2.4 map插入数据元素操作
14.map.insert(...);//往容器插入元素，返回pair<iterator,bool>
15.|map<int,string>mapStu;
//第一种通过pair的方式插入对象16.
17.mapStu.insert(pair<int,string>(3,"小张"));
18.//第二种通过pair的方式插入对象
19.mapStu.inset(make_pair(-1,"校长"));
20.//第三种通过value_type的方式插入对象
21.mapStu.insert(map<int,string>::value_type(1,"小李"));
22.//第四种通过数组的方式插入值
23.mapStu[3]="小刘";
24.mapStu[5]="小王";
25. 3.8.2.5 map删除操作
26. clear();//删除所有元素
27. erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
28.erase(beg,end);//删除区间(beg,end)的所有元素，返回下一个元素的迭代器。
erase(keyElem);//删除容器中key为keyElem的对29.组。
30.*/
31.
32.void test01()
33.{34.//1---100 2---200 3---300 4--
4005---500
35.map<int,int>m1;
//方式1:36.
37.
m1.insert(pair<int,int>(4,400));
//方式2:38.
39.m1.insert(make_pair(3,300));
//方式3:40.
41.
m1.insert(map<int,int>::value_type(1
,100));
//方式4:插入时不推荐42.
43.m1[5]=500;
44.m1[2]=200;
45.
46.//[]插入数据的时候如果不存在自动填0
47.cout <<m1[5]<<endl;
48.
for(map<int,int>::iterator it=m1.be
gin();it!=m1.end();it++)
49.
{
50.
//*it是一个对组
51.
cout <<"key ="<<(*it).first <
<",value ="<<(*it).second <<endl;
52.
53.
54.
//只遍历value
55.
for(int i=0;i<m1.size();i++)
56.
{
57.
cout <<m1[i+1]<<"";
58.
}
cout <<endl;59.
60.
61.
}
运行结果：
500key =1,value =100lkey =2,value =200key =3,value =300key =4,value =400key =5,value =500100200300400500请按任意键继续..·
案例：
for(map<int.Person>::iterator it=m.begin():it!=m.end():it++
cout《"编号："《(*it).first《",选手姓名："《(*it).second.name《",选手age:"《(*it).second.age\
案例：
01.void test03()02.{03.vector<int>v;04.v.push_back(9527);05.v.push_back(10086);06.v.push_back(1024);07.v.push_back(100);08.v.push_back(200);09.10.map<int,Person>m;11.for(vector<int>::iterator it =v.begn();it !=v.end();it++)12.{cout <<“请为选手"<<*it<<"输入13.name age score"<<endl;14.Person p;
15.
cin >>p.name >>p.age >>p.score
16.//将数据插入map容器中17.
m.insert(make_pair(#it,p));18.
19.
}
20.
21.//遍历容器
22.for(vector<int>::iterator it =v.begin();it !=v.end();it++)
23.
24.
cout <<"编号："<<#it<<"选手
name="<<m[*it].name <<",age="<<m[*i
t].age <<",score="<<m[*it].score <<e
ndl;
25.
子
26.
27.
sort(v.begin(),v.end());
28.
cout <<"
<<endl;
29.
for(vector<int>::iterator it =v.beg
in();it !=v.end();it++)
30.
31.
cout<<“编号："<<*it<<”选手
name="<<m[*it].name <<",age="<<m[*i
t].age <<",score="<<m[*it].score <<e
nd1;
32.}//打乱容器数据33.
34.
random_shuffle(v.begin(),v.end());
35.
cout <<"
<<endl;
36.
for(vector<int>::iterator it =v.beg
in();it !=v.end();it++)
37.{cout <<"编号："<<*it<<“选手38.name="<<m[*it].name <<",age="<<m[*it].age <<",score="<<m[*it].score <<end1;
39.
}
40.
运行结果：
请为选手9527输入name age score灵lucy 1888气请为选手10086输入name age scorebob 1999d请为选手1024输入name age scoretom 2030请为选手100输入name age scorehehe 1555d请为选手200输入name age scorepheihei 1777编号：9527选手name=lucy,age=18,score=88S编号：10086选手name=bob,age=19,score=99编号：1024选手name=tom,age=20,score=30编号：100选手name=hehe,age=15,score=55编号：200选手name=heihei,age=17,score=77编号：100选手name=hehe,age=15,score=55籍编号：200选手name=heihei,age=17,score=77编号：1024选手name=tom,age=20,score=30编号：9527选手name=lucy,age=18,score=88S编号：10086选手name=bob,age=19,score=99第------
/编号：10086选手name=bob,age=19,score=99编号：200选手name=heihei,age=17,score=77编号：9527选手name=lucy,age=18,score=88编号：1024选手name=tom,age=20,score=30绝只：100选毛 - -16 -66隔报在益链能续
2、map的查找
01./*
3.8.2.6 map查找操作02.
find(key);//查找键key是否存在，若存在，返回该键03.的元素的迭代器；/若不存在，返回map.end();
count(keyElem);//返回容器中key为keyElem的对04.组个数。对map来说，要么是0,要么是1。对multimap来说，值可能大于1。
05.lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个06.key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与07.keyElem相等的上下限的两个迭代器。
08.*/09.void test04()10.{11.map<int,int>m;12.m.insert(make_pair(1,100));13.m.insert(make_pair(2,200));14.m.insert(make_pair(4,400));15.m.insert(make_pair(5,500));16.m.insert(make_pair(3,300));17.18.map<int,int>::iterator ret;19.ret =m.find(4);20.if(ret !=m.end())21.{cout <<"找22.到：key ="<<(*ret).first <<",value ="<<(*ret).second <<endl;23.}24.pair<map<int,int>::iterator,map<int,int>::iterator>ret2;25.ret2 =m.equal_range(3);26.if(ret2.first !=m.end())27.{cout <<"上限找28.到：key ="<<(*ret2.first).first<<",value ="<<(*ret2.first).second <<endl;29.
30.
?
if(ret2.second !=m.end())31.
32.{
33.
cout <<"下限找
到：key ="<<(*ret2.second).first <<",
value ="<<(*ret2.second).second <<end
1;
34.}
35. }
运行结果：
找到：key =4,value =400上限找到：key =3,value =300下限找到：key =4,value =400请按任意键继续...
3、修改map容器的排序规则void test050map<int,int,myCompareMap>m;m.insert(make_pair(1,100));m.insert(make_pair(2,200));m.insert(make_pair(4,400));m.insert(make_pair(5,500));m.insert(make_pair(3,300));for (map<int,int,myCompareMap>::iterator it=m.begin();it!=m.end();it++){cout<<"key ="<<(*it).first<<",value ="<<(*it).second <<endl;}D:work\studentbj_c++_33(20181017\STL\O1_code\day02104_map\Debug\04_map.exeint main(int *argc,char *argv[])2le0test050;请按任意键继续..system("pause");return EXIT SUCCESS:知识点7【multimap允许key值重复】avoid test06(multimap<int,int>m;m.insert(make_pair(1,100));m.insert(make_pair(1,200));m.insert(make_pair(3,400));m.insert(make_pair(3,500));
m.insert(make_pair(3,300));for(multimap<int,int>::iterator it =m.begin();it !=m.end();it++)
cout <<"key ="<<(*it).first <<",value="<<(*it).second <<endl;
D:work\student\bj_c++_33(20181017\STL\01_code\day02\04map\Debug\04_D:work\student\bj_c++
白int main(int *argc,char *argv[])
key =1,value =100key =1,value =100
test06();system("pause");return EXTT SICCESS·
key =3,value =400key =3,value =400
key =3,value =500key =3,value =500key =3,value =300key =3,value =300请按任意键继续.·请按任意键继续.·