C++ 复习 STL库

参照传智播客的黑马的教程 https://www.bilibili.com/video/BV1et411b73Z/?p=2

Standard Template Library(标准模板库)

STL从广义上分为:容器、算法和迭代器 (container、algorithm、iterator)

容器之vector

三种遍历方法

#include<vector>
vector<int> v;
v.push_back(10);
vector<int>::iterator itBegin = v.begin(); //第一个元素的地址(指针)
vector<int>::iterator itEnd = v.end();    //最后一个元素的下一个元素的地址(指针)
while (itBegin != itEnd) {
    cont << * itBegin << endl;
    itBegin++;
}

for (vector<int> ::iterator it = v.begin(); it != v.end(); it++){
    cout<<*it<<endl;
}
#include <algorithm> //标准算法头文件
void myPring(int val){ cout<<val<<endl;}
for_each(v.begin(), v.end(), myPrint); //这里采用了回调函数的技术

自定义类型的容器

vector<Person> v;
for(vector<Person>::iterator it = v.begin(); it != v.end(); it++){
    cout << (*it).name << endl;
}
vecter<Person*>v;
for(vector<Person*>::iterator it = v.begin(); it != v.end(); it++){
    cout << (*(*it)).name << endl;
    cout << (*it)->name <<endl;
}

容器可以嵌套

vector<vector<int>> v;
for (vector<vector<int>>::iterator outerIt = v.begin(); outerIt != v.end(); outerIt ++) {
    for (vector<int> ::iterator innerIt = (*outerIt).begin(); innerIt != (*outerIt).end(); innerIt ++ ) {
        cout << *innerIt << " ";
    }
    cout<<endl;
}

string类,底层就是通过char*来实现的(字符串的字面量实际上时const char * 类型的)

string的四种构造函数

  • string()
  • string (const char * c)
  • string(const & string str)
  • string(int n, char a)

string类内部重载=赋值运算符,还重载了多个,还有提供了assign以及重载的多个方法。

string类内部还重载+=等拼接字符串的方法,还提供了append一些列重载函数。

string类的查找函数find,rfind,一个从左往右找,一个从右边往左边查,并且重载了一系列。

string类的替换函数replace,详细函数的定义需要查查文档。

字符串比较 int compare(const & str)

字符串重载[]实现字符的读写,也提供了at函数提供访问。(这和java不同)下面两种都是合法的。

  • str[1] = ‘a’;
  • str.at(1) = ‘b’;

字符串插入删除 insert() erase()方法

字符串的字串 subStr()

vector

是一个动态的数组,有以下四种方式的构造函数

  • vector()
  • vector(v.begin(), v.end())
  • vector(int n, element)
  • vector(const vector & v)

vector容器可以赋值(重载了operator=),也可以调用assign方法

vector的size() capacity() empty() resize()方法

vector的插入和删除

push_back() pop_back() insert() erase()

vector元素存储 重载[]运算符,调用at(), front() 第一个元素,back()最后一个元素

vector容器的swap()方法

看得懂这个代码吗 vector<int>(v).swap(v)

调用拷贝构造函数创建匿名对象并实现vector的内容交换,一定程度上会节省v中capacity多余的空间浪费,而匿名对象会被系统回收。

reserve()函数,预留空间,减少动态扩容是的复制数据的开销。

deque容器

双端队列 #include<deque>

头部插入的效率高于vector,具体需要数据结构看底层源码

vector访问元素的速度会比deque快

API基本和vector类似,只是多了一些在头部的方法

deque没有capacity()方法,和底层实现有关(中控器)

//deque容器的排序
#include <algorithm>
sort(d.begin(), d.end())

stack容器

#include<stack>

stack<T> stk; stack<T>(const & stack stk); 普通构造和拷贝构造

pop push top 三个方法

size empty 方法

queue容器

#include<queue>

queue<T> que; queue<T>(const & queue que);

pop push front back 方法

size empty 方法

list容器

list表示链表(注意和java中的区别),c++底层实现是双向循环列表

多数的API和vector差不多,但是没有capacity的概念,不支持[] 和at访问,l.begin() 只能++或者– 不能 +=1 +=2 之类的(不支持随机访问)

