C++ 面向对象程序设计 14万字总结笔记（一）

这些“容器”有list，vector，set，map等，STL也是算法和其他⼀些组件的集合。STL的⽬的是标准化
组件，这样就不⽤重新开发，可以使⽤现成的组件。STL现在是C++的⼀部分，因此不⽤安装额外的
库⽂件。
什么意思呢，⽐如说刷算法过程中需要⽤到集合 set ，我们知道 set 的特点是集合内的元素不重复
（特别地，在 C++ ⾥⾯， set 是会⾃动排序的集合， unordered_set 是不会⾃动排序的集合），⽐如
在set⾥分别放进 4、1、1、2、3 这⼏个元素，set⾥会⾃动变成 1、2、3、4 ，如果我们只会C语⾔，可
能需要⼀个个把数据放到数组⾥⾯，然后⼿动编写⼀些代码，检查进来的每⼀个元素在数组中是否已
经存在，如果存在就不要再放进数组，最后对整个数组进⾏排序，才能达到set的效果。但是如果直接
使⽤ C++ ，我们就可以在头⽂件⾥⾯加个 #include <set> ，然后直接把 set 当作⼀个类似于数组的容
器，把所有元素直接丢到⾃⼰定义的这个set类型的容器⾥，就会⾃动实现去重（去除重复元素）和排
序的步骤～⽐如说题⽬要求将最后所有的答案去重后按从⼩到⼤的顺序输出，就可以直接将所有的答
案元素放到set⾥⾯输出即可～这样我们在刷题过程中就能更好地集中精⼒解决代码思路、算法⽅⾯的
问题，⽽不是⼀个简单的答案输出或语法⽅⾯的问题，在考试过程中也能⼤⼤地节省时间，降低代码
的错误率～

给定一个K进制数，求它是多大
假设有一个n+1位的K进制数，它的形式如下：
AnAn-1An-2。。。。。。A2A1A0 (比如 八进制数 1723)
则其大小为：
A0×K0 + A1×K1 + ……+ An-1×Kn-1+ An×Kn
数就是数，没有进制之分，只有数的表示形式，才有进制之分。
所谓“十进制数”，是“数的十进制表示形式" 的简称。 
给定一个数，求其K进制表示形式
10
 求数的K进制表示形式 -- 短除法
给定一个整数N和进制K，那么N可表示成以下形式：
N = A0×K0+A1×K1+A2×K2+……+An-1×Kn-1+An×Kn
= A0 +K (A1 +A2×K1+……+An-1×Kn-2+An×Kn-1
)
N除以K所得到的余数是A0，商是A1+A2×K1+……+An-1×Kn-2+An×Kn-1。将这个商再除
以K，就得到余数A1，新的商是
A2 + A3×K1+……+An-1×Kn-3+An×Kn-2
不停地将新得到的商除以K，直到商变成0，就能依次求得A0 、A1、 A2 …… An-1 、An
。显然，Ai <K ( i = 0…n)，且最终得到的K进制数就是:
AnAn-1An-2。。。。。。A2A1A0
K进制小数
11
K进制小数 0.A0A1……An的值是：
A0×K-1+A1×K-2+……+An×K-(n+1) 
(0.12)10 = 1 ×10-1 + 2 ×10-2
(0.1)3 = 1 ×3
-1 即1/3, 表示成10进制就是无限循环小数
可见，n进制下的有限位小数，在m进制下可能就无法精确表示，因为会无限
循环
十进制有限位小数，在二进制的情况未必能用有限位数表示出来。计算机内
存有限，不可能存放无限位，因此计算机的小数运算会有误差。比如，计算
机其实无法精确表示 4.9，只能精确表示4.899999999...之类一个很接近的数 

sizeof(变量名)
sizeof(类型名)
能够得到某个变量或某一类型变量占用的字节数
int n1 = 10;
double f;
char c;
printf("%d,%d,%d,%d",sizeof(n1),sizeof(short),
sizeof(double),sizeof(c));
输出： 4,2,8,1

字符型数据可以转换成整型数据
int k = 'a' ; //k内容变为'a'的ASCII码，即97
printf("%d",k) ; //输出：97
 整型数据也可以转换为字符型数据，但只会留下最右边的一个字节（第0位
