默认初始化

默认初始化，变量没有指定初值，被赋予默认值，默认值由变量类型和变量位置决定。变量类型分为内置类型和类，变量位置有函数内部和任何函数之外。

内置类型

对于内置类型的变量，如果没有显式初始化，它的位置由定义的位置决定。函数内部的内置类型不会被初始化，定义于任何函数外部的内置类型被初始化为$0$。未初始化的变量的值是未定义的。

类

对于自定义的类型来说，每个类决定初始化对象的方式，而且是否允许不经过初始化就定义对象也由自己决定。如果类允许这种行为，由类决定对象的初始值是什么；如果类要求每个对象显示初始化，在创建类对象没有进行明确的初始化操作时，会引发错误。

列表初始化

1. 用花括号初始化变量。
2. 无论是初始化对象或者为对象赋值，都可以使用花括号括起来的值。
3. 对于内置类型来说，如果使用列表初始化，并且初始值存在丢失的风险的时候，编译器会报错。
4. 可以用多个初值初始化vector

拷贝初始化和直接初始化

使用等号进行初始化的过程叫做拷贝初始化，否则是直接初始化。
拷贝初始化和直接初始化的区别在在于：
拷贝初始化使用的拷贝构造函数，拷贝一个对象到一个新创建的对象。拷贝初始化只能提供一个初始值，因为拷贝构造函数的参数就只有一个参数。。。
直接初始化使用的是函数匹配，选择最合适的构造函数，创建一个对象。

值初始化

1. 只提供给vector对象容纳的元素数量而不用略去初始值。会创建一个值初始化的元素初值，并把它赋给容器中所有元素，这个初始值由vector对象中元素类型决定。
2. 如果vector对象中元素类型是内置类型，如int，初始值自动设置为0。
3. 如果是某种类类型，比如string，由类默认初始化。
4. 有些类要求必须显式的给出初始值。如果vector中对象不支持默认初始化，必须提供初始值。
5. 如果值提供了元素的数量而没有设定初值，只能使用直接初始化。
6. 初始化的真实含义依赖于传递初始值时用的是花括号还是圆括号。花括号进行列表初始化，圆括号提供的信息构造vecotr对象。如果使用花括号中的形式，但是提供的值不能用来列表初始化，考虑使用值构造vector对象。但是如果使用圆括号提供不能构造vector对象的值，不能用来进行列表初始化。也就是说花括号可以用来列表初始化，也可以用来构建vector对象，但是圆括号只能用来构建vector对象。

特例

1. 使用拷贝初始化时（使用=），只能提供一个初始值。
2. 如果提供的是一个类内初始值，只能使用拷贝初始化或者花括号的形式初始化。
3. 如果提供的是初始值元素的列表，只能把初始值都放在花括号里，而不能使用圆括号。

40页2.2.1节
默认初始化
内置类型由变量的类型和位置决定
类类型各自决定器初始化对象的方式

76页3.2.1节
直接初始化和拷贝初始化

88页3.3.1节
vector的列表初始化

值初始化：
内置类型，元素自动设置为0
类类型，元素由类默认初始化

300页9.2.4节
容器的列表初始化

441页13.1.1节，拷贝初始化

参考文献

1.《C++ Primer第五版》
默认初始化：
C++ Primer第五版第40页
列表初始化：
C++ Primer第五版第39页
拷贝初始化：
C++ Primer第五版第76页
值初始化：
C++ Primer第五版第91页
2.https://stackoverflow.com/questions/13461027/why-does-the-standard-differentiate-between-direct-list-initialization-and-copy
3.https://stackoverflow.com/questions/18222926/why-is-list-initialization-using-curly-braces-better-than-the-alternatives
4.https://en.cppreference.com/w/cpp/language/list_initialization
5.https://en.cppreference.com/w/cpp/utility/initializer_list

C++中基本类型包括算术类型和空类型。这一节主要介绍算术类型，然后介绍了字面值常量的相关内容。

算术类型