反转和排序 list<int> l; l.reverse(); l.sort()

所有不支持随机访问迭代器的容器,不可以使用标准算法,(#include <algorithm>),一般来说这种容器的内部会提供对应的成员方法。

bool compare(int v1, int v2){ return v1 > v2; }
l.sort(compare);   //降序排序

自定义数据类型排序需要指定排序规则。

set/multiset

#include<set>

底层是用二叉树来实现的数据结构,是一种关联式容器

set不允许重复元素,multiset允许重复元素

插入元素只能用insert函数,删除erase,清空clear

find函数返回的是迭代器,count函数非1即0(multiset可能是其他值)

    set<int> s;
    pair<set<int>::iterator, bool> res = s.insert(100);
    if (res.second) {
        cout << "successful insertion!" << endl;
    } else {
        cout << "inserted failed!" << endl;
    }
    res = s.insert(100);
    if (res.second) {
        cout << "successful insertion!" << endl;
    } else {
        cout << "inserted failed!" << endl;
    }

set 的函数返回的结果是pair<iterator, bool> 第二个参数表示是否插入成功。

pair队组

两种创建队组的方式

  • pair<string, int> p(“Amy”, 17);
  • pair<string, int> p2 = make_pair(“Jerry”, 30);

cout << p.first << ” ” << p.second << endl;

set的排序(仿函数)

class MyCompare {
    public:
        bool operator()(int a, int  b) const{
            return a > b;
        }
};

int main() {
    cout << 'a' << endl;
    set<int, MyCompare> s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(4);
    s.insert(5);
    for (set<int, MyCompare>::iterator iter = s.begin(); iter != s.end(); iter ++) {
        cout << *iter << endl;
    }

}

自定义数据类型装入set中必须在创建set的时候,指定仿函数比较器,或者在自定义类中重载比较运算符。

Map容器

#include <map> //一种关联式容器

map里面存的都是队组pair

int main() {
    map<int, int> m;
    m.insert(pair<int, int>(10,10));
    m.insert(make_pair(30,10));
    m.insert(pair<int, int>(20,10));
    for (map<int, int>::iterator iter = m.begin(); iter != m.end(); iter++) {
        cout << iter->first << " " << iter->second <<endl;
    }
}

empty size swap erase(重载多个) clear

查找元素

map<int, int>::iterator iter pos = m.find(key);

函数对象(仿函数)

特点

  • 函数对象在使用时,像普通函数一样调用
  • 函数对象超出普通函数的概念,可以有自己的状态
  • 函数对象可以作为参数传递

谓词

仿函数返回值是bool数据类型,称为谓词。(有些类似java中的函数式接口或者python中的filter)

一元谓词(有一个形式参数)–过滤

二元谓词(有两个形式参数) –排序

内建函数对象

算术仿函数

#include <functional>
negate<int>n; //一元
cout<<n(50)<<endl;
plus<int> q;  //二元
cout<<q(10,5)<<endl;

关系仿函数(greater 最常用)

#include<vector>
#include<functional>
vector<int>v;
sort(v.begin(), v.end(), greater<int>());  //关键在这里
for(vector<int>::iterator it = v.begin(); it != v.end(); it ++) {
     cout << (*it) << endl;
}

逻辑仿函数(基本用不到)

STL常用算法

  • #include<algorithm>
  • #include <numeric>
  • #include <functional>

遍历

for_each(v.begin(), v.end(), 函数或者仿函数);

搬运、转换(类似java8的stream或者python的列表表达式)

trandform(s.begin(), s.end(), d.begin(), 函数或者仿函数); //目标容器需要提前开辟空间

查找:

find (v.begin(), v.end(), int val); //自定义类型需要重写运算符==方法。

find_if(v.begin(), v.end(), 仿函数); //

adjacent_find 查找重复相邻元素的地址

binary_search(v.begin(), v.end(), int val);

count(v.begin(), v.end(), int val);

count_if(v.begin(), v.end(), 一元谓词);

排序

sort(v.begin(), v.end(), 二元谓词);

random_shuffle(v.begin(), v.end());//记得加随机数种子

merge(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()); //target需要先开辟,v1,v2需要有序

reverse(v1.begin(), v2.begin());

拷贝和替换

copy(v1.begin(), v1.end(), target.begin()); //先开辟空间

replace(v1.begin(), v2.end(), int old, int new);

replace_if(v.begin(), v.end(), 一元谓词, int new);

swap(v1,v2);//同种类型的容器才能交换

算术生成算法

#include <numeric>
int total = accumulate(v.begin(), v.end(), int start_sum);
fill(v.begin(), v.end(), 100);

“集合”算法

set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()) //target的容量需要先开辟,前提必须是两个有序的序列

