15.计算机图形学OpenGL与C++

理解GLFW和GLAD

GLFW（）

GLFW是一个开源的、跨平台的库，用于创建窗口、处理输入和渲染图形。它提供了一种简单的方式来与OpenGL进行交互，使得开发图形应用程序变得更加容易。

GLFW的主要功能包括：

• 创建窗口
• 定义上下文
• 处理用户输入

GLAD（）

GLAD是一个开源的、跨平台的库，用于管理OpenGL的函数指针。它提供了一种简单的方式来获取OpenGL的函数指针，使得开发OpenGL应用程序变得更加容易。

相关说明：

• OpenGL本身知识规范/标准
• 各个厂家具体实现方式可以不同
• 不同操作系统处理方式也可以不同

主要功能：

• 获取OpenGL函数指针
• 处理OpenGL版本兼容性问题
• 处理OpenGL扩展函数 ……

如果没有GLAD库，在Windows下：

typedef void (*GL_GENBUFFER) (GLsizei,GLuint*);//声明函数指针
GL_GENBUUFFER glGenBuffer = (GL_GENBUFFER)wglGetProcAddress('glGenBuffer');//获取函数指针
unsigned int buffer;//声明缓冲区对象
glGenBuffer(1,&buffer);//调用函数

有了GLAD库，只需要：

unsigned int buffer;
glGenBuffer(1,&buffer);

14.新标准C加加程序设计

内存分区模型

内存代码区的意义：程序代码放在不同的区域，有程序自动管理的代码，也有程序员管理的代码，灵活管理；

一、程序执行前

1.代码区 存放二进制指令，就是代码，特点：

• 共享：多个进程的代码区是共享的，因为代码是相同的，所以只需要加载一份到内存中即可，节省内存空间。
• 只读：代码是只读的，防止程序意外地修改了代码。

2.全局区 全局变量和静态变量存储在全局区，还包括常量区、字符串常量和其他常量（如：const）,特点：

• 全局区是程序结束后由系统释放。
• 全局变量和静态变量在程序结束后系统会自动释放，而局部变量在函数结束后由系统自动释放。

例子：

#include <iostream>
using namespace std;

//全局变量 
int g_a = 10;
int g_b;

//const 修饰的全局变量
const int c_g_a = 10;

int main(int argc,char *argv[]){
    //局部变量
    int a = 10;
    int b = 20;

    //静态变量
    static int s_a = 10;
    static int s_b;

    //字符串常量
    char *P = "hello world";

    //const修饰的局部变量
    const int c_l_a = 10;

    cout<<"局部变量a的地址："<<&a<<endl;
    cout<<"局部变量b的地址："<<&b<<endl;
    cout<<"全局变量a的地址："<<&g_a<<endl;
    cout<<"全局变量b的地址："<<&g_b<<endl;
    cout<<"静态变量a的地址："<<&s_a<<endl;
    cout<<"静态变量b的地址："<<&s_b<<endl;

    cout<<"字符串常量P的地址："<<P<<endl;
    cout<<"const修饰的局部变量c_l_a的地址："<<&c_l_a<<endl;
    cout<<"const修饰的全局变量c_g_a的地址："<<&c_g_a<<endl;

    return 0;
}

3.总结

• 代码区：存放二进制指令，共享，只读。
• 全局区：存放全局变量和静态变量，程序结束后由系统释放。

二、程序运行后

1.栈区

由编译器自动分配释放，存放函数的参数值，局部变量等。

注意： 不要返回局部变量的地址，因为局部变量在函数结束后会被系统释放，再次访问会导致程序崩溃。

例子：

#include <iostream>
using namespace std;

int *GetAddr(int b){//形参数据也放在栈区
    b = 10;
    int a = 10;
    return &a;//返回局部变量的地址
}

int main(){
    int *p = GetAddr();
    cout<<*p<<endl;//第一次可以打印正确的数据，是因为编译器做了保留，
    cout<<*p<<endl;// 但是第二次访问将不再保留
    return 0;
}

2.堆区

由程序员分配释放，如果程序员不释放，程序结束时由系统回收。

在C++中主要利用new和delete操作符进行动态内存管理。

例子1-在堆上开辟空间：

#include <iostream>
using namespace std;
int* getAddr(){

    //在堆上开辟空间，并初始化为10
    int *p = new int(10);//new出来的数据返回的是一个指针
    //使用存在栈区的局部指针指向堆区的数据，栈区的内容会被程序自动释放，但是指向堆区的数据不会被释放
    return p;
}
int main(){

    int *p = getAddr();

    cout<<*p<<endl;//输出10
    delete p;//释放空间
    return 0;
}

图解：

例子2-堆区上的数据开辟与释放

#include <iostream>
using namespace std;
void test(){
    int *P = new int(10);
    cout<<*P<<endl;
    
    delete P;
}
void test2(){
    int *arr = new int[10];
    for(int i = 0;i<10;i++){
        arr[i] = i+10;
    }
    for(int i = 0;i<10;i++){
        cout<<arr[i]<<" ";
    }
    delete[] arr;
}
int main(){
    test();
}

引用

给变量取别名。

一、变量引用

引用注意事项：

• 引用必须初始化，int &b;//这样是不正确的
• 引用初始化后不能改变
• 通过引用参数产生的效果与指针地址传递效果一样，引用语法更清楚；

测试代码：