算术类型有两类：整形和浮点型。算术类型的大小在不同的机器上实现也可能不同。
整形包括字符，布尔型，整形，长整形。
浮点类型有单精度，双精度和扩展精度浮点数，具体怎么表示可以查看IEEE 754标准。
一般情况下，char占用$1$字节，int占用$4$字节，long占用$8$字节，long long占用$8$个字节。float占用$4$字节，double占用$8$字节。
除了布尔型和扩展的字符型（wchar_t, char16_t, char32_t)之外，其他整形可以划分为无符号和带符号的两种，无符号类型中所有的比特位都用来存储值，而有符号类型需要使用其中的某些位存储符号。int,long, long long默认是带符号的。char可以分为三种，char, signed char, unsigned char，char不一定是有符号的，由不同的编译器来决定。

其他注意事项：

1. 算术表达式中不要使用char，因为不同的编译器对char的处理方式可能不同，一些把char当做有符号的，一些把char当做无符号的，在不同机器之间进行迁移时可能会出现问题。
2. 浮点数运算用double，float精度不够，而且计算代价和double差不多。

类型转换

在程序的某处使用一种类型而其实对象应该使用另外一种类型时，程序会自动进行类型转换。关于类型转换的更多内容可以查看C++ type conversions。

1. 在将有符号数转化为无符号数的时候，如果这个有符号数是负数，那么会做一个模运算，将它转换为正值。
2. 无符号数永远不可能为负。
3. 如果一个运算同时有有符号数和无符号数参与运算，那么会将有符号数转换为无符号数进行运算。如下示例：

1
2
3
4
5
6
7
8

int a = -3;
unsigned int b = 0;
b--;
std::cout << b << std::endl;
//output: 4294967295
b = a;
std::cout << b << std::endl;
//output: 4294967293

字面值常量

字面值(literal)是字面值常量的缩写，它的值是一看就知道的量，并且不允许改变。每一个字面值常量都对应一种数据类型，可以是整形，浮点型，字符，字符串，转义序列，布尔和指针等，数据类型由它的形式和值决定。可以通过前缀或者后缀显式的指定字面值的类型，字符和字符串的字面值类型通过前缀指定，整形和浮点型的字面值类型通过后缀指定。
前缀

• u，表示unicode 16字符
• U，表示unicode 32字符
• L，表示宽字符
• u8，utf-8，只用于字符串字面值常量

后缀，这里给出的最小匹配类型，如果不够的话，会自动选择更大的。

• u,U，unsigned
• l, L, long
• ll, LL, long long
• f, F, float
• l, L, long double

整形字面值常量

如12,1345等。
十进制的字面值常量是带符号数，比如12是int, long, long long中能容纳下的占用最小字节的类型；八进制和十六进制的字面值常量是能容纳其数值的int, long, long long, unsigned int, unsigned long, unsigned long中的最小类型。

浮点型字面值常量

浮点型的字面值常量是double。

字符和字符串字面值常量

'a'是字面值字符常量，"hello world"是字符串字面值常量。

转义序列

包含不可打印和可打印的字符。\n,\r,\t,\b,\a等。

布尔字面值

true, false是bool变量的字面值。

指针字面值

nullptr是指针字面值。

参考文献

1.《C++ Primer第五版》
2.https://www.cnblogs.com/yc_sunniwell/archive/2010/06/18/1760034.html

第一章

• 变量，具有名字的对象
• 缓冲区，一个存储区域，用于保存数据。IO设施通常将输入输出数据保存在一个缓冲区中。
• 文件结束符(end of file, EOF)，文件结束标志，通常是-1。
• 初始化，对象创建的时候给它一个初始值。
• 未初始化的变量，没有给定初始值的变量，类类型的变量如果没有指定初值，按类定义指定的方式进行初始化。函数内部的内置类型变量默认是不初始化的，需要进行显式的初始化。

第二章

• 无法预知的行为，编译器无须或者不能检测的错误。即使代码编译通过了，如果程序执行了一条未定义的表达式，仍有可能产生错误，而且这是很有可能的。

• 字面值常量：12, 024, 0x3,true, 3.141, nullptr,A都是字面值常量，他们分别属于int,int,int, bool, double, 指针，char等类型。可以通过前缀或者后缀显式的指定字面值的类型，字符和字符串的字面值类型通过前缀指定，整形和浮点型的字面值类型通过后缀指定。

• 字面值类型：算术类型，引用和指针都属于字面值类型，string，IO库和类不属于字面值类型。算术类型包含整形和浮点型，整形中又包含字符和int,long等。constexpr只能用于字面值类型。

• 在将有符号数转化为无符号数的时候，如果这个有符号数是负数，那么会做一个模运算，将它转换为正值。