set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()) //target的容量需要先开辟, 要求有序

set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()) //target的容量需要先开辟, 要求有序 ,差集有先后顺序关系

C++ 基本语法复习

参照传智播客的黑马的教程 https://www.bilibili.com/video/BV1et411b73Z/?p=2

基础内容不多赘述。

单行注释多行注释 // /**/

变量、常量(宏常量 #define k 1, const 常量)、关键字、标识符(_、字母、数字)

short int long long long float double char bool

string 需要导入头文件 #include <string>

sizeof 可以获得变量或者基本数据类型锁占的内存空间数目(以字节为单位)

+ – * / % ++ — = == > < >= <= != && || * & …..算术运算符 赋值运算符 比较运算符 逻辑运算符

流程控制 if else do while for switch case default break continue goto(不常用)

数组的定义:

  • int arr [] = {1,2,3,4,5}; //推断数组长度
  • int arr[5] ;
  • int arr[10] = {1,2,3,4};//其余的自动补充初始化默认值 0

二维数组

  • int arr [3][4];
  • int arr[3][2] = {1,2,3,4,5,6};
  • int arr[3][2] = {{1,2,3},{4,5,6}};
  • int arr[][3] = {1,2,3,4,5,6};

函数的声明,函数的定义,函数参数值传递机制

函数的分文件编写:

创建.h头文件(写函数的声明)

创建.cpp源文件(写函数的定义)(在第一行写 #include “xxx.h” 关联两个文件(函数的定义和声明))

<>系统自带 “” 用户自定义

在主程序.cpp源文件中引入头文件就可以使用函数了 (第一行引入 #include “xxx.h)

指针

int a = 5;

int * p = & a;

指针也是一种数据类型,只不过存的内容是地址值, * 号和&号的意义。

空指针(NULL) 野指针 乱给的地址值

  • const int * p,指针指向可以改,指的内容不能改
  • int * const p 指针指向不能改,指的内容可以改
  • const int * const p 都不能改

数组的名称实际上就是一个指针

结构体

  • struct Student {int age; string name;};
  • struct Student stu;
  • Student stu1 = {10, “mingming”};
  • stu.age = 10;
  • stu.name = “lili”;
  • Student *p = &stu;
  • p->age = 11;

结构体变量作为函数的形式参数的时候,利用指针作为形式参数,节省空间(不会复制一份变量),const Student * stu 还可以避免函数内部的修改操作,保护原来的变量。

C++内存模型

代码区、全局区(全局变量、静态变量和常量)、栈区(编译器自动分配和释放)、堆区(用户分配和释放)

代码区就是程序编译之后的二进制机器指令,共享且只读

全局区: (全局变量、静态变量和常量) 和普通的函数内的局部变量存放地址存的区域不同

常量 :

  • 字符串常量 &“hello world”
  • 全局常量 :在全局区中
  • 局部常量:不在全局区中

程序运行之前分为代码区和常量区

栈区的数据是由编译器管理和释放的,切记不要返回局部变量的地址

堆空间的数据都是用户new出来的,使用用delete

  • int * a = new int (10);
  • delete a;
  • int * arr = new int[10];
  • delete [] arr;

引用:就是变量的别名

int a = 10;

int & b = a;

引用必须初始化,并且初始化之后不可以修改

区别 值传递、地址传递(本质还是值传递)、引用传递

不要返回局部变量的引用,如果一个函数返回值是引用,则函数调用可以作为左值

从底层的角度来看,引用的本质就是用指针常量来实现的。

int &b = a; ==> int * const b = &a;

b = 10; ==> *b = 10;

编译器会帮你做转换,相当于一种语法糖吧

const int & b = 10;

编译器会优化为 int tmp = 10;const int & b = tmp;

但是 int & b = 10;这样的语句是非法的。

const int & b 可以用在函数的形参,只读,防止值在函数内被改变

void fun(const int & a) {}

函数支持默认参数,一个位置由默认参数,则右边的参数都应该由。函数的声明和定义只能在一处写默认值,否则存在二义性。

函数的占位参数,运算符重载的时候会用到

void func(int a, int )

函数重载:同一个作用域,函数名相同,参数类型、个数、顺序不同,返回值不作为重载的条件(会产生歧义)。const和非const参数可能会导致重载,默认参数也可能导致一些重载错误,主要从是否存在歧义性进行分析。

面向对象三大特性:封装、继承、多态

封装:就是类class(成员方法、成员函数)

权限 public、protected、private(struct 默认是public, class 默认是private)

构造函数Person(){}、析构函数~Person(){}、拷贝构造函数Person(const Person & p){…},如果定义,编译器会自动加上

创建对象的三种方式:

  • Person p1, Person p1(10);//这种空参不能带括号,否则和函数声明一样歧义。
  • Person p1 = Person(10);
  • Person p1 = 10;

拷贝构造函数调用的时机:

  • 使用一个已经创建的对象初始化另个新对象
  • 值传递的方式给函数传参数
  • 值传递的方式在函数内返回

默认的拷贝函数是浅拷贝,内部的成员变量默认都是值传递,而new出来在堆区保存的地址,只会拷贝地址,析构的时候会重复释放报错。

构造函数可以有初始化列表Person(int a):age(a){}

静态成员变量和静态成员函数是所有对象共享的,可以 类名::变量/函数名 进行访问或者调用。静态方法只能访问静态变量(因为没有this指针)

C++对象模型

  • 成员变量和成员函数是分开存储的
  • 空对象默认占一个字节(占位置),普通对象占空间就是非静态成员变量所占的总大小。

this指针 指向对象本身,可以通过返回当前对象的引用实现链式编程

Person & doSomething(){return *this;}

空指针可以访问成员函数,只要函数里面不会用到this就不会报错。

常函数: void show()const {……;}

this指针本质上就是一个指针常量, Person * const this,指向不可修改。因此常函数可以理解为const Person * const this, 不可以修改。

常对象:const Person p;

常对象只能调用常函数

mutable 修饰的属性,即使在常函数/常对象里面也可以修改。

友元( 访问类的私有成员)

  • 全局函数做友元函数
  • 类也可以做友元
  • 成员函数做友元

运算符重载

通过成员函数重载

Person operator+(Person& p) { Person tmp; tmp.val= this->val + p.val; return tmp}

通过全局函数重载

Person operator+(Person &p1, Persion & p2) {Person tmp; tmp.val = p1.val + p2.val; return tmp;}

重载<<运算符

ostream & operator<<(ostream & cout, Persion &p) { cout<<p.val; return cout;}

满足调用顺序(只能用全局函数重载),链式调用(返回引用),访问私有(加友元)

重载递增运算符

前++ Person & operator++(){this->age ++; return *this;}

返回引用是为了支持链式调用

后++ Person operator++(int){Person tmp = * this; this->age ++; return tmp;}

int 是占位参数,返回方式是值返回,防止局部变量的返回

编译器自动给写的4个函数

  • 默认构造函数
  • 默认析构函数
  • 默认拷贝构造函数
  • 重载赋值运算符

重载赋值运算符

Person & operator =(Person & p){ this->age = p.age; return *this;}

赋值运算符会涉及深拷贝和浅拷贝的问题,需要注意

重载关系运算符 bool operator==(Person & p){} bool operator!=(Person & p){}

函数调用运算符重载(仿函数) void operator()(string str){ cout<<str<<endl;}

使用方式:

Person p;
p("hello word");//调用仿函数
Person()("hello word");//匿名对象调用仿函数

继承

继承有三种主要方式public、protected、private

父类的私有的成员子类不可访问,public继承父类权限保留;protected继承,父类全变protected;private继承父类全变private。

继承中的对象模型,对象的大小(sizeof)包括所有非静态的变量所占的大小,包括父类的私有属性。

构造函数的执行顺序:先祖先(继承),再朋友(组合),最后自己,析构顺序相反。

同名的成员处理方式,加作用域。 直接访问是访问子类的,访问父类:Base::属性(适用于属性和方法,静态(可以通过类名访问)非静态都是一样的访问思路)

c++支持多继承,实际一般不推荐这么用

class son: public base1, public base2 {}

多继承会存在菱形继承的问题,用虚继承的方式来解决,这样只会有一份爷爷类的变量,节省空间(具体是再两个父亲类中设置虚继承指针,指向同一个爷爷类变量的起始位置),虚继承写在父类上。

class grandpa{} class father1: virtual public grandpa{} class father2: virtual public grandpa{} class son: public father1,public father2{}

多态

静态多态(早绑定,编译时期就确定函数地址,如函数重载、运算符重载)

动态多态(晚绑定,运行时期才能确定函数地址)

多态的本质就是父类的引用/指针 指向 子类的对象。 需要virtual关键字(虚函数)来配合。

动态多态的必要条件:

  • 存在继承关系
  • 子类需要重写父类的虚函数

原理:虚方法会在对象模型中生成一个vfptr(虚函数指针),指向虚函数表

子类首先会继承一份vfptr和虚函数表, 当子类重写父类的虚方法时, 会覆盖掉子类虚函数表中的父类虚函数。

纯虚函数 virtual 返回值类型 函数名(参数列表)= 0;

有纯虚函数的类为抽象类,抽象类无法实例化,子类必须重写,否则也成为抽象类。

虚析构和纯虚析构函数

父类的指针指向子类的对象在析构的时候不会调用子类的析构函数,如果子类有在堆中申请空间,容易造成内存泄漏。

用虚析构就可以解决上述的问题

纯虚析构也可以解决,不过会导致该类成为抽象类,不能实例化而且需要有函数定义。

文件操作

需要引入头文件 #include<fstream>

文件流对象 ofstream ifstream fstream

ofstream ofs;
ofs.open("filepath", ios::out);
ofs<<“hello world"<<endl;
ofs.close();

ifstream ifs;
ifs.open("filepath", ios::is | ios::binary);
if (ifs.is_open()){
    //读取内容,有很多中方式
}
ifs.close();

模板

建立通用的工具,提升代码复用性

template<typename T> //或者写template<class T>
void swap(T& a, T& b){
    T tmp = a;
    a = b;
    b = a;
}

调用过程由自动类型或者显示指定推到来确定

int a = 1, b = 2;
swap(a,b);
swap<int>(a,b);

普通函数和模板函数的区别

  • 普通函数可以发生隐式类型转化(e.g. char -> int)
  • 自动推导不可以隐式自动类型推到
  • 显示指定可以

普通函数和模板函数调用规则(调用存在二义性时)

  • 优先调用普通函数
  • 用空模板参数列表强制调用函数模板 //swap<>(a,b);
  • 函数模板也可以重载
  • 如果模板更好匹配,优先调用函数模板 // 完全匹配>隐式类型推导(char->int)

类模板

template <class T>
class Person{
public:
    T a;
}

类模板没有自动类型推到的方式,必须显示指定 Person<string> p(“小米”);

类模板可以由默认参数 // template<class T, class F = int>

类模板中成员函数在调用时才创建(分文件编写的时候不同版本的编译器可能会产生链接问题,.h 文件(声明) 和 .cpp文件(实现))

类模板与继承

父类时模板,子类需要执行模板具体的类型,否则子类也变成模板类

class Son:public Base<int> {}

class Son:public Base<T> {}

类模板的成员函数的外联实现需要带上模板参数

练手题:实现一个数组的模板类实现数组创建在堆区,写构造函数、拷贝构造,赋值重载、析构函数,尾插函数、删除尾部函数、获得容量、获得大小、重载下表访问