//值传递
void test1(int a,int b) {

}
//地址传递
void test2(int *a,int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
//引用传递
void test3(int &a,int &b) {
	int temp = a;
	a = b;
	b = temp;
}

二、应用做函数的返回值

• 不要返回局部变量的引用
• 函数返回值是引用，那么这个函数调用可以作为左值

测试代码：

// 二、引用做函数返回值
	//1.不能返回应用返回值
int& test04()//以引用的方式返回b,相当于给这个b起了一个别名
{
	int b = 10;//局部变量存放在栈区，函数结束后会被释放
	return b;
}
	//2. 函数的调用可以作为左值
int& test05()
{
	static int b = 10;//静态变量存放在全局区，程序结束后由系统自动释放
	return b;
}

int main() 
{
	int& ret04 = test04();
	int& ret05 = test05();
	std::cout << "ret04= "<<ret04 << std::endl;
	std::cout << "ret04= " << ret04 << std::endl;//第二次访问返回的是乱码
	std::cout << "ret05= " << ret05 << std::endl;
	test05() = 130;//函数的返回是引用，函数的调用可以作为左值
	std::cout << "ret05= " << ret05 << std::endl;

	system("pause");
	return 0;
}

测试代码结果

三、引用的本质

引用的本质在C++内部实现是一个指针常量，引用类型必须和引用实体是同类型。

四、常量引用

作用：用来修饰形参，防止误操作。

代码说明：

//四、常量引用
	//int &ref = 10; 这样的操作是不被允许的，因为赋值给引用的是一个字面量,引用需要一个合法的空间，
	// 程序运行时没有专门为其分配可修改的内存空间
	// 但是如果在前面在上const，这条代码就通过
	// const int &ref = 10;
	//用来修饰形参，防止误操作
void test06(const int &val)
{
	//val = 100;不被允许修改
	std::cout << "val = " << val << std::endl;
}

函数进阶

一、函数默认参数

返回值 函数名(参数 = 默认值){}

注意事项：

1.如果某个位置已经有了默认参数，那么该位置往后都必须有默认参数

//函数默认参数
void test(int a ,int b = 20,int c = 30)
{
	std::cout << "a = " << a << std::endl;
	std::cout << "b = " << b << std::endl;
	std::cout << "c = " << c << std::endl;
}

2.函数的声明有默认参数，函数实现不能有默认参数,声明和实现只能有一个有默认值

#include <iostream>
//函数声明
void test(int a=10,int b = 20);//
//函数实现
void test(int a ,int b)
{
	std::cout << "a = " << a << std::endl;
	std::cout << "b = " << b << std::endl;
}

二、函数占位参数

作用：为了函数声明和定义的统一 语法：返回类型 函数名(数据类型){}

//函数占位参数
void test(int a,int)//第二个参数为占位参数
{
    std::cout << "a = " << a << std::endl;
}

int main() {
    test(10,10);//占位参数必须填补,否则无法运行
}

注意：占位参数可以有默认参数，此时调用时就不用在传值

//函数占位参数
void test(int a,int = 10)//第二个参数为占位参数，含默认值
{
    std::cout << "a = " << a << std::endl;
}

int main() {
    test(10);//不需要传站位参数
}

三、函数重载

满足条件：

• 在同一个作用域下。
• 函数名相同，
• 参数类型不同，
• 参数个数不同，
• 参数顺序不同。

作用： 提高复用性

注意：

1.返回值不能作为重载的条件

2.引用作为重载的条件

加const和不加是可以重载的

void fun(int &a){
    std::cout<<"fun(int &a)"<<std::endl;
}
void fun(const int &a){
    std::cout<<"fun(const int &a)"<<std::endl;
}
int main(){
    int a = 10;
    const int &b = 20;
    fun(a);//调用fun(int &a)
    fun(b);//调用fun(const int &a)
    fun(10);//调用fun(const int &a)
    return 0;
}

3.函数重载遇到默认参数

void fun2(int a,int b = 10){
    std::cout<<"fun(int &a)"<<std::endl;
}
void fun2(int a){
    std::cout<<"fun(const int &a)"<<std::endl;
}
int main(){

    fun2(10);//此时程序出现二义性，无法确定调用哪个函数
    return 0;
}

类和对象的基本概念

C++的特性：封装、多态、继承

一、基本概念

• 抽象：将事物所能进行的的行为归纳出来，形成函数，这些函数可以操作事物归纳后的数据结构。
• 类： 、

封装

将事物归纳的数据结构和操作该数据结构的算法呈现显而易见的紧密关系，叫封装。

一、 封装的意义

1.将属性和行为作为一个整体，表现生活中的事物。

namespace test_class
{
	//设计一个圆的类
#define PI 3.14
	class Circle
	{
		//访问权限
	public:
		//属性
		int m_r;
		//行为
		double calculateZC()
		{
			return 2 * PI * m_r;
		}
	};
	void test() {
		Circle c1;
		c1.m_r = 10;
		cout << "圆的周长 = " << c1.calculateZC() << endl;
	}
}

2.访问权限

• public 公共权限
• protected 保护权限
• private 私有权限

二、访问权限说明

• public修饰的成员，可以在类内或者类外直接访问
• protected修饰的成员，只能在类内和子类中访问
• private修饰的成员，只能在类内访问

三、struct 与 Class 的区别

• 默认访问权限不同
• struct 默认权限为 public
• class 默认权限为 private

四、设置访问权限

一般对于变量设置为private，当要访问private的变量时，通过public的函数来访问。

namespace test_class
{
	class Person
	{
	private:
		//姓名
		string m_Name;
		//年龄
		int m_Age;
    public:
		void setAge(int age)
		{
			m_Age = age;
        }
    };
    int main(){
        Person p;
        p.setAge(18);
        return 0;
    }
}

对象特性

一、初始化和清零 如果我们不提供构造函数，编译器会自动提供默认构造函数，但两个函数是空实现。

1.作用

• 构造函数：主要作用在于粗昂见对象那个时为对象成员属性赋值，
• 析构函数：主要作用在于对象销毁前系统自动调用析构函数，执行一些清理工作。

2.语法

二、构造函数的分类及调用

1. 按参数分类：有参构造和无参构造(默认构造函数)
2. 按类型分类：普通构造和拷贝构造

3.调用规则

• 如果定义了有参构造，最好显示定义无参构造
• 如果定义了拷贝构造，最好显示定义赋值构造

namespace test
{
	//构造函数的分类及调用

	//分类 按照参数分：有参构造函数和无参构造函数（默认构造函数）
	//		按照类型分：普通构造和拷贝构造
	class Person
	{
		public:
			Person() {
				cout << "调用无参构造函数" << endl;
			}
			Person(int Age)
			{
				age = Age;
				cout << "调用有参构造函数" << endl;
			}
			Person(const Person &p)
			{
				age = p.age;
				cout << "调用拷贝构造函数" << endl;
			}
			~Person() {
				cout << "调用析构函数" << endl;
			}

		private:
			int age;
	};
	//调用
	void test() {
		//1.括号法
		Person p1;
		Person p2(18);
		Person p3(p2);
		//注意事项
		// 如果写的是 Person p1();那么编译器会认为是函数声明，而不会调用默认构造函数

		//2.显示法
		Person p1;
		Person p2 = Person(10);
		Person p3 = Person(p2);

		//匿名对象：只写Person (10)的形式，特点是当前行执行结束后，系统会立即回收
		// 注意2：
		// 不要使用拷贝构造函数初始化匿名对象、编译器会认为Person (p3) === Person p3;即对象声明
		//3.隐式调用
		Person p4 = 10;//隐式转换为Person p4 = Person(10);
	}
}

三、拷贝构造函数调用时机

1.使用一个已经创建完毕的对象来初始化一个新对象 2.值传递的方式给函数参数传值 3.值方式返回局部对象

namespace test_copy
{
	//拷贝构造函数调用时机
	class Person
	{
	public:
		Person() {
			cout << "调用无参构造函数" << endl;
		}
		Person(int Age)
		{
			age = Age;
			cout << "调用有参构造函数" << endl;
		}
		Person(const Person& p)
		{
			age = p.age;
			cout << "调用拷贝构造函数" << endl;
		}
		int getAge() {
			return age;
		}
		~Person() {
			cout << "调用析构函数" << endl;
		}

	private:
		int age;
	};
	//1.使用一个创建好的对象初始化一个新的对象
	void test01() {
		Person p(19);
		Person p2(p);
	}
	//2.值传递方式传给函数参数传值
	void doWork01(Person p){
		cout << "值传递方式调用拷贝构造函数" << endl;
	}
	//3.以返回值的方式返回
	Person doWork02() {
		Person p1;
		cout << (int*)&p1 << endl;
		return p1;//返回时不直接返回p而是通过拷贝构造函数，拷贝一份返回给外面。当然，也有存在被编译器优化的情况
					//这个时候就不会调用拷贝构造函数
	}
	void test02() {
		Person p = doWork02();
		cout << (int*)&p << endl;
		//cout << p.getAge() << endl;
	}
}

四、构造函数调用规则

1.默认情况下，c++编译器至少给一个类添加3个函数

• 默认构造函数(无参，函数体为空)
• 默认析构函数(无参，函数体为空)
• 默认拷贝构造函数，对属性值进行拷贝

2.如果我们提供了有参构造函数，编译器就不会提供默认构造函数，但会提供默认拷贝构造函数

3.如果我们提供了拷贝构造函数，编译器就不会提供其他构造函数

五、深拷贝与浅拷贝

1.浅拷贝：简单的赋值拷贝操作 2.深拷贝：在堆区重新申请空间，进行拷贝操作

namespace test_deepcopy
{
	class Person
	{
	public:
		Person(int age,int height);
		Person(const Person& p);
		~Person();

		int m_Age;
		int* m_Height;
	};

	Person::Person(int age,int height)
	{
		m_Age = age;
		m_Height = new int(height);//在堆区申请一块内存空间用于存储身高
		cout << "调用构有参造函数" << endl;
	}
	Person::Person(const Person& p)
	{
		m_Age = p.m_Age;
		//m_Height = p.m_Height;//这段代码就是浅拷贝操作
		m_Height = new int(*p.m_Height);//这段代码就是在堆区另申请内存空间，存储赋值过来的身高值
	}
	Person::~Person()
	{
		if (m_Height != NULL)
		{
			delete m_Height;
			m_Height = NULL;//避免野指针出现置空
		}
		cout << "调用析构函数" << endl;
	}
	void test()
	{
		Person p(18, 180);
		cout << "person年龄：" << p.m_Age << "身高：" << *p.m_Height << endl;

		// 为测试浅拷贝与深拷贝写如下代码
		Person p1(p);//在没有写拷贝构造函数中的申请内存空间情况下，程序会报错，原因是程序是浅拷贝，导致第二次调用析构函数的时候报错
		cout << "person年龄：" << p1.m_Age << "身高：" << *p1.m_Height << endl;
	}
}

结果如下：

六、初始化列表

1.作用

用于初始化属性

2.语法

namespace test_init
{
	class Person
	{
	public:
		//初始化列表
		//Person() :m_A(10), m_B(20), m_C(30) { }
		Person(int a,int b,int c) :m_A(a), m_B(b), m_C(c) { }

		~Person() {}

		int m_A;
		int m_B;
		int m_C;
		
	};
	void test() {
		Person p(10, 20, 30);
		cout << "m_A:" << p.m_A << endl;
		cout << "m_B:" << p.m_B << endl;
		cout << "m_C:" << p.m_C << endl;
	}
}

七、类对象作为类成员

1.类中的成员可以是另一个类的对象，我们称该成员为对象成员

2.类对象作为类成员时，其构造顺序和声明顺序一致，析构顺序和构造相反

八、静态成员

1.静态成员变量

• 所有对象共享同一份数据
• 在编译阶段分配内存
• 类内声明，类外初始化

2.静态成员函数

• 所有对象共享同一个函数
• 静态成员函数只能访问静态成员变量

namespace test_static
{
	class Person
	{
	public:
### 继承

### 多态

### 类

将数据结构和操作该数据结构的函数捆绑在一起形成一个类。

### 在类中使用缺省函数

需要注意避免二义性：
![alt text](image-5.png)

## 构造函数

### 类中为什么需要构造函数

![alt text](image-6.png)

### 构造函数在数组中的使用

```cpp
class A{
    int a;
    public:
        A(){std::cout<<"hello\n";}//1
        A(int b){std::cout<<"value: "<<b<<std::endl;}//2
}
int main(){
    A arr[2] = {1};
}

上面的语句就调用了第1，2个构造函数，首先数据里的1会调用2，而数组的第二个是空值那么就会调用第1个。

复制构造函数-copy constructor

函数名与类名相同，参数为A(A& a)或A(const A& a)（二选一）。

三种情况下复制构造函数起作用

• 同类对象a,b，将a的值初始化b；
  • A a; A b(a);
• 将类当作参数传入函数；
• 将类作为返回值；

注意：对象之间的复制是不会导致复制构造函数的

转换构造函数

什么是转换构造函数

示例代码： 在上面的例子当中，c1 = 9;会被自动转换为调用转换构造函数，如果不想让这样的事情发生，可以在转换构造函数前面加上修饰字段 explicit，这样再次使用c1 = 9;时程序会报错。

析构函数-destructors

这里补充几点，一个类只能有一个析构函数；

析构函数与数组：

数组成员的每一次结束时都会调用析构函数，假设类A数组array[2]，则生命周期结束时会调用两次析构函数。

析构函数什么时候被调用呢？

    class CMyclass {
    public:
    ~CMyclass() { cout << "destructor" << endl; }
    };
    CMyclass obj;
    CMyclass fun(CMyclass sobj ) { //参数对象消亡也会导致析
    //构函数被调用
    return sobj; //函数调用返回时生成临时对象返回
    }
    int main(){
    obj = fun(obj); //函数调用的返回值（临时对象）被
    return 0; //用过后，该临时对象析构函数被调用
    }

上面结果输出三个destructor，在fun(CMyclass sobj)参数对象消亡调用析构函数（具体可以联想复制构造函数），会调用一次析构函数；当函数返回赋值给obj后，再次调用析构函数；整个程序结束再次调用析构函数。

this指针

静态成员函数中可以直接使用this指针来代表指向该函数作用的对象的指针

示例1：

class Complex {
public:
double real, imag;
void Print() { cout << real << "," << imag ; }
Complex(double r,double i):real(r),imag(i)
{ }
Complex AddOne() {
this->real ++; //等价于 real ++;
this->Print(); //等价于 Print
return * this;
}
}; 

int main() {
Complex c1(1,1),c2(0,0);
c2 = c1.AddOne();//调用AddOne函数后内部this指针变为c1，所以是c1中的read++
return 0;
} //输出 2,1

示例2：

    class A
{
int i;
public:
void Hello() { cout << i << "hello" << endl; }
}; // 翻译为void Hello(A * this ) { cout << this->i << "hello"<< endl; }
int main()
{
A * p = NULL;
p->Hello(); //翻译为Hello(p);
} //编译报错

报错的原因是p指针式一个空指针，它并不指向任何A的对象，所以编译到 this->i 会报错。

静态成员变量和函数

基本特点：

• 普通成员变量每个对象有各自的一份，而静态成员变量一共就一份，为所有对象共享。
• 普通成员函数必须具体作用于某个对象，而静态成员函数并不具体作用于某个对象。因此静态成员不需要通过对象就能访问。

对第二句话的理解，如下代码示例：

class Dog {
public:
    // 普通成员函数
    void bark() {
        std::cout << "Woof!" << std::endl;
    }

    // 静态成员函数
    static std::string getSpecies() {
        return "Canine";
    }
};

要调用bark我们需要先创建一个Dog的类对象，然后通过 . 调用，也就是非静态成员作用于对象的意思，但是对于 getSpecies 就不需要，可以直接 Dog::getSpecies调用。

如何访问静态成员？

1. 类名::成员名 CRectangle::PrintTotal();

2. 对象名.成员名 CRectangle r; r.PrintTotal();

3. 指针->成员名 CRectangle * p = &r; p->PrintTotal();

4. 引用.成员名 CRectangle & ref = r; int n = ref.nTotalNumber;

设置静态成员变量的目的是什么？

设置静态成员这种机制的目的是将和某些类紧密相关的全局变量和函数写到类里面，看上去像一个整体，易于维护和理解。比如，考虑一个需要随时知道矩形总数和总面积的图形处理程序，可以用全局变量来记录总数和总面积，用静态成员将这两个变量封装进类中，就更容易理解和维护。

注意事项：

• 必须在定义类的文件中对静态成员变量进行一次说明或初始化。否则编译能通过，链接不能通过。
• 在静态成员函数中，不能访问非静态成员变量，也不能调用非静态成员函数。

成员对象和封闭类

• 有成员对象的类叫 封闭(enclosing)类。
• 任何生成封闭类对象的语句，都要让编译器明白，对象中的成员对象，是如何初始化的。具体的做法就是：通过封闭类的构造函数的初始化列表。

封闭类的复制构造函数:

    class A
    {
    public:
    A() { cout << "default" << endl; }
    A(A & a) { cout << "copy" << endl;}
    };

    class B { A a; };

    int main()
    {
    B b1,b2(b1);//b2调用自生默认复制构造函数，而内部的A a也会调用默认的复制构造函数
    return 0;
    }

友元

1. 友元函数: 一个类的友元函数可以访问该类的私有成员。
2. 可以将一个类的成员函数(包括构造、析构函数)说明为另一个类的友元。
3. 友元类: 如果A是B的友元类，那么A的成员函数可以访问B的私有成员。
4. 友元类之间的关系不能传递，不能继承。

常量成员

常量成员函数：内部不能改变属性的值，也不能调用非常量成员函数。

**注意：**如果一个成员函数中没有调用非常量成员函数，也没有修改成员变量的值，那么，最好将其写成常量成员函数。 mutable成员变量 可以在const成员函数中修改的成员变量

    class CTest
    {
    public:
    bool GetData() const
    {
    m_n1++;//这个值更可以更改
    return m_b2;
    }
    private:
    mutable int m_n1;
    bool m_b2;
    };

运算符重载函数

浅拷贝与深拷贝：

为解决这个问题，我们需要修改赋值运算符重载：

    String & operator = (const String & s){
        if( this == & s)
            return * this;
        delete [] str;
        str = new char[strlen(s.str)+1];
        strcpy( str,s.str);
        return * this;
    }

自增自减运算法重载

class CDemo {
private :
int n;
public:
CDemo(int i=0):n(i) { }
CDemo & operator++(); //用于前置形式
CDemo operator++( int ); //用于后置形式
operator int ( ) { return n; }
friend CDemo & operator--(CDemo & );
friend CDemo operator--(CDemo & ,int);
}

operator int ( ) {return n;}

这里，int 作为一个类型强制转换运算符被重载, 此后

Demo s;
(int) s ; //等效于 s.int();

类型强制转换运算符被重载时不能写返回值类型，实际上其返回值类型就是该类型强制转换运算符代表的类型。

继承和派生

**注意：**在派生类的各个成员函数中，不能访问基类中的private成员。

派生类的内存空间

类之间的关系

继承：“是”关系。

• 基类 A，B是基类A的派生类。
• 逻辑上要求：“一个B对象也是一个A对象”。

复合：“有”关系。

• 类C中“有”成员变量k，k是类D的对象，则C和D是复合 关系
• 一般逻辑上要求：“D对象是C对象的固有属性或组成部 分”

复合关系的示例：

基类与派生类名字重名的情况

一般来说，基类和派生类不定义同名成员变量。但如果要方位可以使用基类::基类成员来访问。

访问权限

• 基类的private成员：可以被下列函数访问

• 基类的成员函数
• 基类的友元函数

• 基类的public成员：可以被下列函数访问

• 基类的成员函数
• 基类的友元函数
• 派生类的成员函数
• 派生类的友元函数
• 其他的函数

• 基类的protected成员：可以被下列函数访问

• 基类的成员函数
• 基类的友元函数
• 派生类的成员函数可以访问当前对象和其它对象的基类的保护成

举一个例子：

class Father {
private: int nPrivate; //私有成员
public: int nPublic; //公有成员
protected: int nProtected; // 保护成员
};
class Son :public Father{
void AccessFather () {
nPublic = 1; // ok;
nPrivate = 1; // wrong
nProtected = 1; // OK，访问从基类继承的protected成员
Son f;
f.nProtected = 1; //ok，派生类的成员函数可以访问当前对象和其它对象的基类的保护成
}
};

int main(){
    Father f;
    Son s;
    f.nPublic = 1; // Ok
    s.nPublic = 1; // Ok
    f.nProtected = 1; // error，因为只能在派生类（或友元类）中访问
    f.nPrivate = 1; // error
    s.nProtected = 1; //error
    s.nPrivate = 1; // error
    return 0;
}

派生类构造函数中包含成员变量时该如何写？

    class Bug {
    private :
    int nLegs; int nColor;
    public:
    int nType;
    Bug ( int legs, int color);
    void PrintBug (){ };
    };

    class Skill {
    public:
    Skill(int n) { }
    };

    class FlyBug: public Bug {
    int nWings;
    Skill sk1, sk2;
    public:
    FlyBug( int legs, int color, int wings);
    };

    FlyBug::FlyBug( int legs, int color, int wings):
    Bug(legs,color),sk1(5),sk2(color) ,nWings(wings) { }//注意这种写法。

private 和 protected的继承

• protected继承时，基类的public成员和protected成员成为派生类的protected成员。 • private继承时，基类的public成员成为派生类的private成员，基类的protected成员成 为派生类的不可访问成员。 • protected和private继承不是“是”的关系。

问题：

即便基类指针指向的是一个派生类的对象，也不能通过基类指针访问基类没有，而派生类中有的成员。

解决办法：

通过强制指针类型转换，可以把ptrBase转换成Derived类的指针

    Base * ptrBase = &objDerived;
    Derived *ptrDerived = (Derived * ) ptrBase;

程序员要保证ptrBase指向的是一个Derived类的对象，否则很容易会出错。

虚函数和多态

多态的表现形式

• 派生类的指针（或引用）可以给基类赋值。
• 当指针指向基类时调用，基类的函数，当指针指向派生类时，调用调用派生类的函数，这叫做多态。
• 另外，在非虚函数和非构造、析构函数中调用虚函数，也叫做多态。 例子：

如果在构造、析构函数中调用虚函数，那么会怎么样呢？

如果这么做，那么编译器只会调用当前的虚函数，如果当前没有重写虚函数，则会从基类中找进行调用，为什么要这么做呢？其实这是为了防止未初始化就调用派生类的虚函数的情况。

你想想啊，一类的初始化先从基类的构造函数开始，如果这个时候构造函数具有多态性，那么此时将调用派生类的对应虚函数，但是派生类这个时候都还没有初始化。

例子： `

• 补充：在上面的图例子中，派生类写了与基类虚函数相同的名字，但是没有在前面加修饰符virtual，这种情况编译器认为是虚函数。

多态的作用

在面向对象的程序设计中使用多态，能够增强程序的可扩充性，即程序需要修改或增加功能的时候，需要改动和增加的代码较少。

虚函数的访问权限

动态联编的实现机制

“多态”的关键在于通过基类指针或引用调用一个虚函数时，编译时不确定到底调用的是基类还是派生类的函数，运行时才确定 —- 这叫“动态联编”。

每一个有虚函数的类（或有虚函数的类的派生类）都有一个虚函数表，该类的任何对象中都放着虚函数表的指针。虚函数表中列出了该类的虚函数地址。多出来的4个字节就是用来放虚函数表的地址的。

下面一段代码将验证，对象的首地址是存了虚函数表的地址的：

    #include <iostream>
    using namespace std;
    class A {
    public: virtual void Func() { cout << "A::Func" << endl; }
    };
    class B:public A {
    public: virtual void Func() { cout << "B::Func" << endl; }
    };
    int main() {
    A a;
    A * pa = new B();
    pa->Func();
    //64位程序指针为8字节
    long long * p1 = (long long * ) & a;
    long long * p2 = (long long * ) pa;
    * p2 = * p1;
    pa->Func();
    return 0;
    }

纯虚函数和抽象类

• 纯虚函数：没有函数体的虚函数
• 抽象类：有纯虚函数的类

注意：

• 包含纯虚函数的类叫抽象类
  • 抽象类只能作为基类来派生新类使用，不能创建独立的抽象类的对象
  • 抽象类的指针和引用可以指向由抽象类派生出来的类的对象

    A a ; // 错，A 是抽象类，不能创建对象
    A * pa ; // ok,可以定义抽象类的指针和引用
    pa = new A ; //错误, A 是抽象类，不能创建对象

• 在抽象类的成员函数内可以调用纯虚函数，但是在构造函数或析构函数内部不能调用纯虚函数。
• 如果一个类从抽象类派生而来，那么当且仅当它实现了基类中的所有纯虚函数，它才能成为非抽象类。

13.从C到C++

指针

指针的声明：

数组

数组的范围必须是常量表达式，同时如果需要变化的范围可以做如下定义：

2.字符串文字量

指的是用 ““括起来的字符串。

• 长字符串编写：
• 带有L的字符是宽字符，如L"sddsf”，类型是const wchar_t.

3.指向数组的指针

4.常量

5.指针和常量

使用一个指针时涉及到两个对象:该指针本身和被它所指的对象。将一个指针的声明用cons“预先固定”将使那个对象而不是使这个指针成为常量。要将指针本身而不是被指对象声明为常量，我们必须使用声明运算符*const，而不能只用简单的const。

定义常量指针的声明运算符是const。并没有cons** 声明符，所以出现在之前的conr是作为基础类型的一部分。例如

// 到char的hconst指针
char *const cp;
char const* pc;
// 到const char的指针
const char* pc2;
//到const char的指针

有人发现从右向左读这种定义很有帮助。例如，“cp是一个conse指针到char”，以及“pe2是一个指针措到const chor”

引用

void f(){
    int ii=1;
    int &rr = ii;
    rr++;//实际上是ii++,rr不能像指针一样操作。
    int *pp = ⅈ
}

12.其他库的介绍

为什么需要哈希函数？

哈希函数在计算机科学中扮演着重要的角色，其主要作用包括：

1. 数据检索：哈希函数可以将键（key）映射到哈希表中的一个位置，从而快速检索数据。这是哈希表（如 C++ 中的 std::unordered_map 和 std::unordered_set）的基础。

2. 快速比较：在数据库和各种数据结构中，哈希函数可以快速比较字符串或对象，常用于检查两个字符串是否相等。

3. 数据分布：在分布式系统中，哈希函数可以将数据均匀地分布到多个节点上，以实现负载均衡。

4. 密码学应用：在密码学中，哈希函数用于生成数据的摘要，用于数据完整性验证和数字签名。

5. 缓存实现：哈希函数可以用于实现缓存机制，通过快速定位缓存中的数据。

6. 负载均衡：在网络流量管理中，哈希函数可以用于将请求分配到不同的服务器上。

C++ 库中哈希函数的实现和底层逻辑

在 C++11 及以后的版本中，标准库提供了一个专门的哈希函数库 <functional>，其中包含了 std::hash 模板类。std::hash 为基本数据类型（如 int、double、std::string 等）提供了特化版本。

实现底层逻辑：

1. 整数类型：对于整数类型，std::hash 直接返回数值本身或其变体。例如，对于 int 类型，std::hash<int>()(10) 可能直接返回 10 或者 10 的一个简单变换。

2. 浮点类型：对于浮点类型，std::hash 通常会将浮点数的位表示转换为整数，然后应用整数的哈希函数。

3. 字符串类型：对于字符串，std::hash 通常会遍历字符串中的每个字符，将每个字符的哈希值组合起来，生成最终的哈希值。这可以通过位操作和数学函数（如乘法、加法、异或等）来实现。

4. 自定义类型：对于自定义类型，如果需要使用 std::hash，则需要为该类型提供自定义的哈希函数。

5. 组合哈希：对于复合类型（如结构体或类），哈希函数需要将各个成员的哈希值组合起来。这通常通过将成员的哈希值进行某种形式的数学运算（如加权求和、异或等）来实现。

6. 均匀分布：一个好的哈希函数应该能够产生均匀分布的哈希值，以减少哈希冲突。

7. 确定性：哈希函数应该是确定性的，即对于同一个输入总是产生相同的哈希值。

8. 快速计算：哈希函数的计算应该尽可能快，以减少对性能的影响。

在 C++ 中，std::hash 的实现可能因编译器和平台而异，但基本原理是相似的。正确实现哈希函数对于哈希表的性能至关重要，因为它直接影响到哈希表的冲突率和检索效率。

hash function-哈希函数

如果要自己给自己的数据写一个哈希函数，那又该怎么写呢？能否基于这些数据计算出hash code的呢？

编写模版规范

    #include <functional>
    namespace test_hash_function
    {
        class Customer {
            private:
            string fname;
            string lname;
            int on;

            public:
                Customer( string fn,  string ln, int id) : fname(fn), lname(ln), on(id) {}
                bool operator==(const Customer& other) const {//需要重载==
                    return fname == other.fname && lname == other.lname && on == other.on;
                }
                friend class CustomerHash;
        };
        class CustomerHash {
        public:
            std::size_t operator()(const Customer& c) const {
                return ...;
            }
        };
        unordered_set<Customer, CustromerHash> custsct;
    }

   #include <functional>
    namespace test_hash_function
    {
        template <typename T>
        inline void hash_combine(size_t& seed, const T& val) {
            seed ^= hash<T>()(val) +
                0x9e3779b9 +
                (seed << 6) +
                (seed >> 2);
        }
        template <typename T>
        inline void hash_val(size_t& seed, const T& val) {
            hash_combine(seed, val);
        }
        template <typename T, typename... Types>
        inline void hash_val(	size_t& seed,
                                    const T& val,
                                    const Types&... args) 
        {
            hash_combine(seed, val);
            hash_val(seed, args...);
        }
        template <typename... Types>
        inline size_t hash_val(const Types&... args) {
            size_t seed = 0;
            hash_val(seed, args...);
            return seed;
        }
        class Customer {
        private:
            string fname;
            string lname;
            int on;

        public:
            Customer( string fn,  string ln, int id) : fname(fn), lname(ln), on(id) {}
            bool operator==(const Customer& other) const {
                return fname == other.fname && lname == other.lname && on == other.on;
            }
            friend class CustomerHash;
        };

        class CustomerHash {
        public:
            size_t operator()(const Customer& c) const {
                return hash_val(c.fname, c.lname, c.on);
            }
        };

        void test() {
            unordered_set<Customer, CustomerHash> s;
            s.insert(Customer("Asd", "dfw", 1L));
            s.insert(Customer("Dfg", "kjt", 2L));
            s.insert(Customer("VVB", "ert", 3L));
            s.insert(Customer("TgR", "uik", 4L));
            s.insert(Customer("Gdf", "pii", 5L));
            s.insert(Customer("Gdf", "pii", 6L));
            s.insert(Customer("Gdf", "pii", 7L));//8
            cout << s.bucket_count() << endl;

            CustomerHash hh;
            cout << hh(Customer("Asd", "dfw", 1L)) % 8 << endl;//4
            cout << hh(Customer("Dfg", "kjt", 2L)) % 8 << endl;//0
            cout << hh(Customer("VVB", "ert", 3L)) % 8 << endl;//3
            cout << hh(Customer("TgR", "uik", 4L)) % 8 << endl;//7
            cout << hh(Customer("Gdf", "pii", 5L)) % 8 << endl;//2
            cout << hh(Customer("Gdf", "pii", 6L)) % 8 << endl;//7
            cout << hh(Customer("Gdf", "pii", 7L)) % 8 << endl;//4

            for (unsigned i = 0; i < s.bucket_count(); i++) {
                cout << "bucked #" << i << "has" << s.bucket_size(i) << "element\n";
            }
        }
    }
    // bucked #0has1element
    // bucked #1has0element
    // bucked #2has1element
    // bucked #3has1element
    // bucked #4has2element
    // bucked #5has0element
    // bucked #6has0element
    // bucked #7has2element

    #include <functional>
    namespace test_hash_function
    {
        class Customer {
            private:
            string fname;
            string lname;
            int on;

            public:
                Customer( string fn,  string ln, int id) : fname(fn), lname(ln), on(id) {}
                bool operator==(const Customer& other) const {//需要重载==
                    return fname == other.fname && lname == other.lname && on == other.on;
                }
                friend class CustomerHash;
        };
        class CustomerHash {
        public:
            size_t customer_hash_func(const Customer& c) const {
                return ...;
            }
        };
        unordered_set<Customer, size_t(*)(const Custromer&)> custsct(20,customer_hash_func);//注意与类型1的不同写法
    }

tuple

在C++中，tuple 是一个标准库模板类，它提供了一种方式来存储不同类型数据的集合。tuple 类似于一个固定大小的数组，但是数组中的每个元素可以是不同的类型。这个特性使得 tuple 非常灵活，可以用于多种场景。

11.STL库学习之适配器

整体框架的回顾

存在多种适配器-adapters

一个人理解，要将适配器理解透彻，我们需要先从别的组件入手，这里以vector容器为例，我们都知道该容器需要迭代器，也就是一些智能指针来确定容器的头尾，以及内容位置，目的是方便后续的算法的怎删改查等操作，假设算法现在要做拿到位置8的数据，那么vector的指针要怎么移动呢？已知指针移动上，vector是随机访问指针，也就是前后都可以跑，而这个操作实际上是迭代器的其中一个内容，而这一内容就需要一个适配器去做适配。

下面做一个模拟问答，来加以了解：

—c 模拟问答 算法：你好，vector的迭代器，我需要知道你的迭代器类别，这样我才能正确地进行操作。

vector的迭代器：好的，我先问一下我的适配器。

vector的迭代器：适配器，算法想知道 iterator_traits<InputIterator>::iterator_category 是什么类型的迭代器？

vector_iterator的适配器：你好，我们这里是随机访问迭代器（Random Access Iterator）。

算法：太好了，随机访问迭代器可以让我进行更高效的操作。那么，如果我想访问第8个元素，我该怎么做？

vector_iterator的适配器：很简单，你可以直接通过加上偏移量来访问第8个元素。比如，如果你有一个指向第一个元素的迭代器 first，那么 first + 7（因为迭代器是从0开始计数的）就会给你第8个元素的迭代器。

算法：明白了，那我可以直接使用 *(first + 7) 来获取第8个元素的值了。

vector_iterator的适配器：是的，完全正确。

算法：如果我需要反向迭代器，或者插入迭代器，你们能提供吗？

vector_iterator的适配器：当然可以。我们 vector 提供了多种迭代器适配器，包括反向迭代器（reverse_iterator）、插入迭代器（insert_iterator）等，以满足不同的需求。

算法：那太好了，这样我可以更灵活地处理 vector 中的数据了。谢谢你的帮助！

STL中适配器的重要特性

对于容器、迭代器和仿函数它们第二次迭代器都有一个重要的特性，就是适配器会包含（也有继承）对应的类，比如stack包含了deque，然后使用了deque的某些功能，屏蔽了deque的某些某能，实现了先进后出的功能。

仿函数适配器

binder2nd适配器

该适配器是用于绑定的，比如对于一个容器，需要操作比88小于数，这使用可以用binder2nd，第一个参数可以传入比较大小的less仿函数，第二个传入比较的数值x，本质上在binder2nd中，less的第二个参数传入就是x,这样就达到比较的目的了。 小结：把A类和数值a传入另一个类B中，在B中再操作A和a.这样就实现了绑定。

not1

对结果取反

一些新的适配器

bind

迭代器适配器

reverse——iterator

三个细节：

• 1.begin=rend,end=rbigin
• 2.取值是取后一个，所以内部实现的*是做–操作；
• 3.operate ++()操作重载后内部实现为–，operate –()重载后内部实现++操作。

具体图下图所示

insert_iterator

在下面的案例中copy(bar.begin(),bar.end(),inserter(foo,it));欲将list的bar数据从it指向的位置 开始插入，但是foo的空间不够，为什么还能成功？

设计的小技巧，当传入copy中时，因为inserter对operate =()做了重载，重载中调用了insert()该函数能决绝以上问题， 因此不会因为foo的内存不足导致插入失败。

ostream_iterator

下面通过一个案例说明该迭代器的一些特性和使用方法：

1.当执行初始化操作std::ostream_iterator out_it(std::cout,",")时调用构造函数，并初始化。 2.执行copy操作时，因为ostream_iterator对operate =()重载，所以会将值value传给*out_stream，通过这个方法把数据打印在屏幕上。

istream_iterator

下面也是两个例子说明istream_iterator的特性：

1.std::istream_iterator<double> iit(std::cin);时同样会调用对应的构造函数，并且此处会调用operate ++()重载，在该重载中，*in_stream接收按键输入的一个值，也就是说才定义时，就已经在准备接收一个值，如果此时在该语句下写一段打印操作没见无法看到输出！

2.下面是copy操作，对于这个操作，我们可以观察是否有对*和=的操作符进行重载，对于=的重载上述已经介绍， *的重载是将value返回，也就是 *first的操作取得的是容器中的值。

10.STL库学习之仿函数

仿函数的个人理解

仿函数是行为类似函数的一个类，比较明显的特征是仿函数重载了operate()，比如你写了一个struct，并在里面重载了operate()，当调用这个类的()时就会返回响应的数据。

你的理解是正确的，仿函数（functor）是 C++ 中的一个概念，它指的是那些可以像函数一样被调用的对象。这些对象通常重载了函数调用操作符 operator()，使得对象可以被当作函数来使用。以下是对你描述的一些补充说明：

仿函数的特点

1. 重载 operator()：仿函数类必须重载函数调用操作符 operator()，这样对象就可以被像函数那样调用。

2. 可以携带状态：与普通函数不同，仿函数可以拥有成员变量，这意味着它们可以携带状态。这些状态可以是私有的，也可以是公开的，取决于仿函数的设计。

3. 可以进行重载：仿函数可以重载 operator()，以接受不同数量和类型的参数。

4. 可以定义在类中：仿函数可以是类的成员函数，也可以是独立的类。

5. 可以有返回值：当仿函数被调用时，可以返回一个值，就像普通函数那样。

6. 可以作为参数传递：由于仿函数可以像函数一样被调用，它们可以作为参数传递给接受函数作为参数的函数。

仿函数的应用

1. 算法的参数：仿函数经常用作 STL 算法的参数，例如 std::sort 和 std::find_if，因为这些算法需要一个可以被调用的实体来比较元素或测试条件。

2. 回调函数：在事件驱动的编程中，仿函数可以作为回调函数，响应特定的事件。

3. 策略模式：在设计模式中，仿函数可以用于实现策略模式，允许算法的行为在运行时动态改变。

4. 简化代码：通过使用仿函数，可以减少函数指针和全局函数的使用，使得代码更加简洁和易于管理。

示例代码

struct Max {
    // 重载()操作符，使其可以被调用
    int operator()(int a, int b) const {
        return (a > b) ? a : b;
    }
};

int main() {
    Max max_functor;
    int result = max_functor(10, 20); // 使用仿函数对象调用
    std::cout << "Max value: " << result << std::endl;
    return 0;
}

在这个例子中，Max 是一个仿函数，它重载了 operator() 来比较两个整数并返回最大值。然后，我们可以像调用函数一样调用 max_functor 对象。

仿函数内部一般设计什么？

仿函数一般重载operate()后，会在内部设计运算操作，如算数、逻辑、相对关系等运算。如下图所示。 从上面一张图也可以发现，plus,minus,logical_and,equal_to,less类都集成了binary_function，该类的作用是什么呢？

std::binary_function 的主要作用是：

1. 泛型框架：提供一个泛型框架，允许函数对象接受任意类型的参数。
2. 类型转换：允许参数类型和返回类型的转换，使得函数对象可以用于不同的数据类型。
3. 模板编程：支持模板编程，使得可以创建通用的算法和函数。

• 原型

std::binary_function 的原型如下：

template <class Arg1Type, class Arg2Type, class ResultType>
struct binary_function {
    typedef Arg1Type first_argument_type;
    typedef Arg2Type second_argument_type;
    typedef ResultType result_type;
};

• Arg1Type：第一个参数的类型。

• Arg2Type：第二个参数的类型。

• ResultType：函数返回值的类型。

• 继承和使用

函数对象如 std::plus, std::minus, std::logical_and, std::equal_to, std::less 等都继承自 std::binary_function。这意味着这些函数对象都定义了 first_argument_type, second_argument_type, 和 result_type 这三个类型别名，它们分别表示函数对象接受的第一个参数类型、第二个参数类型和返回值类型。

关于 std::binary_function的具体细节在适配器一节会重点讲到。

下图是是否继承binary_function的一些示例，如果不继承会怎么样呢？以我个人的理解，继承会让仿函数的扩展性更高，它将来可以扩展出更好的功能。如下图所示。

除了上面讲到的binary_function还有unary_function，该类是针对单个变量的操作，比如取反，加加。如下图：

关于binary_function的细节此处先不介绍，下一节将着重说明。

对于仿函数，鲜明的特点就是对operate()做了重载，这样的类创建出来的对象叫仿函数对象，具有函数的行为。如果要对重载做更多操作需要结合一些仿函数适配器，比如相面讲到的binary_function和unary_funtion。

9.STL库学习之迭代器与算法

标准库常用算法

迭代器

迭代器-的分类

struct input_iterator_tag {}；
struct output_iterator_tag {};
struct forward_iterator_tag:public input_iterator_tag{};
struct bidirectional_iterator_tag:public forward_iterator_tag{};
struct random_access_tag:public bidirectional_iterator_tag {};

以上5中迭代器的继承关系，如下图所示。

1.Input Iterator（输入迭代器）： 输入迭代器是最基本的迭代器类型，支持单向遍历，只能向前移动。

用法示例：

     std::vector<int> vec = {1, 2, 3, 4, 5};
     std::input_iterator<int> it = vec.begin();
     while (it != vec.end()) {
         std::cout << *it << " ";
         ++it;
     }

2.Forward Iterator（前向迭代器）： 前向迭代器支持双向遍历，可以向前和向后移动。

用法示例：

     std::list<int> lst = {1, 2, 3, 4, 5};
     std::forward_iterator<int> it = lst.begin();
     while (it != lst.end()) {
         std::cout << *it << " ";
         ++it;
     }

3.Output Iterator（输出迭代器）： 输出迭代器允许对容器中的元素进行写操作，但不支持读操作。

用法示例：

     std::vector<int> vec;
     std::back_insert_iterator<std::vector<int>> it(vec);
     *it = 1; // 写操作
     ++it;
     *it = 2; // 写操作

4.Bidirectional Iterator（双向迭代器）： 双向迭代器支持双向遍历，可以向前和向后移动。

用法示例：

     std::list<int> lst = {1, 2, 3, 4, 5};
     std::bidirectional_iterator<int> it = lst.end();
     while (it != lst.begin()) {
         --it;
         std::cout << *it << " ";
     }

5.Random Access Iterator（随机访问迭代器）： 随机访问迭代器支持任意位置的快速访问，类似于指针操作。

用法示例：

     std::vector<int> vec = {1, 2, 3, 4, 5};
     std::random_access_iterator<int> it = vec.begin();
     it += 2; // 随机访问
     std::cout << *it << " ";

各种容器的迭代器类型

测试代码：

    #include <iterator> 
    namespace test_iterator_category
    {
        template <typename T>
        void display_category(T itr) {
            typename iterator_traits<T>::iterator_category cagy; // 使用 std::iterator_traits 获取迭代器类别
            // 这里不需要递归调用 display_iterator 函数
            cout << typeid(cagy).name() << endl;
        }

        void test() {
            cout << "\ntest_iterator_category....................\n";
            display_category(array<int, 10>::iterator());
            display_category(vector<int>::iterator());
            display_category(list<int>::iterator());
            display_category(forward_list<int>::iterator());
            display_category(deque<int>::iterator());

            display_category(set<int>::iterator());
            display_category(map<int, int>::iterator());
            display_category(multiset<int>::iterator());
            display_category(multiset<int, int>::iterator());

            display_category(istream_iterator<int>());
            display_category(ostream_iterator<int>(cout,""));
        }
    }

此处可以参考一下display_category(array<int, 10>::iterator());中传递array<int, 10>::iterator()的方法。

测试结果：

test_iterator_category....................
struct std::random_access_iterator_tag
struct std::random_access_iterator_tag
struct std::bidirectional_iterator_tag
struct std::forward_iterator_tag
struct std::random_access_iterator_tag
struct std::bidirectional_iterator_tag
struct std::bidirectional_iterator_tag
struct std::bidirectional_iterator_tag
struct std::bidirectional_iterator_tag
struct std::input_iterator_tag
struct std::output_iterator_tag

迭代器对算法的影响

例子1-distance

迭代器如何计算容器元素之间的距离呢？当调用迭代器时，迭代器是如何操作以协助算法完成后续的增删改查的？

在计算距离方面，我们可以看到调用接口需要传入容器的头，以及容器尾部，接着使用：

    ...
    typedef typename iterator_traits<InputIterator>::itrerator_category category;
    return __distance(first,last, category);

typedef typename iterator_traits<InputIterator>::itrerator_category category;这一句会判断迭代器的类型，进而执行加操作或一步一步加操作。详细如下图所示。

例子2-copy

copy的动作也不仅仅是对迭代器类型的判断，还做了许多特化、偏特化。如下图所示。

例子3-destroy

例子4-__unique_copy

对传入的迭代器类型的暗示

在调用一些需要传入迭代器的函数时，从函数的形参名可以判断传入的迭代器类型，如InputIterator，由于forward_iterator_tag、bidirection_iterator_tag、random_asccess_iterator_tag与input_iterator的继承关系可知，前三者都可以传入，以此类推如果形参是forward_iterator_tag那么除了其本身，bidirection_iterator_tag、random_asccess_iterator_tag也可传入。

算法源码剖析

accumulate-累计

测试用例：

    #include <functional>//std::minus
    #include <numeric>//std::accumulate
    namespace test_accumulate
    {
        int myfcn(int x, int y) { return x + 2 * y; }
        struct myclass {
            int operator()(int x, int y) { return x + 3 * y; }
        } myobj;
    }
    void test(){
        int init = 10;
        int nums[] = {10,10,10};
        cout << accumulate(nums, nums + 3, init)<<endl;//40
        cout << accumulate(nums, nums + 3, init, test_accumulate::myfcn)<<endl;//70
        cout << accumulate(nums, nums + 3, init, test_accumulate::myobj) << endl;//100
    }

for_each

拿到每一个元素时都对该元素执行某一操作。

测试用例：

    namespace test_for_each
    {
        void myfcn(int i) { cout<<i<<"-"; }
        struct myclass {
            void operator()(int i) { cout << "[" << i<<"] "; }
        } myobj;
        void test() {
            vector<int> c;
            c.push_back(10);
            c.push_back(20);
            c.push_back(30);
            for_each(c.begin(), c.end(), test_for_each::myfcn);//10-20-30-
            cout << "\n";
            for_each(c.begin(), c.end(), test_for_each::myobj);//[10] [20] [30]
        }
    }

replace,replace_if,rreplace_copy

replace用于将新值替换为旧值，例如将数组中所有的8替换为9.详细源码如下图所示。

replace、replace_if 和 replace_copy 是 C++ 标准库中的算法，它们用于在容器或数组中替换元素。这些函数属于 <algorithm> 头文件。下面是每个函数的详细介绍和作用：

1. replace

replace 函数用于将容器中所有满足特定条件的元素替换为另一个值。这个函数直接在原容器上操作，不创建新的容器。

函数原型:

void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);

• first, last：定义了要替换元素的范围。
• old_value：要被替换的值。
• new_value：替换后的值。

示例:

vector<int> v = {1, 2, 3, 4, 3, 2};
replace(v.begin(), v.end(), 2, 5);
// v 变为 {1, 5, 3, 4, 3, 5}

2. replace_if

replace_if 函数用于将容器中满足特定条件的元素替换为另一个值。与 replace 不同，replace_if 需要一个谓词（条件函数），只有满足这个条件的元素才会被替换。这个函数也直接在原容器上操作。

函数原型:

void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);

• first, last：定义了要替换元素的范围。
• pred：一个谓词函数，返回 true 表示替换，false 表示不替换。
• new_value：替换后的值。

示例:

vector<int> v = {1, 2, 3, 4, 3, 2};
replace_if(v.begin(), v.end(), [](int i) { return i == 2; }, 5);
// v 变为 {1, 5, 3, 4, 3, 5}

3. replace_copy

replace_copy 函数用于将容器中所有满足特定条件的元素复制到另一个容器中，并替换为另一个值。这个函数不会改变原容器，而是创建一个新的容器，其中包含替换后的元素。

函数原型:

template <class InputIterator, class OutputIterator>
OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value);

