loch's blog🫶🏻

Cpp_learning_note_3

Posted on Mar 17, 2021

[toc]

reference：《黑马》C++系列教程 基础 核心 提高

本篇主要参考提高篇进行记录

模板

  • 模板就是建立通用的模具，提高复用性。模板只是一个框架，不能直接使用

  • 函数模板

    • C++另一种编程思想称为 泛型编程，主要利用的技术就是模板
    • C++提供两种模板机制：函数模板 和 类模板

函数模板语法：template<typename T>，其中typename可以用class代替

template<typename T>
void Swap(T& a,T& b){
	T temp = a;
	a = b;
	b = temp;
}
void main(){
	int a = 10,b = 20;
	Swap(a, b);//1.自动类型推导
	Swap<int>(a, b);//2.显示指定类型
	return;
}

*tips：

  1. 自动类型推导，必须推导出一致的数据类型T才可以使用

  2. 显示指定类型，必须确定出T的数据类型才可以使用

也就是说，凡是给出了模板定义，之后跟着的函数，必须给出数据类型才能调用。

template<typename T>
void function(){
	cout << "test" << endl;
}//函数中没用用到模板类型T，但是调用时必须给出才能使用
  • 普通函数与函数模板的区别
  1. 普通函数调用时可以发生自动类型转换（隐式类型转换）
  2. 函数模板调用的时候，如果利用自动类型推导，不会发生隐式类型转换
  3. 如果利用显式指定类型的方式，可以发生隐式类型转换
  • 普通函数与函数模板的调用规则
  1. 如果函数模板和普通函数都可以实现，优先调用普通函数
  2. 可以通过空模板参数列表来强制调用函数模板 funtion<>(a, b);
  3. 函数模板也可以发生重载
  4. 如果函数模板可以产生更好的匹配（例如不用进行隐式转换），优先调用函数模板
  • 模板的局限性：传入数组、类对象、自定义数据类型等数据不能处理，可以为这些特定的类型提供具体化的模板

具体化的模板以template<>开头，通过名称来指出类型，具体化优先于常规模板

template<> bool compare(Person& p1, Person& p2){ }
  • 类模板

建立一个通用类，类中的成员数据类型可以不具体指定，用一个虚拟的类型来代表

语法：

template<typename T1， typename T2, ...>
class
  • 类模板与函数模板的区别
  1. 类模板没有自动类型推导的使用方式
  2. 类模板在模板参数列表中可以有默认参数（在显示指定的时候可以更换参数类型，如int->double）
template<class nametype, class agetype = int>//2.defualt parameter
class Person{ }

void main(){
	Person <string, double>p('string',10);//1.显示指定
}
  • 类模板中的成员函数并不是一开始就创建的，在调用的时候才会创建
  • 类模板对象做函数参数
  1. 指定传入的类型 – 直接显示对象的数据类型
void printPerson1(Person<string, int> &p)
  1. 参数模板化 – 将对象中的参数变为模板进行传递
template <class T1, class T2>
void printPerson2(Person<T1, T2>&p){
	p.showPerson();
	cout << "T1的类型为： " << typeid(T1).name() << endl;
	cout << "T2的类型为： " << typeid(T2).name() << endl;
}
  1. 整个类模板化 – 将这个对象类型模板化进行传递
template<class T>
void printPerson3(T & p){
	cout << "T的类型为： " << typeid(T).name() << endl;
	p.showPerson();

}
  • 类模板与继承
  1. 当子类继承的父类是一个类模板时，子类在声明的时候要制定出父类中T的类型
  2. 如果不指定，编译器无法给子类分配内存
  3. 如果想灵活制定出父类中T的类型，子类也需要变为类模板
  • 类模板成员函数类外实现
  • 类模板份文件编写
  • 类模板与友元

STL初识

STL(Standard Template Library, 标准模板库)

STL广义上分为：容器(container)、算法(algorithm)和迭代器(iterator)。其中容器和算法之间通过迭代器进行无缝连接。STL中几乎所有的代码都采用了模板类或者模板函数。

STL六大组件