• 有符号数永远不可能为负。

• 不要混用无符号类型和有符号类型，因为有符号数会被转化成有符号数进行运算。

  1 2 3 4 5 6 7 8 9 10 11

  int a = -3; unsigned int b = 0; b --; std::cout << b << std::endl; b = a; std::cout << b << std::endl; b = 3; std::cout << a* b << std::endl;

• 不要用char进行算术运算，因为不同的平台实现可能不同，有的是无符号的，有的是有符号的。

• 常见的未定义行为：

1. 1 2	int i = 1; i = i++;

2. 给带符号数一个超出它表示范围的值。

• 默认初始化，变量没有指定初值，被赋予默认值。默认值由变量类型和变量位置决定。
  对于内置类型的变量，如果没有显式初始化，它的位置由定义的位置决定。函数内部的内置类型不会被初始化，定义于任何函数外部的内置类型被初始化为$0$。未初始化的变量的值是未定义的。
  对于自定义的类型来说，每个类决定初始化对象的方式，而且是否允许不经过初始化就定义对象也由自己决定。如果类允许这种行为，由类决定对象的初始值是什么；如果类要求每个对象显示初始化，在创建类对象没有进行明确的初始化操作时，会引发错误。

• 未初始化变量。

• 声明和定义的区别和联系。

• 在函数体内部不能初始化由extern关键字标记的变量。

• 静态类型，在编译阶段检查类型。

• 类型修饰符：*和&，它是声明符的一部分，const也是类型修饰符。

• 声明符：变量名或者变量名前面加上类型修饰符，即*d和&d，其中d是变量名。

• 复合类型：基于其他类型定义的类型，引用和指针都是复合类型。

• 引用就是别名，不能更改，必须初始化。

• 指针存放的是某个对象的地址，要想获取变量的地址，使用&符号获取变量的地址。

• 建议初始化所有指针。如果指针未经初始化，该指针变量中存放的值被当做一个地址，访问该指针，相当于访问一个本不存在的变量，如果这个地址中的内容被我们拿到了，我们可能就不知道这个值是合法还是非法的。建议初始化所有的指针，不知道指针应该指向什么的话，就让指针指向nullptr或者0。

• 复杂的指针或者引用的声明语句，从右往左读。

• 常量引用是对const的引用的简称。严格来说，并不存在常量引用，因为引用不是一个对象，我们没办法让引用本身恒定不变。但是因为C++中，引用绑定的对象是不能更改的，所以从这层意义上理解，所有的引用又都称得上常量。引用的对象是常量还是非常量决定了引用能进行的操作，但是影响不到引用和对象的绑定关系。

• 指向常量的指针和对常量的引用（常量引用），可以使用非常量对象初始化指向常量的指针和常量引用，不论指向或者引用的是不是常量对象，都不能通过指针或者引用修改他们引用或者指向的对象的值。因为他们认为自己指向或者引用了常量，而常量是不能修改的，所以就不能修改了。

• 常量指针即指针本身是一个常量。它的指向不能改变，但是它指向变量的值是可以改变的。

  1 2 3 4

  int val =3; const int &cr = val; // 对常量的引用，引用的变量不能通过cr引用改变。 cont int *ptr = &val; // 指向常量的指针，指针指向的变量不能通过ptr指针改变。 int *const p = &val; //常量指针，指针的指向不能变，指针指向变量的值可以改变。

• 顶层const，变量本身是一个常量。

• 底层cosnt，针对于复合类型如指针和引用来说的，引用的对象是一个常量（常量引用）或者指针指向的是一个常量。

• 顶层const和底层const
  对常量的引用（常量引用）可以和常量对量绑定；
  对常量的引用（常量引用）可以和非常量对量绑定；
  非常量引用不可以和常量对象绑定；
  非常量引用可以和非常量对象绑定；
  指向常量的指针可以指向常量对象；
  指向常量的指针可以指向非常量对象；
  常量指针可以指向非常量对象；
  常量指针不可以指向常量对象；
  普通指针不可以指向常量对象；
  普通指针可以指向非常量对象；
  常量指针（顶层const）可以用来初始化非常量对象。
  对常量的引用和指向常量的指针（底层const）不可以用来初始化非常量对象。

• 常量表达式，值不会改变并且在编译时值就已经确定的表达式。