• first, last：定义了要替换元素的范围。
• result：指向目标容器的迭代器，用于存储替换后的元素。
• old_value：要被替换的值。
• new_value：替换后的值。

示例:

vector<int> v = {1, 2, 3, 4, 3, 2};
vector<int> v2(v.size());
replace_copy(v.begin(), v.end(), v2.begin(), 2, 5);
// v 保持不变，v2 变为 {1, 5, 3, 4, 3, 5}

count，count_if

源代码如下：

小结：

find，find_if

sort

binary_search

算法原理：

二分查找的基本思想是将一个有序序列分为两半，通过比较中间元素和目标值来缩小搜索范围。如果中间元素正好是目标值，则查找成功；如果目标值小于中间元素，则在序列的左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。这个过程不断重复，直到找到目标值或搜索范围为空。

函数原型：

binary_search 的函数原型如下：

template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first,
                   ForwardIterator last,
                   const T& value);

• first, last：定义了要搜索的范围，first 是序列的开始迭代器，last 是序列的结束迭代器（指向序列末尾的下一个位置）。
• value：要查找的值。

返回值：

• 如果在序列中找到 value，则返回 true。
• 如果没有找到，则返回 false。

示例代码：

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int target = 5;

    bool found = std::binary_search(data.begin(), data.end(), target);

    if (found) {
        std::cout << "Element found in the array." << std::endl;
    } else {
        std::cout << "Element not found in the array." << std::endl;
    }

    return 0;
}