STL大体分为六大组件，分别是：容器、算法、迭代器、仿函数、适配器（配接器）、空间配置器

  1. 容器：各种数据结构，如vector、list、deque、set和map等，用来存放数据；
  2. 算法：各种常用的算法，如sort、find、copy、for_each等；
  3. 迭代器：扮演了容器与算法之间的胶合剂；
  4. 仿函数：行为类似函数，可以作为算法的某种策略；
  5. 适配器：一种用来修饰容器或者仿函数或迭代器接口的东西；
  6. 空间配置器：负责空间的配置与管理。
  • STL中容器、算法、迭代器
  1. 容器将运用最广泛的一些数据结构实现出来，分为序列式容器和关联式容器两种：

序列式容器：强调值的排序，序列式容器中的每个元素均有固定的位置。

关联式容器：二叉树结构，各元素之间没有严格的物理上的顺序关系

  1. 算法分为质变算法和非质变算法：

质变算法：是指运算过程中会更改区间内的元素内容，如拷贝、替换、删除等

非质变算法：是指运算过程中不会更改区间内的元素内容，如查找、计数、遍历、寻找极值等

  1. 迭代器：提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。每个容器都有自己专属的迭代器（类似于指针）

容器算法迭代器初识

  1. vector存放内置数据类型

容器：vector

算法：for_each

迭代器：vector<int>::iterator

#include <vector>
#include <algorithm>

void MyPrint(int val)
{
    cout << val << endl;
}

void test(){
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    
    vector<int>::iterator pBegin = v.begin();
    vector<int>::iterator pEnd = v.end();
    // 遍历方式1
    while(pBegin != pEnd) {
		cout << *pBegin << endl;
        pBegin++;
    }
    // 遍历方式2
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++){
        cout << *it << endl;
    }
    // 遍历方式3
    for_each(v.begin(), v.end(), Myprint);
}

int main(){
	test();
    system("pause");
    return 0;
}
  1. vector存放自定义数据类型
class Person {
public:
    Person(string name, int age){
    mName = name;
    mAge = age;
}
public:
    string mName;
    int mAge;
};
// 存放对象
void test01() {
    vector<Person> v;
    
    Person p1("aaa", 10);
    Person p2("bbb", 20);
    Person p3("ccc", 30);
    
    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    
    for (vector<Person>::iterator it = v.begin(); it!=v.end(); it++) {
        cout << "Name: " << (*it).mName <<", Age: " << (*it).mAge <<endl;
    }
}
// 存放对象指针
void test02() {
    vector<Person*> v;
    
    Person p1("aaa", 10);
    Person p2("bbb", 20);
    Person p3("ccc", 30);
    
    v.push_back(&p1);
    v.push_back(&p2);
    v.push_back(&p3);
    
    for (vector<Person*>::iterator it = v.begin(); it!=v.end(); it++) {
        Person* p = (*it);
        cout << "Name: " << p->mName <<", Age: " << (*it)->mAge <<endl;
    }
}
  1. vector容器嵌套容器

容器中嵌套容器，将所有数据遍历输出

void test01() {
	vector< vector<int>> v;
    
    vector<int> v1;
    vector<int> v2;
    
    for(int i=0;i<4;i++){
        v1.push_back(i+1);
        v2.push_back(i+2);
    }
    
    v.push_back(v1);
    v.push_back(v2);
    
    vector< vector<int>>::iterator pBegin = v.begin();
    vector< vector<int>>::iterator pEnd = v.end();

    while(pBegin != pEnd) {
		for (vector<int>::iterator vit = pBegin->begin(); vit != pBegin->end(); vit++) {
			cout << *vit << " ";
		}
		cout << endl;
        pBegin++;
    }
}

STL - 常用容器

string容器

  • string是c++风格的字符串，本质上是一个类

string与char *的区别：char*是一个指针，string是一个类，类内部封装了char*，管理这个字符串，是一个char*型的容器。

  • string构造函数

string()// 创建一个空的字符串

string(const char* s)// 使用字符串s初始化

string(const string& str)// 使用一个string对象初始化另一个string对象

string(int n, char c)// 使用n个字符c初始化

  • string赋值操作