到第7位），其他字节丢弃
int n = 98;
char k = n ; //k内容变98,98是字符'b'的ASCII码
printf("%c",k) ; //输出：b

#include <cstdio>
#include <iostream>
using namespace std;
int main() {
int n1 = 1378; //1378的十六进制形式是 0x562
short n2;
char c = 'a';
double d1 = 7.809;
double d2;
n2 = c+1; //n2变为98 , 97是'a'的ASCII码
printf("c=%c,n2=%d\n",c,n2); //输出 c=a,n2=98
c = n1; // n1是0x562, 0x62被当做ASCII码赋值给c,c变为 'b'
printf("c=%c,n1=%d\n",c,n1); //输出 c=b,n1=1378
n1 = d1; // d1=7.809, 去掉小数部分后赋值给n1,n1变为7
printf("n1=%d\n", n1); //输出 n1=7
d2 = n1; //d2变为7
printf("d2=%f\n",d2); //输出 d2=7.000000
return 0;

用“struct”关键字来定义一个“结构”，也就定义了一个新的数据类型：
struct 结构名
{
类型名 成员变量名；
类型名 成员变量名；
类型名 成员变量名；
……
}

struct Student {
unsigned ID;
char szName[20];
float fGPA;
};
Student 即成为自定义类型的名字，可以用来定义变量
Stuent s1,s2;

StudentEx stu;
cin >> stu.fGPA;
stu.ID = 12345;
strcpy(stu.szName, "Tom");
cout << stu.fGPA;
stu.birthday.year = 1984;
unsigned int * p = & stu.ID; //p指向stu中的ID成员变量
11
struct Date {
int year;
int month;
int day;
};
struct StudentEx {
unsigned ID;
char szName[20];
float fGPA;
Date birthday;
};

标识符的作用域
void Func(int m)
{
for( int i = 0; i < 4;++i ) {
if( m <= 0 ) {
int k = 3;
m = m *( k ++ );
}
else {
k = 0; //编译出错，k无定义
int m = 4;
cout << m;
}
}
i= 2; //编译出错，i无定义
}

void Func(int m)
{
for( int i = 0; i < 4;++i ) {
if( m <= 0 ) {
int k = 3;
m = m *( k ++ );
}
else {
k = 0; //编译出错，k无定义
int m = 4;
cout << m;
}
}
i= 2; //编译出错，i无定义
}
32

对基本类型的数组从小到大排序: 
sort(数组名+n1，数组名+n2）;
n1和n2都是int类型的表达式，可以包含变量
如果n1=0,则 + n1可以不写
将数组中下标范围为[n1,n2)的元素从小到大排序。下标为n2的元素不在排序
区间内
用sort进行排序(用法一)
int a[] = {15,4,3,9,7,2,6};
sort(a,a+7); //对整个数组从小到大排序
int a[] = {15,4,3,9,7,2,6};
sort(a,a+3); // 结果：{3,4,15,9,7,2,6}
int a[] = {15,4,3,9,7,2,6};
sort(a+2,a+5); //结果：{15,4,3,7,9,2,6}
7
用sort进行排序(用法二)
对元素类型为T的基本类型数组从大到小排序：
sort(数组名+n1，数组名+n2,greater<T>()）;
int a[] = {15,4,3,9,7,2,6};
sort(a+1,a+4,greater<int>()); // 结果：{15,9,4,3,7,2,6}
8
用sort进行排序(用法三)
用自定义的排序规则，对任何类型T的数组排序
sort(数组名+n1，数组名+n2,排序规则结构名());
排序规则结构的定义方式：
struct 结构名
{
bool operator()( const T & a1,const T & a2) const {
//若a1应该在a2前面，则返回true。
//否则返回false。
}
}; 9
sort排序规则注意事项
struct 结构名
{
bool operator()( const T & a1,const T & a2) const {
//若a1应该在a2前面，则返回true。
//否则返回false。
}
};
排序规则返回 true，意味着 a1 必须在 a2 前面
返回 false，意味着 a1 并非必须在 a2 前面
排序规则的写法，不能造成比较 a1,a2 返回 true 比较 a2,a1 也返回 true 
否则sort会 runtime error
比较 a1,a2 返回 false 比较 a2,a1 也返回 false，则没有问题
10
用sort进行排序(用法三)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct Rule1 //按从大到小排序
{
bool operator()( const int & a1,const int & a2) const {
return a1 > a2;
}
};
struct Rule2 //按个位数从小到大排序
{
bool operator()( const int & a1,const int & a2) const {
return a1%10 < a2%10;
}
};
11
用sort进行排序(用法三)
void Print(int a[],int size) {
for(int i = 0;i < size;++i) 
cout << a[i] << "," ;
cout << endl;
}
int main()
{
int a[] = { 12,45,3,98,21,7};
sort(a,a+sizeof(a)/sizeof(int)); //从小到大
cout << "1) "; Print(a,sizeof(a)/sizeof(int));
sort(a,a+sizeof(a)/sizeof(int),Rule1()); //从大到小
cout << "2) "; Print(a,sizeof(a)/sizeof(int));
sort(a,a+sizeof(a)/sizeof(int),Rule2()); //按个位数从小到大
cout << "3) "; Print(a,sizeof(a)/sizeof(int));
return 0;
}
1) 3,7,12,21,45,98,
2) 98,45,21,12,7,3,
3) 21,12,3,45,7,98,
用sort对结构数组进行排序(用法三)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct Student {
char name[20];
int id;
double gpa;
};
Student students [] = { 
{"Jack",112,3.4},{"Mary",102,3.8},{"Mary",117,3.9},
{"Ala",333,3.5},{"Zero",101,4.0}};
13
用sort对结构数组进行排序(用法三)
struct StudentRule1 { //按姓名从小到大排
bool operator() (const Student & s1,const Student & s2) const {
if( stricmp(s1.name,s2.name) < 0)
return true;
return false;
}
};
struct StudentRule2 { //按id从小到大排
bool operator() (const Student & s1,const Student & s2) const {
return s1.id < s2.id;
}
};
struct StudentRule3 {//按gpa从高到低排
bool operator() (const Student & s1,const Student & s2) const {
return s1.gpa > s2.gpa;
}
};
14
用sort对结构数组进行排序(用法三)
void PrintStudents(Student s[],int size){
for(int i = 0;i < size;++i)
cout << "(" << s[i].name << "," 
<< s[i].id <<"," << s[i].gpa << ") " ;
cout << endl;
}
15
用sort对结构数组进行排序(用法三)
int main()
{
int n = sizeof(students) / sizeof(Student);
sort(students,students+n,StudentRule1()); //按姓名从小到大排
PrintStudents(students,n);
sort(students,students+n,StudentRule2()); //按id从小到大排
PrintStudents(students,n);
sort(students,students+n,StudentRule3()); //按gpa从高到低排
PrintStudents(students,n);
return 0;
}
(Ala,333,3.5) (Jack,112,3.4) (Mary,102,3.8) (Mary,117,3.9) (Zero,101,4)
(Zero,101,4) (Mary,102,3.8) (Jack,112,3.4) (Mary,117,3.9) (Ala,333,3.5)
(Zero,101,4) (Mary,117,3.9) (Mary,102,3.8) (Ala,333,3.5) (Jack,112,3.4)