注意事项：

1. 有序序列：binary_search 要求序列必须是有序的，否则查找结果将不可预测。
2. 效率：二分查找的时间复杂度为 O(log n)，其中 n 是序列中的元素数量。这使得它比线性查找（O(n)）更高效，尤其是在大数据集上。
3. 稳定性：如果存在多个相同的目标值，binary_search 将返回第一个匹配的位置。如果需要找到所有匹配项，可能需要使用其他方法。

8.STL库学习之容器

list

vector

deque

deque的迭代器

deque实现中间插入值的做法：如果欲插入值在最前端（最尾端）调用push_front()（push_back()）,否则借助insert_aux()迭代器，实现如果欲插入位置靠近前端使用，就让前端的数据往前挪，否则往后挪。

deque中+=的实现：1.先计算+=后是否超过缓冲区，如果没有则直接+=，否则需要判断需要跨几个缓冲区，然后再去确定前进几个缓冲区。

Vector的内存扩充：

std::vector 在需要更多空间时，通常会将容量增加到当前大小的两倍（这是最常见的增长策略，但不是唯一的，具体实现可能有所不同）。

当发生扩充时，std::vector 会分配一个新的更大的内存块，然后将所有元素从旧内存块复制到新内存块，最后释放旧内存块。

Deque的内存扩充：