string& operator=(const char* s); //char*类型字符串赋值给当前的字符串

string& operator=(const string &s); //把字符串s赋给当前的字符串

string& operator=(char c); //字符赋值给当前的字符串

string& assign(const char *s); //把字符串s赋给当前的字符串

string& assign(const char *s, int n); //把字符串s的前n个字符赋给当前的字符串

string& assign(const string &s); //把字符串s赋给当前字符串

string& assign(int n, char c); //用n个字符c赋给当前字符串

  • string字符串拼接

实现在字符串末尾拼接字符串

string& operator+=(const char* str); //重载+=操作符

string& operator+=(const char c); //重载+=操作符

string& operator+=(const string& str); //重载+=操作符

string& append(const char *s); //把字符串s连接到当前字符串结尾

string& append(const char *s, int n); //把字符串s的前n个字符连接到当前字符串结尾

string& append(const string &s); //同operator+=(const string& str)

string& append(const string &s, int pos, int n);//字符串s中从pos开始的n个字符连接到字符串结尾

  • string查找和替换

查找：查找指定字符串是否存在

替换：在指定的位置替换字符

int find(const string& str, int pos = 0) const; //查找str第一次出现位置,从pos开始查找

int find(const char* s, int pos = 0) const; //查找s第一次出现位置,从pos开始查找

int find(const char* s, int pos, int n) const; //从pos位置查找s的前n个字符第一次位置

int find(const char c, int pos = 0) const; //查找字符c第一次出现位置

int rfind(const string& str, int pos = npos) const; //查找str最后一次位置,从pos开始查找

int rfind(const char* s, int pos = npos) const; //查找s最后一次出现位置,从pos开始查找

int rfind(const char* s, int pos, int n) const; //从pos查找s的前n个字符最后一次位置

int rfind(const char c, int pos = 0) const; //查找字符c最后一次出现位置

string& replace(int pos, int n, const string& str); //替换从pos开始n个字符为字符串str

string& replace(int pos, int n,const char* s); //替换从pos开始的n个字符为字符串s

conclusion：find查找是从左向右，rfind自右向左；find找不到时返回-1；replace要指定从哪个位置起，多少个字符，替换的字符串。

  • string字符串比较

字符串按字符的ASCII码进行对比，=返回0、>返回1、<返回-1

int compare(const string &s) const; //与字符串s比较

int compare(const char *s) const; //与字符串s比较

  • string字符串存取

string中单个字符存取方式有两种

char& operator[](int n); //通过[]方式取字符

char& at(int n); //通过at方法获取字符

  • string插入和删除

string& insert(int pos, const char* s); //插入字符串

string& insert(int pos, const string& str); //插入字符串

string& insert(int pos, int n, char c); //在指定位置插入n个字符c

string& erase(int pos, int n = npos); //删除从Pos开始的n个字符

  • string子串

从字符串中获取想要的子串

string substr(int pos = 0, int n = npos) const; //返回由pos开始的n个字符组成的字符串

vector容器

vector数据结构和数组非常相似，也称为单端数组；不同之处在于数组是静态空间，而vector可以动态扩展。这里的动态扩展并不是在原空间之后续接新空间，而是找更大的内存空间，将原数据copy新空间，释放原空间。

  • vector构造函数

vector<T> v; //采用模板实现类实现，默认构造函数

vector(v.begin(), v.end()); //将v[begin(), end())区间中的元素拷贝给本身。

vector(n, elem); //构造函数将n个elem拷贝给本身。

vector(const vector &vec); //拷贝构造函数。

  • vector赋值操作

vector& operator=(const vector &vec);//重载等号操作符

assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。

assign(n, elem); //将n个elem拷贝赋值给本身。

  • vector容量和大小

empty(); //判断容器是否为空

capacity(); //容器的容量

size(); //返回容器中元素的个数