STL提供在排好序的数组上进行二分查找的算法
binary_search
lower_bound
upper_bound
18
用binary_search进行二分查找（用法一）
在从小到大排好序的基本类型数组上进行二分查找
binary_search(数组名+n1，数组名+n2,值); 
n1和n2都是int类型的表达式，可以包含变量
如果n1=0,则 + n1可以不写
查找区间为下标范围为[n1,n2)的元素，下标为n2的元素不在查找区间内
在该区间内查找"等于"值”的元素，返回值为true(找到）或false(没找到）
"等于"的含义： a 等于 B <=> a < b和b < a都不成立
19
用binary_search进行二分查找（用法二）
在用自定义排序规则排好序的、元素为任意的T类型的数组中进行二分查找
binary_search(数组名+n1，数组名+n2,值，排序规则结构名()); 
n1和n2都是int类型的表达式，可以包含变量
如果n1=0,则 + n1可以不写
查找区间为下标范围为[n1,n2)的元素，下标为n2的元素不在查找区间内
在该区间内查找"等于"值的元素，返回值为true(找到）或false(没找到）
查找时的排序规则，必须和排序时的规则一致！
"等于"的含义： a 等于 b <=> "a必须在b前面"和"b必须在a前面"都不成立20
用binary_search进行二分查找（用法二）
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct Rule //按个位数从小到大排
{
bool operator()( const int & a1,const int & a2) const {
return a1%10 < a2%10;
}
};
void Print(int a[],int size) {
for(int i = 0;i < size;++i) {
cout << a[i] << "," ;
}
cout << endl;
}
用binary_search进行二分查找（用法二）
int main() {
int a[] = { 12,45,3,98,21,7};
sort(a,a+6);
Print(a,6);
cout <<"result:"<< binary_search(a,a+6,12) << endl;
cout <<"result:"<< binary_search(a,a+6,77) << endl;
sort(a,a+6,Rule()); //按个位数从小到大排
Print(a,6);
cout <<"result:"<< binary_search(a,a+6,7) << endl;
cout <<"result:"<< binary_search(a,a+6,8,Rule()) << endl;
return 0;
}
22
3,7,12,21,45,98,
result:1
result:0
21,12,3,45,7,98,
result:0
result:1
"等于"的含义： a 等于 b <=> "a必须在b前面"和"b必须在
a前面"都不成立
用binary_search进行二分查找（用法二）
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct Student {
char name[20];
int id;
double gpa;
};
Student students [] = { 
{"Jack",112,3.4},{"Mary",102,3.8},{"Mary",117,3.9},
{"Ala",333,3.5},{"Zero",101,4.0}};
23
用binary_search进行二分查找（用法二）
struct StudentRule1 { //按姓名从小到大排
bool operator() (const Student & s1,const Student & s2) const {
if( stricmp(s1.name,s2.name) < 0)
return true;
return false;
}
};
struct StudentRule2 { //按id从小到大排
bool operator() (const Student & s1,const Student & s2) const {
return s1.id < s2.id;
}
};
struct StudentRule3 {//按gpa从高到低排
bool operator() (const Student & s1,const Student & s2) const {
return s1.gpa > s2.gpa;
}
};
24
用binary_search进行二分查找（用法二）
int main(){
Student s;
strcpy(s.name,"Mary");
s.id= 117;
s.gpa = 0;
int n = sizeof(students) / sizeof(Student);
sort(students,students+n,StudentRule1()); //按姓名从小到大排
cout << binary_search( students , students+n,s,
StudentRule1()) << endl;
strcpy(s.name,"Bob");
cout << binary_search( students , students+n,s,
StudentRule1()) << endl;
sort(students,students+n,StudentRule2()); //按id从小到大排
cout << binary_search( students , students+n,s,
StudentRule2()) << endl;
return 0;
}
用lower_bound二分查找下界(用法一)
在对元素类型为T的从小到大排好序的基本类型的数组中进行查找
T * lower_bound(数组名+n1,数组名+n2,值);
返回一个指针 T * p;
*p 是查找区间里下标最小的，大于等于"值" 的元素。如果找不到，p指向下标为n2的
元素
26
用lower_bound二分查找下界(用法二)
在元素为任意的T类型、按照自定义排序规则排好序的数组中进行查找
T * lower_bound(数组名+n1,数组名+n2,值,排序规则结构名());
返回一个指针 T * p;
*p 是查找区间里下标最小的，按自定义排序规则，可以排在"值"后面的元素。如果找
不到，p指向下标为n2的元素
27
用upper_bound二分查找上界(用法一)
在元素类型为T的从小到大排好序的基本类型的数组中进行查找
T * upper_bound(数组名+n1,数组名+n2,值);
返回一个指针 T * p;
*p 是查找区间里下标最小的，大于"值"的元素。如果找不到，p指向下标为n2的元素
28
用upper_bound二分查找上界(用法二)
在元素为任意的T类型、按照自定义排序规则排好序的数组中进行查找
T * upper_bound(数组名+n1,数组名+n2,值,排序规则结构名());
返回一个指针 T * p;
*p 是查找区间里下标最小的，按自定义排序规则，必须排在"值"后面的元素。如果找
不到，p指向下标为n2的元素
29
lower_bound,upper_bound用法示例
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct Rule 
{
bool operator()( const int & a1,const int & a2) const {
return a1%10 < a2%10;
}
};
void Print(int a[],int size) {
for(int i = 0;i < size;++i) {
cout << a[i] << "," ;
}
cout << endl;
} 30
lower_bound,upper_bound用法示例
#define NUM 7 
int main()
{
int a[NUM] = { 12,5,3,5,98,21,7};
sort(a,a+NUM);
Print(a,NUM); // => 3,5,5,7,12,21,98,
int * p = lower_bound(a,a+NUM,5);
cout << *p << "," << p-a << endl; //=> 5,1
p = upper_bound(a,a+NUM,5);
cout << *p << endl; //=>7
cout << * upper_bound(a,a+NUM,13) << endl; //=>21
31
lower_bound,upper_bound用法示例
sort(a,a+NUM,Rule());
Print(a,NUM); //=>21,12,3,5,5,7,98,
cout << * lower_bound(a,a+NUM,16,Rule()) << endl; // => 7
cout << lower_bound(a,a+NUM,25,Rule()) - a<< endl; // => 3
cout << upper_bound(a,a+NUM,18,Rule()) - a << endl; // => 7
if( upper_bound(a,a+NUM,18,Rule()) == a+NUM)
cout << "not found" << endl; //=> not found
cout << * upper_bound(a,a+NUM,5,Rule()) << endl; // =>7
cout << * upper_bound(a,a+NUM,4,Rule()) << endl; // =>5
return 0;
}

multiset<T> st; 
定义了一个multiset变量st，st里面可以存放T类型的数据，并且能自
动排序。开始st为空
排序规则：表达式 “a < b” 为true，则 a 排在 b 前面
可用 st.insert添加元素，st.find查找元素，st.erase删除元素，复杂度
都是 log(n)
multiset 用法
#include <iostream>
#include <cstring>
#include <set> //使用multiset和set需要此头文件
using namespace std;
int main()
{
multiset<int> st; 
int a[10]={1,14,12,13,7,13,21,19,8,8 };
for(int i = 0;i < 10; ++i)
st.insert(a[i]); //插入的是a [i]的复制品
multiset<int>::iterator i; //迭代器，近似于指针
for(i = st.begin(); i != st.end(); ++i) 
cout << * i << ","; 
cout << endl;
输出：1,7,8,8,12,13,13,14,19,21,
40
multiset 用法
i = st.find(22); //查找22，返回值是迭代器
if( i == st.end()) //找不到则返回值为 end()
cout << "not found" << endl;
st.insert(22); //插入 22
i = st.find(22);
if( i == st.end())
cout << "not found" << endl;
else
cout << "found:" << *i <<endl; 
//找到则返回指向找到的元素的迭代器
输出：
not found
found:22
41
i = st.lower_bound(13);
//返回最靠后的迭代器 it，使得[begin(),it)中的元素
//都在 13 前面 ，复杂度 log(n)
cout << * i << endl;
i = st.upper_bound(8);
//返回最靠前的迭代器 it，使得[it,end())中的元素
//都在 8 后面，复杂度 log(n)
cout << * i << endl;
st.erase(i); //删除迭代器 i 指向的元素，即12
for(i = st.begin(); i != st.end(); ++i) 
cout << * i << ",";
return 0;
}
输出：
13
12
1,7,8,8,13,13,14,19,21,22,
42
1,7,8,8,12,13,13,14,19,21,
multiset 上的迭代器
multiset<T>::iterator p; 
p是迭代器，相当于指针，可用于指向multiset中的元素。访问multiset中的元素要通
过迭代器。
与指针的不同：
multiset上的迭代器可 ++ ，--， 用 != 和 == 比较，不可比大小，不可加减整数，不
可相减
multiset 上的迭代器
multiset<T> st;
st.begin() 返回值类型为 multiset<T>::iterator, 
是指向st中的头一个元素的迭代器
st.end() 返回值类型为 multiset<T>::iterator, 
是指向st中的最后一个元素后面的迭代器
对迭代器 ++ ,其就指向容器中下一个元素，-- 则令其指向上一个元素
44
自定义排序规则的multiset 用法
#include <iostream>
#include <cstring>
#include <set>
using namespace std;
struct Rule1 {
bool operator()( const int & a,const int & b) const { 
return (a%10) < (b%10); 
}//返回值为true则说明a必须排在b前面
};
int main() {
multiset<int,greater<int> > st; //排序规则为从大到小
int a[10]={1,14,12,13,7,13,21,19,8,8 };
for(int i = 0;i < 10; ++i)
st.insert(a[i]);
multiset<int,greater<int> >::iterator i; 
for(i = st.begin(); i != st.end(); ++i) 
cout << * i << ",";
cout << endl;
45 输出：21,19,14,13,13,12,8,8,7,1,
自定义排序规则的multiset 用法
multiset<int,Rule1 > st2;
//st2的元素排序规则为：个位数小的排前面
for(int i = 0;i < 10; ++i)
st2.insert(a[i]);
multiset<int,Rule1>::iterator p; 
for(p = st2.begin(); p != st2.end(); ++p) 
cout << * p << ",";
cout << endl;
p = st2.find(133);
cout << * p << endl;
return 0;
}
输出：
1,21,12,13,13,14,7,8,8,19,
13 46
自定义排序规则的multiset 用法
multiset<int,Rule1 > st2;
//st2的元素排序规则为：个位数小的排前面
for(int i = 0;i < 10; ++i)
st2.insert(a[i]);
multiset<int,Rule1>::iterator p; 
for(p = st2.begin(); p != st2.end(); ++p) 
cout << * p << ",";
cout << endl;
p = st2.find(133);
cout << * p << endl;
return 0;
}
输出：
1,21,12,13,13,14,7,8,8,19,
13 47
find(x): 在排序容器中找一个元素y，使得
“x必须排在y前面”和 “y必须排在x前面”
都不成立
自定义排序规则的multiset 用法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
struct Student {
char name[20];
int id;
int score;
};
Student students [] = { {"Jack",112,78},{"Mary",102,85},
{"Ala",333,92},{"Zero",101,70},{"Cindy",102,78}};
struct Rule {
bool operator() (const Student & s1,const Student & s2) const {
if( s1.score != s2.score) return s1.score > s2.score;
else return (strcmp(s1.name,s2.name) < 0); 
}
}; 48
自定义排序规则的multiset 用法
int main()
{
multiset<Student,Rule> st;
for(int i = 0;i < 5;++i)
st.insert(students[i]); //插入的是students[i]的复制品
multiset<Student,Rule>::iterator p;
for(p = st.begin(); p != st.end(); ++p)
cout << p->score <<" "<<p->name<<" "
<< p->id <<endl;
Student s = { "Mary",1000,85};
p = st.find(s);
if( p!= st.end())
cout << p->score <<" "<< p->name<<" "
<< p->id <<endl;
return 0;
} 49
92 Ala 333
85 Mary 102
78 Cindy 102
78 Jack 112
70 Zero 101
85 Mary 102

set和multiset的区别在于容器里不能有重复元素
a和b重复  “a必须排在b前面” 和“b必须排在a前面”都不成立
set插入元素可能不成功
51
set的用法
#include <iostream>
#include <cstring>
#include <set>
using namespace std;
int main()
{
set<int> st;
int a[10] ={ 1,2,3,8,7,7,5,6,8,12 };
for(int i = 0;i < 10; ++i)
st.insert(a[i]);
cout << st.size() << endl; //输出：8
set<int>::iterator i;
for(i = st.begin(); i != st.end(); ++i)
cout << * i << ","; //输出：1,2,3,5,6,7,8,12,
cout << endl; 
52
set的用法
pair<set<int>::iterator, bool> result = st.insert(2);
if( ! result.second ) //条件成立说明插入不成功
cout << * result.first <<" already exists." 
<< endl;
else
cout << * result.first << " inserted." << endl;
return 0;
} 
输出：
2 already exists.
53
pair<set<int>::iterator, bool> 

struct {
set<int>::iterator first;
bool second;
};
pair模板的用法
pair<T1,T2>类型等价于：
struct {
T1 first;
T2 second;
};
例如：pair<int, double> a; 
等价于：
struct {
int first;
double second;
} a;
a.first = 1;
a.second = 93.93;