std::deque（双端队列）的内存管理机制与 std::vector 不同。std::deque 是一个使用多个固定大小的内存块来存储元素的容器，这些内存块被称为“chunks”或“maps”。

当 std::deque 需要更多空间时，它可能会在已有的内存块之后添加新的内存块，或者在前面添加，这取决于哪个方向上的空间更紧张。 std::deque 不会像 std::vector 那样将所有元素复制到一个新的连续内存块中，而是在多个内存块之间分配元素。

stack和queue

stack和queue默认使用deque的功能来分别实现先进后出和先进先出的功能，除此之外还可以使用list，stack还可以使用vector，但是deque就不能用vector，以我的理解，是因为vector不提供后端操作。

Rb-tree

在C++中，set和map的底层实现都是基于红黑树（RB-tree）。红黑树是一种自平衡的二叉搜索树，能够保证在最坏情况下，插入、删除和查找操作的时间复杂度均为O(log n)。

    template <  int key,
                int value,
                identity<int>,
                less<int>,
                alloc
                >
    class rb_tree;

set 和 map 的区别：

set：set中的元素是唯一的键值，即Key和Value是同一个。插入时使用insert_unique()方法，确保键值不重复。

map：map中的元素是键值对（Key-Value），键值用于索引，值表示与索引相关联的数据。插入时使用insert_equal()方法，允许键值重复。