• constexpr`用于声明常量表达式，常量表达式一定是常量，但是常量不一定是常量表达式。比如：

  1	const int sz = get_size() //sz是常量，但是不是常量表达式

• auto会忽略顶层const，保留底层const。

• auto也会忽略引用。

• 设置类型为auto的引用，可以保留顶层const

• decltype的结果可以是引用，引用从来都是作为它所指对象的同义词出现，只有在decltype处是例外。

• 如果表达式的内容是解引用操作，使用decltype将会得到引用类型。

• decltype((variable))的结果永远是引用，而decltype(variable)的结果只有在真的是引用的时候才会返回引用。

第三章

1. cin和getline的区别，对于空白符的处理
2. string的初始化方式，默认初始化，拷贝初始化，直接初始化
3. range for语句逐字符操作。

第七章

• 构造函数。每个类都会定义它的对象被初始化的方式，类通过一个或者几个特殊的成员函数控制每个类的初始化过程,这些函数叫做构造函数。
• 前向声明。仅仅声明类而暂时不定义它，这种声明有时候也叫前向声明。
• 不完全类型。在类声明之后定义之前，这个类属于不完全类型。我们知道它是一个类，但是不清楚它到底包含哪些类型。

参考文献

1.《C++ Prime第五版》

I/O类

标准库提供了三类IO操作，它们分别是读写流的iostream，读写文件的fstream，读写内存中string的sstream。如下表所示：

ifstream和istringstrem都继承自istream，ofstream和ostringstream都继承自ostream。像使用cin和cout那样使用它们就行。

IO对象的特性

1. 不能拷贝或者对IO对象赋值。所以不能将形参和返回类型设置为流类型，必须将它们设置为流引用类型。
2. 读写一个IO对象会改变它的状态，因此传递和返回的引用不能是const的。

IO流的状态

IO操作很容易出错，一些错误是可恢复的，另一些是不可恢复的。下面是IO类中定义的函数和表示，可以帮助我们访问和操纵流的状态。

strm::iostate中存放了当前IO流的状态，这个类型是一个位集合，IO类定义了四个iostate类型的常量表达式表达特定的位类型，可以使用位运算与设置或者检测多个标志位：

• strm::badbit，表示系统级的错误
• strm::failbit，可恢复错误（到达文件结束也会置位strm::failbit，发生系统级错误时也会被置位）
• strm::eofbit，到达文件结束
• strm::goodbit，流处于未出错状态

它们用来表示流的状态，可以用good(), fail()，eof(), bad()分别查询对应标志位的状态。我们将流当做条件使用的代码其实就是使用的是状态位的状态。
可以使用rdstate函数获得当前流的状态，使用setstate对给定条件位置位，使用clear可以清除所错误标志位，也可以清除指定错误标志位。

管理缓冲区

关于缓冲区的内容，简单来说，缓冲区的作用就是减少系统级IO，提高读写效率。具体介绍可以查看。
这里介绍一下导致C++中缓冲区刷新的原因：

1. 程序结束，作为main函数return的一部分，冲洗缓冲区
2. 缓冲区满时，冲洗缓冲区
3. 使用操作符endl，会在输出内容的末尾加一个'\n'，然后刷新缓冲区；使用flush刷新缓冲区，不附加任何字符；使用ends在输出内容的末尾加一个空字节，并不会刷新缓冲区（C++ Primer第五版上写错了）。
4. 使用cout << unitbuf设置为每次输出操作后都刷新缓冲区（即使不适用endl等操作符），即无缓冲，使用cout << nounitbuf恢复。
5. 一个输出流可能关联到另一个流，当读写关联的流时，关联到的流的缓冲区都会被刷新。

iostream

C++标准IO库iostream提供了输入流istream和输出流ostream，一个流就是一个字符序列，从IO设备中读出或者写入IO设备。

标准输入输出对象

• cin，标准输入
• cout，标准输出
• cerr，标准错误
• clog，用来输出一些普通信息。

通常系统会将程序所运行的窗口和标准IO对象关联起来，读取cin，从当前程序关联的窗口进行读取，向cout,cerr和clog写入数据时，会写到同一个窗口中，可对它们进行重定向。

输入输出运算符

• <<输出运算符，接收两个运算符，左侧需要是ostream对象，右侧需要是要打印的对象。返回左侧运算对象，即写入给定值的ostream对象。
• >>输入运算符，接收两个运算符，左侧需要是istream对象，右侧从istream中读入的数据要写入的对象。返回左侧运算对象，即给定的istream对象。

一直有个问题就是为什么<<是输出，>>是输入，可以简单的把箭头方向当做数据流向，输出的数据流向ostream中的标准输出cin，输入时，数据从istream的标准输入cin流向变量。

操纵符

endl是一种操纵符。当把它写入到ostream的时候，有两个作用：

1. 结束当前行
2. 将与当前输出设备相关的缓冲区中的内容刷新到输出设备中。这个刷新操作可以保证目前为止程序的所有输出都真正写入输出流而不是在内存中的等待写入输出流。

命名空间

命名空间可以解决名自定义冲突问题。比如有两个不同的库中实现了一个同名的函数，可以通过加上命名空间进行区分。cin,cout和endl都定义在std命名空间中。在访问时需要使用以下方式：std::cin，std::cout，std::endl。
C++标准库定义的名字在都在std中。

读取任意的输入数据

下面的示例代码对任意的输入数据进行求和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include<iostream>

using std::cin;
using std::endl;
using std::cout;

int main()
{
    int sum = 0, value = 0;
    while(std::cin >> value)
    {
        sum += value;
    }

    std::cout << "Sum is: " << sum << std::endl;

    return 0;
}

fstream

头文件fstream定义了三个类型支持文件IO：

• ifstream从一个给定的文件读取数据；
• ofstream向一个给定的文件写入数据；
• fstream读写给定文件。

这些类型和我们之前使用的cin和cout一样，可以使用getline从一个ifstream中读取数据。fstream具有以下的一些特殊操作：

这些操作只有fstream,ofstream和ifstream对象能调用，其他类型不行。

使用fstream,ifstream和ofstream

我们想要读文件的时候，可以定义一个fstream对象，然后将这个对象和文件关联起来，每个fstream类都定义了一个名字为open的成员函数，它完成了一些系统相关的操作，定位给定的文件，打开为读或写模式。
在创建fstream对象时，我们可以提供一个文件名，此时open函数会被自动调用。如果定义了一个空fstream对象，可以手动调用open将它和一个文件关联起来。调用open可能失败，进行open是否成功的检测通常是一个好习惯。
close函数可以关闭fstream当前关联的文件，当一个fstream对象被销毁时，会自动调用close函数。

1
2
3
4
5
6

// 1.构造一个ifstream并打开给定文件，文件名可以是string，也可以是C风格字符串
ifstream in(ifile);

// 2.输出文件流并未关联到任何文件。
ofstream out;
out.open(ifile+".out");

可以使用fstream代替iostream，因为fstream是iostream的子类。

file mode

C++ 中的file mode如下所示：

具体的使用可以等用到的时候查资料。

sstream

头文件sstream定义了三个类型支持内存IO：

• istringstream从string读取数据；
• ostringfstream向string写入数据；
• stringstream读写string。

stringstream特有的操作如下：

使用istringstream和使用ostringstream

最好的就是写一个例子。

参考文献

1.《C++ Primer第五版》

char arr[]（字符数组，C类型字符串）

1. C语言中的字符串的概念：以NULL字节结尾的零个或者多个字符。而字符数组可以不以'\0'结束，而且不能为空。
2. 字符串通常存在字符数组中，这也是C语言中没有显式的字符串类型的原因。
3. 因为字符串以NULL结束，所以字符串内部不能有NULL字节。
4. 为什么选择NULL作为字符串的终止符，因为它不是一个可打印的字符。

如下所示，是char str[]，即字符数组的定义。str是局部变量，存放在栈里面。

1
2
3

char str1[] = "hello";
char str2[] = {'h', 'e', 'l', 'l', 'o', '\0'};
char str3[] = {'h', 'e', 'l', 'l', 'o'};

char*（字符指针）

1. char*是一个指针，指向一个char，理论上来说，它并不是一个数组。
2. char *ptr;并不为它指向的内容分配内存，而是只分配一个char *大小的内存存放指针变量ptr。
3. char arr[10];是一个数组，不是一个指针，char *和char[10]不是一个类型。

如下所示：

1
2
3
4
5
6
7

char str[] = "hello world";
char *ps = str;
// char *类型的指针ps指向一个字符数组。

char c = 'x';
char *pc = &c;
// char *类型的指针pc指向一个字符。

char**（指向字符指针的指针）

char**是一个指针，指向一个指向char的指针，它可以指向一个指针数组。如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include "stdio.h"
#include "stdlib.h"


int main() {

    char *arr[] =  {
        "hello",
        "world",
        "hi"
    };  

    // arr是一个数组，数组的元素是`char*`类型。
    // 数组名可以看成指向数组首元素的指针。
    char **p = arr;

    printf("%s\n", *p);
    printf("%s\n", *(p+1));

    printf("%c\n", *(*(p+1)+2));

}

p是char**类型的元素，即指向char*类型的指针，p+1获取下一个指向char*的指针；*p是char*类型的元素，即指向char类型的指针，指向第一个字符串的第一个字符，*(p+1)指向第二个字符串的第二个字符；**p是char类型的元素，是第一个字符串的第一个字符，*(*(p+1)+2)指向第二个字符串的第三个字符。
事实上，这个p和arr的作用是一样的。注：关于指针运算可以查看复合类型－指针。

怎么理解？如下图所示：

std::string

字符串字面值和string是不同的类型，字符串字面值是为了和C语言兼容，它不是标准库中string对象的内容。

字符串字面值常量

字符串字面值常量是用一对双引号包围一串字符。如"hello", "hi\n", ""等，'a'是字面值字符常量。
程序在使用字符串常量时，编译器会将字符串常量存放在数据区的常量区。当一个字符串常量出现在在一个表达式中，表达式使用的值是字符串常量在内存中的地址，而不是这些字符串常量本身。可以把字符串赋值给“指向字符的指针”，即让指针指向字符串常量在内存中的地址。但是不能把字符串常量赋值给一个字符数组，即不能把字符串常量的地址赋值给字符数组。比如

1

char *message1 = "Hello world!";

这个代码是将字符串常量中第一个字符的地址传递给message。

字符数组和字面值常量的区别

1
2

char message1[] = "Hello world!;
char *message2 = "Hello world!";

第一种方式，其实是一种约定，它等于char message1[] = {'H', 'e', 'l', 'l', 'o', 'w', 'o', 'r', 'l', 'd', '\0'};。
而第二种方式中，"Hello world"是一个字面值常量，它在内存中只能以数组的形式存在，是一个不可修改的左值表达式。而message2实际上指向了这个字符串数组的首字符。

常见的指针数组

1. main函数的形参char *argv[]就是一个指针数组
2. getline的第一个参数是char **lineptr。

参考文献

1.《C++ Primer第五版》
2.https://www.zhihu.com/question/307261590/answer/563448215
3.https://www.zhihu.com/question/307261590/answer/563630017
4.https://stackoverflow.com/questions/10004511/why-are-string-literals-l-value-while-all-other-literals-are-r-value

malloc

C标准malloc定义

malloc定义在头文件<stdlib.h>中

Allocates size bytes of uninitialized storage.
If allocation succeeds, returns a pointer to the lowest (first) byte in the allocated memory block that is suitably aligned for any object type with fundamental alignment.
If size is zero, the behavior is implementation defined (null pointer may be returned, or some non-null pointer may be returned that may not be used to access storage, but has to be passed to free).

malloc is thread-safe: it behaves as though only accessing the memory locations visible through its argument, and not any static storage.
A previous call to free or realloc that deallocates a region of memory synchronizes-with a call to malloc that allocates the same or a part of the same region of memory. This synchronization occurs after any access to the memory by the deallocating function and before any access to the memory by malloc. There is a single total order of all allocation and deallocation functions operating on each particular region of memory. (since C11)

malloc, calloc和realloc原型

1
2
3
4
5
6

#include <stdlib.h>

void *malloc(size_t size);
void *calloc(size_t nmemb, size_t size);
void *realloc(void *ptr, size_t size);
void *reallocarray(void *ptr, size_t nmemb, size_t size);

malloc, calloc和realloc性质

0. malloc函数的实现中（C标准没有规定），在分配空间的时候，通常分配的空间要比申请的要大一些，这些额外的空间用来记录malloc这片空间的大小，在使用free的时候会用到。
1. malloc，分配指定字节的内存空间，初始值不定。
2. calloc，为指定长度的固定数量的对象分配空间，每一个bit都被初始化为0。
3. realloc，增加或者减少已经分配的内存空间的大小。当这个大小增加时，可能需要将之前分配的空间中的数据移到另一个足够大的区域以便于增加大小，新增加的区域内的值是不确定的。
4. 这三个函数返回的指针一定是对齐的，保证它可以用于任何对象。比如double的要求最严格，需要从8的倍数的地址单元开始，这三个函数返回的地址一定满足这个要求。
5. 它们的返回类型都是void*，需要使用强制类型转换。
6. realloc函数可以增加或者减少之前分配的内存空间的大小。比如分配了一个固定大小的数组，后来发小它不够用了，可以使用realloc对它进行扩充，如果原有的存储后有足够的大小进行扩充，则可以在原存储区的位置上向高地址进行扩充，无需移动原有数组，返回和传入相同的指针。如果原来的内存空间后没有足够的空间，就重新分配一个足够大的内存空间，再将原有数据的内容复制过去，然后释放原来的内存空间，返回新的指针。
7. realloc传入的参数是存储区的新长度。如果传入的ptr参数是NULL指针，那就退化成了malloc。

自己实现一个malloc

???

free

C标准free定义

free定义在头文件<stdlib.h>中

Deallocates the space previously allocated by malloc(), calloc(), aligned_alloc, (since C11) or realloc().
If ptr is a null pointer, the function does nothing.
The behavior is undefined if the value of ptr does not equal a value returned earlier by malloc(), calloc(), realloc(), or aligned_alloc() (since C11).
The behavior is undefined if the memory area referred to by ptr has already been deallocated, that is, free() or realloc() has already been called with ptr as the argument and no calls to malloc(), calloc() or realloc() resulted in a pointer equal to ptr afterwards.
The behavior is undefined if after free() returns, an access is made through the pointer ptr (unless another allocation function happened to result in a pointer value equal to ptr)
free is thread-safe: it behaves as though only accessing the memory locations visible through its argument, and not any static storage.

A call to free that deallocates a region of memory synchronizes-with a call to any subsequent allocation function that allocates the same or a part of the same region of memory. This synchronization occurs after any access to the memory by the deallocating function and before any access to the memory by the allocation function. There is a single total order of all allocation and deallocation functions operating on each particular region of memory. (since C11)

free原型

1
2
3

#include <stdlib.h>

void free(void *ptr);

free属性

从标准的定义可以看出来，以下都是未定义的行为：

1. free的对象不是alloc函数族的返回值；比如

   1 2 3 4

   int *pi = (int*)malloc(10 * sizeof(int)); pi++; //下面就是错误的，因为这个`pi`不是`alloc`函数族的返回值。 free(pi);

2. free一个已经被释放过了的块；

3. 访问一个free已经释放了的块。
   等等。为什么？？？因为标准并没有定义malloc应该怎么实现，有的内存分配器，malloc实际申请的内存要比传入的参数大，里面存放了额外的数据记录这块内存有多大，一般就是存在指针左边。free的时候，就会读取那个内存块中存放的信息，进行free，所以上面的那些都是未定义的行为。

其他属性

1. free可以释放ptr指向的内存空间，释放的空间通常送入可用内存池，之后可以通过这三个函数重新分配。
2. malloc和free底层通常使用sbrk系统调用实现，这个系统调用扩充或者减小进程的堆，虽然sbrk可以扩充或者缩小进程的堆，但是一般malloc和free的实现不会减少进程的内存空间，释放的内存空间保存在malloc池中，而不是交给内核。
3. 大多数实现分配的空间要比请求的空间大一些，因为需要存储一些管理信息，如block的大小，指向下一个block的指针等等。因此，如果对超过一个分配区域的内存进行读写的话，会造成很严重的错误。
4. free一个已经释放了的块，free的不是alloc函数的返回值，没有进行free等等，都是未定义的结果。为什么？？？

new

对于自定义类型而言，new操作符首先调用operator new()函数申请内存，其内部调用的是malloc函数，返回一个void*类型的指针；new还会负责把它转换成自定义对象的指针；然后调用类的构造函数初始化对象；最后返回自定义对象的指针。malloc只负责内存的分配而不会调用类的构造函数数。举个例子：

1
2
3
4
5
6
7
8

Complex *pc = new Complex(1, 2);
//等价于
// 1.内部调用malloc
void *mem = operator new(sizeof(Complex));
// 2.将void *类型指针转换为Complex*类型的
pc = static_cast<Complex*> (mem);
// 3.调用Complex的构造函数
pc->Complex::Complex(1, 2);

1. 默认初始化。new后面加类型，没有小括号，也没有花括号。
   默认情况下，new分配的对象，不管是单个分配的还是数组中的，都是默认初始化的。这意味着内置类型或组合类型的对象的值是无定义的，而类类型对象将用默认构造函数进行初始化。
2. 值初始化。类型名字后加()即可，对于内置类型的变量，初始化为0，对于类类型的变量，调用默认构造函数。
3. 直接初始化。使用初始化列表加对象值，或者小括号加对象值。

对于自定义类型而言，只要一调用new，无论后面有没有加()，那么编译器不仅仅给它分配内存，还调用它的默认构造函数初始化。

delete

1. delete是和new配对的操作。调用delete操作，编译器实际上会将它转换为两步操作，第一步是调用析构函数；第二部调用opereator delete()，其内部调用了free。
2. 数组的new一定要和数组的delete配对，否则就会出现内存泄露。第一条中说了delete分为两步，第一步其实不会造成内存泄露；而是第二步中，析构函数被调用的次数，delete p只会调用一次析构函数，而delete[] p会调用多次析构函数，调用次数和new时申请的数组大小一样。

malloc vs new

1. malloc是C语言中的函数，而new是C++的操作符；
2. malloc返回的是void*类型的指针，需要我们手动进行强制类型转换转换成我们需要的类型，而new返回的是对象类型的指针，类型和对象严格匹配，new是类型安全型操作符。
3. 在分配内存失败时，malloc会返回NULL，而new会throw on failure。
4. malloc需要指定申请的内存占多少个字节，而new不需要指定申请内存块的大小，编译器会根据类型计算需要的内存大小；
5. malloc和new都是申请heap上的内存；
6. new操作符调用的operator new()函数可以重载（操作符new不能重载），而malloc不能重载。
7. malloc和free，new和delete必须配套使用。

几个问题：

1. 什么时候malloc和new会申请内存失败。
2. new操作符的两个步骤，一个是申请内存，一个是调用构造函数，new的申请内存和malloc的申请内存有什么区别。

参考文献

1.《C++ Primer第五版》
2.https://stackoverflow.com/questions/184537/in-what-cases-do-i-use-malloc-and-or-new
3.https://zhuanlan.zhihu.com/p/47089696?utm_source=wechat_session&utm_medium=social&utm_oi=687606928481730560

map vs hash_map(unordered_map)

• 数据结构，
  map使用平衡二叉树，通常是红黑树；hash_map使用哈希函表。
• 查找时间
  map是$O(\log n)$；hash_map是$O(1)$（没有冲突的情况下），最坏情况下是$O(n)$。

C++中的hash_map叫做unordered_map。

参考文献

1.https://stackoverflow.com/questions/2189189/map-vs-hash-map-in-c/2189206
2.https://stackoverflow.com/questions/5139859/what-the-difference-between-map-and-hashmap-in-stl/5139888

Gram-Schmidi正交化

这一章属于正交的内容，但是因为很重要，就单独拎出来再说一遍。
Gram-Schmidt正交化过程就相当于是在不断的进行投影，这个方法的想法是从$n$个独立的column vector出发，构建$n$个正交向量，然后再单位化。拿$3$个过程举个例子。用$a,b,c$表示初始的$3$个独立向量，$A,B,C$表示三个正交向量，$q_1, q_2,q_3$表示三个正交单位向量。
第一个正交向量，直接对第一个向量单位化
$$A=a, q_1 = \frac{A}{\vert A\vert}$$
第二个正交向量，将第二个向量投影到第一个向量上，计算出一个和第二个向量正交的向量。
$$B=b-\frac{A^T B}{A^T A}A , q_2 = \frac{B}{\vert B\vert}$$
第三个正交向量，将第三个向量分别投影到第一个和第二个正交向量上，计算处第三个正交向量。
$$C=c - \frac{A^T C}{A^T A}A - \frac{B^T C}{B^T B}B , q_2 = \frac{C}{\vert C\vert}$$

参考文献

1.MIT线性代数公开课

矩阵分解

LU分解

PLU分解

QR分解

代码

参考文献

1.http://www.math.iit.edu/~fass/477577_Chapter_7.pdf
2.https://www.sciencedirect.com/science/article/pii/S0377042706001403