resize(int num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

resize(int num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除

  • vector插入和删除

push_back(ele); //尾部插入元素ele

pop_back(); //删除最后一个元素

insert(const_iterator pos, ele); //迭代器指向位置pos插入元素ele

insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele

erase(const_iterator pos); //删除迭代器指向的元素

erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素

clear(); //删除容器中所有元素

  • vector数据存取（除了用迭代去获取vector容器中元素，[]和at也可以）

at(int idx); //返回索引idx所指的数据

operator[]; //返回索引idx所指的数据

front(); //返回容器中第一个数据元素

back(); //返回容器中最后一个数据元素

  • vector互换容器

swap(vec); // 将vec与本身的元素互换

  • vector预留空间

减少vector在动态扩展容量时的扩展次数

reserve(int len); // 容器预留len个元素长度，预留位置不初始化，元素不可访问

deque容器

双端数组，可以对头端进行插入和删除操作。

deque与vector区别：

  • vector对于头部的插入删除效率低，数据量越大，效率越低
  • deque相对而言，对头部的插入删除速度比vector块
  • vector访问元素时的速度比deque快

deque内部工作原理：

​ deque内部有一个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据。中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间。deque容器的迭代器也是支持随机访问的。

stack容器

stack是一种先进后出（FILO）的数据结构，它只有一个出口。

栈中只有顶端的元素才可以被外界使用，不允许有遍历行为。有push和pop操作。

  • stack常用接口

入栈 — push

出栈 — pop

返回栈顶 — top

判断栈是否为空 — empty

返回栈大小 — size

queue容器

queue是一种FIFO的数据结构，有两个出口。

队列容器允许从一端新增元素，从另一端移除元素，只有队头和队尾才可以被使用，不允许有遍历行为。

  • queue常用接口

入队 — push

出队 — pop

返回队头元素 — front

返回队尾元素 — back

判断队是否为空 — empty

返回队列大小 — size

list容器

list（链表）是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的，list将数据进行链式储存。

STL中的链表是一个双向循环链表，list的迭代器只支持前移和后移，属于双向迭代器。

list有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。

tips: const_iterator和iterator都可以遍历容器的元素，并访问这些元素的值。iterator可以改变元素值，但是const_iterator不可改。

  • list 插入与删除

尾插 — push_back

尾删 — pop_back

头插 — push_front

头删 — pop_front

插入 — insert

删除 — erase

移除 — remove

清空 — clear

  • list反转和排序

反转 — reverse

排序 — sort （成员函数）

set/multiset容器

所有元素都会在插入时自动被排序

本质：set/multiset属于关联式容器。底层结构是用二叉树实现的。

  • set与multiset区别：set不允许容器中有重复元素，multiset允许容器中有重复元素。

set不可以插入重复数据，而multiset可以

set插入数据的同时会返回插入结果，表示插入是否成功

multiset不会检测数据，因此可以插入重复数据

  • set构造与赋值

set容器插入数据时用insert

set容器插入数据的数据会自动排序

  • set大小和交换

统计大小 — size

判断是否为空 — empty

交换容器 — swap

  • set查找和统计

查找 — find （返回的是迭代器）

统计 — count （对于set，结果为0或者1）

  • pair对组创建

成对出现的数据，利用对组可以返回两个数据

pair<type, type> p ( value1, value2 );

pair<type, type> p = make_pair( value1, value2 );

pair<set<int>::iterator, bool> ret = s.insert(10);# 注意insert()的返回是一个pair对组，此外对pair对组的访问通过pair.first or pair.second进行。

  • set容器排序

set容器默认排序规则为从小到大，利用仿函数，可以改变排序规则。

仿函数 (functor)，就是使一个类的使用看上去像一个函数。 其实现就是类中实现一个 operator ()，这个类就有了类似函数的行为，就是一个仿函数类了。

通过定义结构体(或类)，并在其中重载()运算符，来自定义排序函数。然后，在定义set的时候，将结构体加入其中例如如下代码中的set<int, intComp>和set<string, strComp >。

map/multimap容器

map中所有元素都是pair，pair中第一个元素为key（键值），起到索引作用，第二个元素为value（实值），所有元素都会根据元素的key自动排序。

本质：map/multimap属于关联式容器，底层结构用二叉树实现。

  • map和multimap的区别：map不允许容器中有重复的key，而multimap可以