红黑树的结构：

红黑树的结构包括节点、根节点、最左节点和最右节点等。根节点通过header.parent保存，最左节点通过header.left保存，最右节点通过header.right保存。

• 插入操作
  • set：插入操作调用insert_unique()，确保键值唯一。
  • map：插入操作调用insert_equal()，允许键值重复。
• 迭代器
  • set：迭代器是RB-tree的const_iterator，不允许修改元素值。
  • map：迭代器也是RB-tree的const_iterator，但允许修改元素的值（因为值部分不是键）。

set和multiset

set与map的底层实现基本可以参考下面的源码图，

需要说明的一点是，在不允许更改键值上，二者的设计还是有区别，主要体现在set使用const_iterator,这样迭代器指向的键值就无法更改，而map在设计上在传进来的Key设置为const，确保键值不会被更改。

hashtable-哈希表

在C++中，hash_set、hash_map、hash_multiset和hash_multimap等数据结构的底层实现确实采用了哈希表的思想。具体来说，这些数据结构的设计核心是通过哈希函数将键（key）映射到数组的索引位置，从而实现高效的插入、删除和查找操作。

数据存储的设计思想

每个键值通过一个哈希函数计算出一个哈希值。这个哈希值通常是一个整数，用于确定键值在数组中的存储位置。例如，对于一个整数键值12，哈希函数可能会直接返回12，这样12就会被存储在数组的第12个位置。

哈希表的核心是一个数组（通常是一个vector），数组的每个元素（即每个位置）可以存储一个指针。这个指针指向一个单向链表的头节点。如果多个键值通过哈希函数计算出相同的哈希值，它们会被存储在同一个位置的链表中。参考下图： 当多个键值映射到同一个哈希值时，这些键值会被存储在一个链表中。链表的每个节点包含一个键值和指向下一个节点的指针。这种设计允许在发生哈希冲突时，通过遍历链表来查找或插入特定的键值。 为了保持高效的性能，哈希表通常会有一个动态扩容机制。当哈希表中的元素数量超过一定阈值时，哈希表会自动重新分配更大的数组，并重新计算所有键值的哈希值，以减少链表的长度，从而提高查找效率。

在实际应用中，哈希函数可能会导致不同的键值计算出相同的哈希值，这种现象称为哈希冲突。常见的解决策略包括链地址法（即使用链表存储冲突的元素）和开放地址法（即在数组中寻找下一个空闲位置）。

具体实现过程

• 当插入一个新键值时，首先通过哈希函数计算出其哈希值，然后根据哈希值找到对应的数组位置。如果该位置已经有元素（即发生冲突），则将新元素插入到该位置的链表中。
• 查找操作同样通过哈希函数计算出键值的哈希值，然后根据哈希值找到对应的数组位置。如果该位置有元素，则遍历链表，直到找到匹配的键值或链表结束。
• 删除操作首先通过哈希函数计算出键值的哈希值，然后根据哈希值找到对应的数组位置。如果该位置有元素，则遍历链表，找到并删除匹配的键值。

实现代码

hashtable类的实现提供了六个模板参数。

  template <class value,
            class key,
            class hashFcn,//计算编号
            class extractKey,//取出键值
            class EqualKey,//判断类型是否相等
            class Alloc=alloc
            >

如果要自己使用这个哈希表，需要写hashFcn()的重载，对齐进行偏特化等操作,如下图：

如果传入的是字符串，那么字符串的编号计算可以参考下图计算方法：

7.STL库学习之分配器

分配器源代码位置：xmemory.h

除了array和vector外，其他容器的适配器必须是一个类，

6.STL库学习之筑基概要

STL程序源代码位置

了解自身编译器STL程序源代码位置。

OOP 与 GP

面向对象编程（OOP）：

面向对象编程是一种编程范式，它将数据和处理这些数据的方法封装在对象中。这种方法强调了数据和函数的捆绑，使得代码更加模块化，易于理解和维护。对象可以包含属性（数据）和方法（函数），它们一起工作来模拟现实世界的行为。

补充说明：OOP 通过类（Class）来定义对象的蓝图，支持继承、封装和多态等特性，从而提高代码的重用性和灵活性。例如list中有自己的sort()函数，专门为list而设计，比::sort()的算法更优。

泛型编程（GP）：

泛型编程是一种编程范式，它允许开发者定义操作类型数据结构的函数和类，而不需要在编译时指定具体的数据类型。这种方法强调了数据和处理方法的分离，提供了更高的代码复用性和类型安全性。

补充说明：GP 通过模板（Templates）或泛型容器（如 std::vector、std::map）来实现，允许开发者写出与数据类型无关的代码，从而在不同的数据类型间共享相同的算法逻辑。例如vector和deque没有为自身设计sort(),在做排序操作时，需要调用::sort()来实现。

操作符重载

STL源码程序中会包含很多的操作符重载，一般你会看到operate修饰符，后面就紧跟着操作符。注意：::、.、.*和 :?不能进行操作符重载。

在我看来操作符重载是一个重要的特性，它可以让你实现任何类的运算法则，这些法则有你自己规定，操作空间还是比较宽泛。

模版-template

最常见的写法如下：

    template <typename T>
    class FOO{
        ...
    }

类模板

最常见的写法如下：

    template <class T>
    class FOO{
        ...
    }

成员模版

泛化、特化和偏特化

以我个人的理解，泛化是为了应对大部分的情况，特化是为了应对特殊的情况，或使用单独的方法处理对某些情况而言更好，偏特化比偏特化更近一步，把处理的手段限定在一定范围内，举个简单的例子，假设为设计计算两种情况的相加做如下定义：

1.泛化

泛化编程在C++中通过模板实现。以下是一个泛化编程的示例，其中 AND 类是一个模板类，可以处理任何类型的数据。

    template <class T,class U>
    class AND{
        ...
    }

2.特化

特化是对模板类或函数的特定实例化。以下是特化的示例，其中 AND 类被特化为处理 string 和 Text 类型：

    template <class T, class U>
    class AND {
        // ... 类的泛型实现
    };

    template <>
    class AND<string, Text> {
        // ... 类的特化实现
    };

3.偏特化

偏特化允许对模板类的部分参数进行特化。以下是偏特化的示例，其中 AND 类被偏特化为处理第一个类型为 int 的情况：

    template <class T, class U>
    class AND {
        // ... 类的泛型实现
    };

    template <class U>
    class AND<int, U> {
        // ... 类的偏特化实现
    };

5.STL库之观其大略

一下主要讲STL组件的测试用例，特别是容器的测试

学习资料

• CPLusPlus.com
• CppReference.com
• gcc.gnu.org
• 《STL源码剖析》

STL六大组件

• 容器-Containers，申请内存用于存储数据
• 分配器-Allocators，配合容器分配内存
• 算法- Algorithms，处理某一数据的最优办法
• 迭代器- Iterators，指针的泛型，本质与指针类似
• 适配器- Adapters，
• 仿函数-Functors，类似函数。

六者的关系

begin()和end()

以迭代器为例，begin()指向迭代器的首地址，而end()指向迭代器尾地址的下一位，可以用前闭后开区间来表示，即**[ )**

容器的分类

数组容器的使用

array 的使用

        #ifndef __AUXFUN__
        #define __AUXFUN__
        #include <iostream>
        #include <string>
        #define RAMD_MAX 32767
        using namespace std;
        long get_a_target_long()
        {
            long target = 0;
            cout << "target (0--" << RAMD_MAX << "):";
            cin >> target;
            return target;
        }

        //将数值转为string，这样可以测试类似object的情况
        string get_a_target_string()
        {
            long target = 0;
            char buf[10];

            cout << "target (0--" << RAMD_MAX << "):";
            cin >> target;
            snprintf(buf, 10, "%d", target);

            return string(buf);
        }
        int compareLongs(const void* a, const void* b)
        {
            return (*(long*)a - *(long*)b);
            /*
            1.类型转换：因为参数是const void* 类型，你需要将它们转换为具体的数据类型指针（在这个例子中是long* ），以便可以解引用并获取它们的值。

            2.解引用：在转换之后，通过在类型转换的结果前使用* 操作符来获取指针指向的实际值。

            3.强制转换的结果：* (long*)a实际上是一个long值，它是通过解引用转换后的指针得到的。*/
        }
        int compareString(const void* a, const void* b)
        {
            if (*(long*)a > *(long*)b)
                return 1;
            else if (*(long*)a < *(long*)b)
                return -1;
            else
                return 0;
        }
        #endif // !__ENTRY__

    #include "TestHeardFiles/AuxFun.h"
    #include <ctime>
    #include <cstdlib>//qsort()、 bsearch()、 NULL
    #include <array>

    const size_t ASIZE = 50000;

    namespace t01
    {
        void test_array()
        {
            cout << "\ntest_array().............. \n";
            array<long, ASIZE> c;//使用数组容器

            clock_t timeStart = clock();
            for (long i = 0; i < ASIZE; ++i)
            {
                c[i] = rand();//可以产生随机数的函数
            }
            cout << "milli_seconds: " << (clock() - timeStart) << endl;
            cout << "array.size(): " << c.size() << endl;//返回数组大小
            cout << "array.back(): " << c.back() << endl;//返回数组最后一个数
            cout << "array.data: " << c.data() << endl;//返回第一个数的地址

            long target = get_a_target_long();
            timeStart = clock();//clock()返回毫秒数
            qsort(c.data(), ASIZE, sizeof(long), compareLongs);//数组排序
            long* pItem = (long*)bsearch(&target, (c.data()), ASIZE, sizeof(long), compareLongs);//数组查找
            cout << "qsort()+bsearch(),milli-seconds:" << clock() - timeStart << endl;
            if (pItem != NULL)
            {
                cout << "found," << *pItem << endl;
            }
            else
                cout << "Not found!" << endl;
        }
    }
    int main() {
        t01::test_array();
    }

vector 的使用

vector是一种向后自动以2次方增加的内存的容器，一般使用push_back向后添加数据；

vector也有一定的缺点，假设我只需要5个内存空间，但是vector分配的是8个，剩下的3个后面如果不使用就会浪费。

    #include <vector>
    #include <stdexcept> //obort()
    #include <cstdio>	//snprintf()
    #include <algorithm>//sort()
    namespace t02
    {
        void test_vector(long& value) {
            cout << "\ntest_vector()..............\n";
            vector<string> c;
            char buf[10];
            clock_t timeStart = clock();
            for (long i = 0; i < value; ++i)
            {
                try
                {
                    snprintf(buf, 10, "%d", rand());
                    c.push_back(string(buf));//将随机数转为string类型，并使用push_back()将数据存入容器尾部，这是vector的特性
                    //同时值得注意，当空间不足时，内存会自动增加，怎么加方式是2的平方
                }
                catch (exception& p)
                {
                    cout << "i=" << i << " " << p.what() << endl;
                    abort();//发生异常使用该函数退出程序
                }
            }
            cout << "milli-seconds: " << (clock() - timeStart) << endl;
            cout << "vector.size(): " << c.size() << endl;
            cout << "vector.front(): " << c.front() << endl;
            cout << "vector.back(): " << c.back() << endl;
            cout << "vector.data(): " << c.data() << endl;
            cout << "vector.capacity(): " << c.capacity() << endl;//返回的是向量当前分配的存储空间可以容纳的元素个数
            string target = get_a_target_string();//获取输入的数字，并转为string类型返回
            //使用算法find查找
            {
                timeStart = clock();
                auto pItem = ::find(c.begin(), c.end(), target);//返回类型是：使用全局::find()寻找目标，这是循环寻找
                cout << "::find(),milli-seconds: " << (clock() - timeStart) << endl;

                //判断有没有找到
                if (pItem != c.end()) {
                    cout << "found," << *pItem << endl;
                }
                else
                {
                    cout << "Not fount!" << endl;
                }
            }
            //进行排序后使用bsearch查找。
            {
                timeStart = clock();
                sort(c.begin(), c.end());//该算法将任何类型进行排序，需要提供相应的比较函数
                string* pItem = (string*)bsearch(&target, (c.data()), c.size(), sizeof(string), compareString);
                cout << "sort()+bsearch(),milli-seconds: " << (clock() - timeStart) << endl;
                if (pItem != NULL) {
                    cout << "found," << *pItem << endl;
                }
                else
                {
                    cout << "Not fount!" << endl;
                }
            }
        }
    }

从上面的结果来看，排序后使用二分查找反而比循环查找慢，原因在于排序话费了很多时间，因为string类型是一个object，其本身大小比较大，所以面对一个object进行查找时不建议使用排序后二分查找。

在实际应用中，选择排序加二分查找还是直接线性查找，需要根据具体情况来决定：

• 如果容器已经排序，或者数据量不大，直接使用二分查找可能更简单、更快。
• 如果容器未排序，且数据量很大，那么可能需要考虑是否值得为了一次查找而进行排序，或者是否可以通过其他方式（如使用更高效的数据结构，如哈希表）来提高查找效率。
• 如果查找操作非常频繁，而插入和删除操作不频繁，那么维护一个已排序的容器可能是合理的，这样每次查找都可以利用二分查找的效率。

总之，选择哪种方法取决于具体的应用场景和性能要求。在某些情况下，可能需要通过实验或性能分析来确定最佳的策略。

链表容器-list

std::list 是 C++ 标准库中的一个容器，它提供了双向链表的实现。

std::list 容器的特点：

• 双向链表结构：std::list 由一系列节点组成，每个节点包含一个元素和两个指针，分别指向前一个节点和后一个节点。
• 动态内存分配：std::list 中的每个节点都是独立分配内存的。这意味着当你添加或删除元素时，std::list 会为新元素分配内存，或释放不再使用的元素所占用的内存。
• 内存空间利用：由于 std::list 的元素是单独分配的，因此不存在像 std::vector 那样的连续内存块，也就不会有额外的内存浪费。每个元素恰好占用它所需的空间，加上一些指针存储开销。

查询操作效率：

• 查询效率较低：与 std::vector 或 std::array 这样的随机访问容器相比，std::list 的查询操作通常较慢。这是因为 std::list 没有提供快速的随机访问能力。
• 顺序访问：在 std::list 中，要访问一个特定位置的元素，你需要从头开始遍历，直到到达那个位置。这意味着访问时间与列表的大小成正比，最坏情况下的时间复杂度为 O(n)。
• 没有跳跃访问：与数组或 std::vector 不同，std::list 没有提供直接跳到任意位置的能力。在数组中，你可以通过简单的指针算术来访问任意位置的元素，而在 std::list 中，你必须遍历链表。

测试代码：

    #include <list>
    namespace t03
    {
        void test_list(long& value)
        {
            cout << "\ntest_list()..............\n";
            list<string> c;
            char buf[10];
            clock_t timeStart = clock();
            for (long i = 0; i < value; ++i)
            {
                try
                {
                    snprintf(buf, 10, "%d", rand());
                    c.push_back(string(buf));//将随机数转为string类型，并使用push_back()将数据存入容器尾部，这是vector的特性
                    //同时值得注意，当空间不足时，内存会自动增加，怎么加方式是2的平方
                }
                catch (exception& p)
                {
                    cout << "i=" << i << " " << p.what() << endl;
                    abort();//发生异常使用该函数退出程序
                }
            }
            cout << "milli-seconds: " << (clock() - timeStart) << endl;
            cout << "list.size(): " << c.size() << endl;
            cout << "list.max_size(): " << c.max_size() << endl;
            cout << "list.front(): " << c.front() << endl;
            cout << "list.back(): " << c.back() << endl;

            string target = get_a_target_string();//获取输入的数字，并转为string类型返回
            //使用算法find查找
            {
                timeStart = clock();
                auto pItem = ::find(c.begin(), c.end(), target);//返回类型是：使用全局::find()寻找目标，这是循环寻找
                cout << "::find(),milli-seconds: " << (clock() - timeStart) << endl;

                //判断有没有找到
                if (pItem != c.end()) {
                    cout << "found," << *pItem << endl;
                }
                else
                {
                    cout << "Not fount!" << endl;
                }
            }
            //测试排序花费的时间
            {
                timeStart = clock();
                c.sort();//使用list自带的排序函数，当然也可以用全局的sort，一般如果容器自带，则选择自带的。
                cout << "list.sort(),milli-seconds: " << (clock() - timeStart) << endl;
            }
        }
    }

    How much memory space you need: 1000000

    test_list()..............
    milli-seconds: 1073
    list.size(): 1000000
    list.max_size(): 329406144173384850
    list.front(): 41
    list.back(): 12679
    target (0--32767):12345
    ::find(),milli-seconds: 4
    found,12345
    list.sort(),milli-seconds: 1611

总结： std::list 的优点在于它的灵活性和高效的插入/删除操作，这些操作可以在 O(1) 时间内完成，因为它们只需要修改几个指针。然而，这种灵活性的代价是牺牲了快速随机访问的能力。因此，如果你的应用场景中需要频繁地在序列中间插入或删除元素，而不太关心随机访问性能，std::list 是一个很好的选择。反之，如果随机访问是一个关键操作，那么可能需要考虑使用其他类型的容器。

链表容器-forward_list

std::forward_list 是 C++ 标准库中的一个容器，它提供了单向链表的实现。

std::forward_list 容器的特点：

• 单向链表结构：std::forward_list 由一系列节点组成，每个节点包含一个元素和一个指向下一个节点的指针。
• 内存分配：与 std::list 类似，std::forward_list 的元素也是动态分配内存的。但是，由于它是单向链表，所以只能从链表的前端（头部）开始进行内存分配。
• 操作限制：由于 std::forward_list 的单向特性，它只提供了 push_front() 和 pop_front() 操作来在链表的前端添加或删除元素。不支持快速的随机访问，也不支持在链表的中间或末尾进行插入和删除操作。

内存使用效率：

• 无尾插法：std::forward_list 没有 push_back() 方法，只能使用 push_front() 在链表的头部插入元素。这意味着，如果你需要在链表的末尾添加元素，你将不得不遍历整个链表以到达末尾，这在大型数据集中可能效率较低。
• 节省空间：与 std::list 相比，std::forward_list 每个节点只需要存储一个指向下一个节点的指针，因此它的内存开销比 std::list 小。

适用场景：

• 空间敏感的应用：如果你的应用对内存使用非常敏感，且需要从链表的前端进行频繁的插入和删除操作，std::forward_list 是一个不错的选择。
• 单向遍历：如果你的应用只需要从链表的前端开始遍历元素，那么 std::forward_list 可以提供良好的性能。

测试代码

    #include <forward_list>
    namespace t04
    {
        void test_forward_list(long& value)
        {
            cout << "\nforward_list()..............\n";
            forward_list<string> c;
            char buf[10];
            clock_t timeStart = clock();
            for (long i = 0; i < value; ++i)
            {
                try
                {
                    snprintf(buf, 10, "%d", rand());
                    c.push_front(string(buf));//将随机数转为string类型，并使用push_frond()将数据存入容器头部，forward_list没有push_back()
                }
                catch (exception& p)
                {
                    cout << "i=" << i << " " << p.what() << endl;
                    abort();//发生异常使用该函数退出程序
                }
            }
            cout << "milli-seconds: " << (clock() - timeStart) << endl;
            cout << "forward_list.max_size(): " << c.max_size() << endl;
            cout << "forward_list.front(): " << c.front() << endl;
            //cout << "forward_list.back(): " << c.back() << endl;	没有该函数
            //cout << "forward_list.size(): " << c.size() << endl;	没有该函数

            string target = get_a_target_string();//获取输入的数字，并转为string类型返回
            //使用算法find查找
            {
                timeStart = clock();
                auto pItem = ::find(c.begin(), c.end(), target);//返回类型是：使用全局::find()寻找目标，这是循环寻找
                cout << "::find(),milli-seconds: " << (clock() - timeStart) << endl;

                //判断有没有找到
                if (pItem != c.end()) {
                    cout << "found," << *pItem << endl;
                }
                else
                {
                    cout << "Not fount!" << endl;
                }
            }
            //测试排序花费的时间
            {
                timeStart = clock();
                c.sort();//使用forward_list自带的排序函数，当然也可以用全局的sort，一般如果容器自带，则选择自带的。
                cout << "forward_list.sort(),milli-seconds: " << (clock() - timeStart) << endl;
            }
        }
    }

    How much memory space you need: 1000000

    forward_list()..............
    milli-seconds: 965
    forward_list.max_size(): 384307168202282325
    forward_list.front(): 12679
    target (0--32767):12345
    ::find(),milli-seconds: 3
    found,12345
    forward_list.sort(),milli-seconds: 1595

值得注意的是： std::forward_list 专为高效的前端插入和删除操作设计，std::forward_list 没有 push_back() 是因为它是单向链表， 只能高效地从前面操作。它没有 size() 函数，因为计算链表长度需要遍历整个链表，这与它优化前端操作的设计目标不符。

总结：

std::forward_list 是一个轻量级的容器，它在内存使用上比 std::list 更为高效，但在功能上也更为有限。它适合于那些只需要单向遍历和操作的场景。由于其单向链表的特性，std::forward_list 在进行元素插入和删除时，只能从链表的前端进行，这限制了它的使用场景。在选择 std::forward_list 时，需要根据应用的具体需求来权衡其优势和局限性。

链表容器-slist

slist容器与forward_list容器一样，只是slis容器存在于ext\slist头文件中。

测试代码：

    #include <forward_list>
    namespace t04
    {
        void test_forward_list(long& value)
        {
            cout << "\nforward_list()..............\n";
            forward_list<string> c;
            char buf[10];
            clock_t timeStart = clock();
            for (long i = 0; i < value; ++i)
            {
                try
                {
                    snprintf(buf, 10, "%d", rand());
                    c.push_front(string(buf));//将随机数转为string类型，并使用push_frond()将数据存入容器头部，forward_list没有push_back()
                }
                catch (exception& p)
                {
                    cout << "i=" << i << " " << p.what() << endl;
                    abort();//发生异常使用该函数退出程序
                }
            }
            cout << "milli-seconds: " << (clock() - timeStart) << endl;
            cout << "forward_list.max_size(): " << c.max_size() << endl;
            cout << "forward_list.front(): " << c.front() << endl;
            //cout << "forward_list.back(): " << c.back() << endl;	没有该函数
            //cout << "forward_list.size(): " << c.size() << endl;	没有该函数

            string target = get_a_target_string();//获取输入的数字，并转为string类型返回
            //使用算法find查找
            {
                timeStart = clock();
                auto pItem = ::find(c.begin(), c.end(), target);//返回类型是：使用全局::find()寻找目标，这是循环寻找
                cout << "::find(),milli-seconds: " << (clock() - timeStart) << endl;

                //判断有没有找到
                if (pItem != c.end()) {
                    cout << "found," << *pItem << endl;
                }
                else
                {
                    cout << "Not fount!" << endl;
                }
            }
            //测试排序花费的时间
            {
                timeStart = clock();
                c.sort();//使用forward_list自带的排序函数，当然也可以用全局的sort，一般如果容器自带，则选择自带的。
                cout << "forward_list.sort(),milli-seconds: " << (clock() - timeStart) << endl;
            }
        }
    }

    How much memory space you need: 1000000

    forward_list()..............
    milli-seconds: 965
    forward_list.max_size(): 384307168202282325
    forward_list.front(): 12679
    target (0--32767):12345
    ::find(),milli-seconds: 3
    found,12345
    forward_list.sort(),milli-seconds: 1595

双向容器-deque

std::deque（双端队列）是一种容器，它允许在序列的前端和后端快速插入和删除元素。尽管从概念图上看， std::deque 似乎是一个连续的存储空间，但实际上它并不是连续的。std::deque 的实现通常是由一个或多个固定大小的连续内存块 （通常称为“节点”或“块”）组成的，这些块通过指针连接在一起。

以下是对您提供内容的整理：

• 存储机制：std::deque 由多个指针组成，每个指针指向一个具有一定容量的连续内存块。这些内存块被组织在一起，形成一个能够从两端快速增长的容器。
• 内存管理：当 std::deque 中的一个内存块满了，需要更多的空间时，它会“自动跳转”到下一个空闲的内存块的开始位置。如果所有现有的内存块都已满，std::deque 会分配一个新的内存块，并更新指针以指向这个新的块。
• 内存效率：使用固定容量的内存块可以减少内存浪费。例如，如果每个内存块的大小为8个元素，那么即使只存储一个元素，也只会浪费7个元素的空间（因为第一个块始终被使用）。这与 std::vector 相比，后者可能会因为频繁的内存重新分配而导致更多的内存浪费。
• 动态增长：当 std::deque 需要更多内存时，它会动态地增加新的内存块。这种设计使得 std::deque 能够在不牺牲太多内存的情况下，提供快速的插入和删除操作。
• 连续性：尽管 std::deque 在内部不是完全连续的，但它提供了随机访问的能力，这意味着你可以像访问 std::vector 或数组一样，通过索引来访问 std::deque 中的任何元素。

总的来说，std::deque 是一个灵活且高效的容器，适用于需要在序列的两端进行频繁插入和删除操作的场景。它的设计既考虑了性能， 也考虑了内存使用效率。

测试代码：

    #include <deque>
    namespace t05
    {
        void test_deque(long& value)
        {
            cout << "\ntest_deque()..............\n";
            deque<string> c;
            char buf[10];
            clock_t timeStart = clock();
            for (long i = 0; i < value; ++i)
            {
                try
                {
                    snprintf(buf, 10, "%d", rand());
                    c.push_back(string(buf));//将随机数转为string类型，并使用push_back()将数据存入容器尾部
                }
                catch (exception& p)
                {
                    cout << "i=" << i << " " << p.what() << endl;
                    abort();//发生异常使用该函数退出程序
                }
            }
            cout << "milli-seconds: " << (clock() - timeStart) << endl;
            cout << "deque.max_size(): " << c.max_size() << endl;
            cout << "deque.front(): " << c.front() << endl;
            cout << "deque.back(): " << c.back() << endl;
            cout << "deque.size(): " << c.size() << endl;

            string target = get_a_target_string();//获取输入的数字，并转为string类型返回
            //使用算法find查找
            {
                timeStart = clock();
                auto pItem = ::find(c.begin(), c.end(), target);//返回类型是：使用全局::find()寻找目标，这是循环寻找
                cout << "::find(),milli-seconds: " << (clock() - timeStart) << endl;

                //判断有没有找到
                if (pItem != c.end()) {
                    cout << "found," << *pItem << endl;
                }
                else
                {
                    cout << "Not fount!" << endl;
                }
            }
            //测试排序花费的时间
            {
                timeStart = clock();
                sort(c.begin(), c.end());//使用全局的sort,deque没有自己的sort。
                cout << "deque.sort(),milli-seconds: " << (clock() - timeStart) << endl;
            }
        }
    }

    How much memory space you need: 1000000

    test_deque()..............
    milli-seconds: 1055
    deque.max_size(): 461168601842738790
    deque.front(): 41
    deque.back(): 12679
    deque.size(): 1000000
    target (0--32767):12345
    ::find(),milli-seconds: 4
    found,12345
    deque.sort(),milli-seconds: 3838

特殊容器-stack和queue

std::stack（栈）

定义：

std::stack 是一个遵循后进先出（LIFO，Last In First Out）原则的容器适配器。它只能在序列的一端（栈顶）进行添加（push）和移除（pop）操作。

主要操作：

• push()：在栈顶添加一个元素。
• pop()：移除栈顶元素。
• top()：返回栈顶元素的引用，不移除它。

特点：

• 只能单端操作，即只能在栈顶进行操作。
• 没有提供直接的迭代器支持，但提供了 top() 方法来访问栈顶元素。

std::queue（队列）

定义：

std::queue 是一个遵循先进先出（FIFO，First In First Out）原则的容器适配器。它只能在序列的一端（队尾）进行添加（push）操作，在另一端（队首）进行移除（pop）操作。

主要操作：

• push()：在队尾添加一个元素。
• pop()：移除队首元素。
• front()：返回队首元素的引用，不移除它。
• back()：返回队尾元素的引用，不移除它。

特点：

• 双端操作，即在队首进行移除操作，在队尾进行添加操作。
• 提供了迭代器支持，允许遍历队列中的所有元素。

与 std::deque 的不同.

• 操作限制：std::stack 和 std::queue 限制了操作的位置，而 std::deque 允许在两端自由操作。
• 迭代器支持：std::stack 不支持迭代器，std::queue 支持迭代器但只能访问队列中的元素，而 std::deque 提供了随机访问迭代器，可以高效地访问序列中的任何位置。
• 使用场景：如果你需要一个简单的后进先出或先进先出的数据结构，std::stack 或 std::queue 可能更适合。如果你需要一个能够在两端快速操作且支持随机访问的容器，std::deque 是更好的选择。

测试代码：

    #include <stack>
    namespace t06
    {
        void test_stack(long& value)
        {
            cout << "\ntest_stack()..............\n";
            stack <string> c;//stack又叫栈，特点是先进后出
            char buf[10];
            clock_t timeStart = clock();
            for (long i = 0; i < value; ++i)
            {
                try
                {
                    snprintf(buf, 10, "%d", rand());
                    c.push(string(buf));//将随机数转为string类型，并使用push()将数据压入容器
                }
                catch (exception& p)
                {
                    cout << "i=" << i << " " << p.what() << endl;
                    abort();//发生异常使用该函数退出程序
                }
            }
            cout << "milli-seconds: " << (clock() - timeStart) << endl;
            cout << "stack.size(): " << c.size() << endl;
            cout << "stack.top(): " << c.top() << endl;
            c.pop();
            cout << "stack.size(): " << c.size() << endl;
            cout << "stack.top(): " << c.top() << endl;

            //与前面的容器不同，stack不可以进行查找操作
        }
    }