======数组、Vector 与字符串======
//第 3 章笔记//
----
====数组====
===Intro===
  * 数组是一种类型，由多个相同对象组成的序列
==定义数组==
  * 数组的类型与包含的对象类型不同：数组的类型由对象的**类型**和自身的**长度**组成
<code cpp>
int a; //int
int b[10]; // int[10]
</code>
  * 数组的长度必须是**常量表达式**
    * 长度需要大于 0（负数是不行的，）
    * 长度需要能转换为 ''size_t''（converted expression，比如浮点就不行）
<code cpp>
int x;
std::cin >> x;
//不合法
//类型由编译器决定，但长度要在运行期才能得到
//编译器无法推断出b[x] 的类型
int b[x];
//合法
constexpr short y = 3;
int c[y];
</code>
<WRAP center round box 100%>
  * C++ 标准不支持运行期数组长度；但在编译器实现中, gcc 和 clang 都可以通过去掉 ''--pedantic-errors'' tag 来支持 variable length array。但这样做是有风险的，因为该功能是 complier denpend。除此之外，某些必须在编译器完成的功能也不能使用该类类型做为参数，比如 ''decltype(b)''
</WRAP>
==数组的初始化==
  * 默认初始化：元素都会按照默认的方式来创建（根据C++ 的方式）
  * 聚合初始化
    * 编译器可以自行推断数组长度
    * 给出的元素不足，剩余元素会进行默认初始化
<code cpp>
int b[3]; //default int
int c[3] = {1, 2, 3}; // int[3], aggregate init
int cn[] = {1,2, 3}; //int[3]
int d[3] = {1,2} // partially aggregate init, 1,2,0
</code>
  * 不能使用 ''auto''：auto 会将 ''{}'' 视作 initialization_list
  * 不能复制数组：
    * 初始化不能通过赋值构造
    * 拷贝赋值的结果是拷贝的指向数组首元素的指针
<WRAP center round box 100%>
  * 数组作为右值会退化为指针。
  * 使用指针访问数组性能更好
</WRAP>
==字符串数组的特殊性==
<code cpp>
//char[6] 简化定义写法，会自动添加 ''\0'' 表示结束
char str[] = "hello";
//char[5] 完整定义写法，但不会为末尾添加 ''\0''
char str[] = {‘h’, 'e', 'l', 'l', '0'};
</code>
===数组的复杂声明===
  * 指针为元素的数组
<code cpp>
//a[3] 是有3个元素为指针的数组
int* a[3];
</code>
  * 指向数组的指针
<code cpp>
//注意括号
//a 是指针，指向 int[3]
int (*a) [3];
</code>
  * 数组的引用
<code cpp>
//a 是引用，指向 int[3]
int b[3];
int (&a) [3] = b;
</code>
<WRAP center round box 100%>
引用不支持聚合初始化。C++ 中不支持元素为引用的数组。从概念上来说，引用不是对象。数组要求元素使对象，因此没有元素为引用的数组。
</WRAP>
===数组中的元素访问===
  * 数组中的第一个元素下标为 0
  * 通过下标操作符访问：''a[0]''
==数组访问的细节==
  * C++ 中，左值的含义被修改为了 //locator value//，也就是带地址信息的值（而不是按等号的左右来决定）。
    * 数组是左值，但不能放在等号左边
    * 在等号右部使用（作为右值）时，数组的类型会隐式转换为指向**数组头元素**的指针。也就是说，指针也可以使用 ''[]'' 操作符
    * 当使用 ''x[y]''，且 ''x'', ''y'' 都是 Built-in 类型时，''x[y]'' 被解析为 ''*(x+y)''，也就是转换为指针，再解引用。
    * 需要注意下标越界

<code cpp>
int a[3] = {1,2,3};
auto b = a;
//int(&)
decltype(b)
//int*
a;
//int*
b;
//int, *(b+0)
b[0]
</code>
<WRAP center round tip 100%>

可以使用 decltype 来判断表达式是否是左值。
</WRAP>
====数组和指针====
===数组到指针的隐式转换===
  * 使用数组的时候通常数组会被转化为指针
    * 会丢失一部分信息（比如长度，编译器无法检查，这也是下标越界的原因）
<code cpp>
// decay, b 是 int* 类型
int a[3];
auto b = a;
//不会 decay 的范例
//decltype 返回的是数组的类型
// int[3]
decltype(a);
// int size * 3
sizeof(a);
</code>
  * 可以通过声明避免隐式转换
<code cpp>
// b 是 Int(&)[3] 类型
// 此时长度信息没有丢失
auto& b = a;
</code>
  * 不要使用 ''extern'' 指针声明数组
<code cpp>
//声明数组
//不能使用 extern 指针
extern int array[4];
//illegal
//runtime error

extern int* array;
</code>\\ 
//**为什么不能这么做？**//\\ \\ 

很多情况下，长度信息需要反复的修改。如果在声明的时候带上长度信息，那么每次更改 array 的长度都必须同时去声明中改变 array 的长度。因此很多情况下会使用指针替代数组。但 ''extern'' 不能直接使用指针代替数组。来看看下面的例子：
<code cpp>
//source.cpp
int array[4] = {1,2,3,4};
void fun()
{
    std::cout << array << std::endl;
}
//main.cpp
extern int* array;
void fun();

int main()
{
    fun();
    std::cout << array << std::endl;
}

// output
// 两个 array 的输出不一样
0x7ff718ee3000
0x200000001
</code>\\ 
//**问题出在哪里？**//
  * 编译阶段没有问题，array 会被翻译为 ''*(array + step)''
  * 链接过程中：无论是 main.cpp 和 source.cpp 中的 array 是没有类型的，只有名称。这是因为类型只在编译期有效，如果加了更多的类型信息可能会导致不同翻译单元之间的链接问题。
  * 运行过程中：
    * source.cpp 中的打印结果是正确的，因为 source.cpp 中的 array 代表的数组可以被编译器识别，此时编译器认为是指向 array 头元素的指针
    * main.cpp 中的 array，实际上不是一个地址：
      * ''array[4]'' 中存储的类型是 int（32字节）一个16进制数为 $2^4$，占 4 bits，那么每个数组成员都需要 32 / 4 = 8 个 16 进制数来表示，比如 1 就是 ''00 00 00 01''
      * 按小端法，int 会从低地址到高地址保存： ''01 00 00 00''
      * 数组中的数是连续存储的，因此该数组在内存中表现为： ''01 00 00 00 02 00 00 00 03 00 00 00 04 00 00 00''
      * 而此时我们此时以指针的方式来解析该段数据，那么就会将前 8 个子节的内容拼成一个类似地址的内容，也就是 ''0x 2 00 00 00 01''。
      * 该内容并不是 array 的首元素地址，而是 ''01 00 00 00 02 00 00 00'' 按内存地址的方式解析出来的结果。这个结果反应的是数组的内容，是固定的，
      * 可见数组和指针还是存在区别的
//**应该怎么做？**//
<code cpp>
extern int array[];
</code>
这么写合法。''int array[]'' 是数组的合法声明。定义已经在 source.cpp 中完成了。
<WRAP center round info 100%>
  * 该方式被称为 //Unkonwn Bounded Array Declaration//。
  * int array[] 被称为 incomplete type，这种类型大多数用于共享定义的场景中
</WRAP>
==指向数组开头和结尾的指针==
  * 开头指针：头元素
  * 结尾指针：尾元素**后一位**
计算的两种方法：
<code cpp>
int a[3] = {1,2,3};
//开头指针
a; //数组名即为指向数组首地址的指针
&(a[0]) // 取数组首元素的地址（注意括号）
std::begin(a); std::cbegin(a); //标准库提供的取地址函数，int* 和 const int*

//结尾指针
a + 3;
&(a[3]);
std::end(a); std::cend(a); 
</code>
需要注意的是，''std::begin()'' 与 ''std::end()'' 适用于**数组类型**而不是指针类型，任何导致数组信息的丢失（转换，Unkonwn bounded）都会导致调用失败：
<code cpp>
b = a;
//error, begin() & end() are not applicable to a pointer.
std::begin(b); std::end(b); 
//之前的共享 array 也不能使用 begin 和 end，因为边界未知
extern int array[];
std::begin(b); std::end(b); 
</code>
对于 incomplete type 的获取，如需使用
''std::begin()'' 和 ''std::end()''，需要在声明的时候声明为 complete type，也就是提供其数组的长度：
<code cpp>
//ok
extern int array[4];
std::begin(b); std::end(b); 
</code>
<WRAP center round box 100%>
std::begin(); std::end(); 是泛型函数，可以应用到各种类型的容器中。
</WRAP>
===指针的其他算术运算===
<code cpp>
int a[3] = {1,2,3};
auto ptr = a;
auto ptr2 = a;
//指针的前进
ptr = ptr + 1;
//比较
ptr == ptr2;
//关系运算（不推荐，除非两个指针在同数组中）
ptr > ptr2;
//求距离
ptr2 - ptr
</code>
===数组的其他操作===
==求数组元素个数==
  * ''sizeof()''：使用 sizeof 获取数组总大小，再除以元素的宽度
  * ''std::size()''：使用标准库方法
  * ''std::end() - std::begin()''
<code cpp>
/* 必须都是对数组类型进行操作 */
int b[10];
//sizeof，[C method]
sizeof(b) / sizeof(int);
//std::size, [recommand]
std::size(b);
//end - begin, [run time method]，通常使用 const 版本。
std::end(b) - std::begin(b);
</code>
==遍历==
<code cpp>
int c[3] = {1,2,3};
//使用 std::size() 和 while
size_t index = 0;
while(index < std::size(c))
{
    std::cout << c[index] << '\n';
    index++;
}

//cbeign, cend
auto bPtr = std::cbegin(c);
while(bPtr != std::cend(c))
{
    std::cout << *bPtr << '\n';
    bPtr++;
}
//range for ，语法糖，基于 cbegin / cend 实现
for (auto elem : c)
{
    std::cout << elem << '\n';
}
</code>
==C 字符串==
  * 本质是数组
  * 有额外的函数来支持该数组 ''<cstring>''
====多维数组====
  * 本质上是元素为数组的数组
  * 在内存中是连续排列的，但按照元素的个数分组
  * 二位数组类似**行优先**矩阵，左边是行，右边是列
===多维数组的理解===
<code cpp>
// 从左到右看
// (x[3]) 是元素，元素类型为 Int[4]
int x[3][4]; 
// (y[3]) 是元素，元素类型为 int[4][5]
Int y[3][4][5];
</code>
{{ :cs:programming:cpp:cpp_primer:mult_array.svg?250 |}}
===多维数组的初始化===
  * 默认初始化：遵从C++ 的默认初始化
  * 聚合初始化：
<code cpp>
//由于在内存中是连续的，因此可以使用 list 初始化
//初始值不够的所有元素都会进行默认初始化
//按位初始化
//1,2,3,4,0,0,0,0,0,0,0,0,0
int x[3][4] = {1,2,3,4};
//分组初始化
int y[3][4] = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
//分组初始化的默认初始化处于分组内部
int z[3][4] = {{1,2,3}, {4,5,6,7}, {8,9,10,11}};
//输出 0
std::cout << z[0][3];
//输出 4
std::cout << z[1][0];
//如果需要自动推断，必须指定元素的类型
//只能省略最高位
int a[][] = {1,2,3,4}; // error
int a[][] = {{1,2,3,4}}; // error 
int a[][4] = {1,2,3,4}; // int[1][4]
</code>
===多维数组的遍历===
  * 多维数组遍历需要多重循环
<code cpp>
int x [3][4] = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}};

//range for
//注意所有外层的 auto 都需要以引用的方式将数组类型传递给内层循环
//否则，内层循环只会得到一个指向外层数组的指针
//内层循环中 range for 需要使用数组的头指针作为起点，头指针 + 内层数组的长度作为终点进行循环
//如果传入的是指针，长度信息丢失，那么将无法进行循环
for (auto &row : x)
{
    for (auto col : row)
    {
        std::cout << col << " ";
    }
    std::cout << std::endl;
}

//while loop
//注意 std::size() 的参数不同
//遍历的顺序：x[0][0-3], x[1][1-3], x[2][1-3]。
//推荐行优先遍历，可以减少 cache miss。
size_t outter = 0;
while (outter < std::size(x))
{
    size_t inner = 0;
    while (inner < std::size(x[inner]))
    {
        std::cout << x[outter][inner] <<" ";
        inner++;
    }
    outter++;
    std::cout << std::endl; 
}
//纯指针遍历
//与之前相同，cbegin 和 cend 需要数组而不是指针，因此内循环需要解引用
auto OutterP = std::cbegin(x);
while (OutterP != std::cend(x))
{
    auto InnerP = std::cbegin(*OutterP);
    {
        while(InnerP != std::cend(*OutterP))
        {
            std::cout << *InnerP << " ";
            InnerP++;
        }
        std::cout << std::endl;
    }
    OutterP++;
}
</code>

===多维数组与指针===
  * 多维数组也可以转化为指针，但只有最高维会进行转换
    * 对于外围数组，如果指针要有意义，其指向的单位一定是外围数组的元素
    * 比如下面的例子，外围数组有3个元素，如果移动指针 ''x+1''，则移动的单位实际上是一个包含 4 个 int 的数组
<code cpp>
int x[3][4];
// ptr int(*)[4]
auto ptr = x;
//ptr2 int(*)[4][5]
int y[3][4][5];
auto ptr2 = y;
</code>
==使用类型别名声明多维数组的指针==
<code cpp>
using A2 = Int[4][5];
int x[3][4][5];
A2* ptr = x; //x 指向 int[4][5]
</code>
注意类型别名会改变维度的优先级：
<code cpp>
using A = int[4];
//如果这里使用 A 定义数组，那么结果会是 [4][3] 而不是 [3][4]
A z2[3]; //等价与 int z2[4][3];
</code>
====Vector====
  * 标准库提供的序列容器（类模板）
  * 可复制，可动态更改个数
<code cpp>
//使用需要包含头文件 vector
#include <vector>
//类型是 vector<int>
std::vector<int> x = {1,2,3};
//可复制
std::vector<int> y;
y = x;
</code>
===Vector 的初始化===
  * 默认初始化为 0 个元素
  * 支持各种初始化
<code cpp>
//聚合初始化，x 的元素为 1,2,3
//使用 brace
std::vector<int> x = {1,2,3};

//init with default element count
//使用panthesis
//y 是 3个元素的 vector，每个元素都被默认初始化为 0
std::vector<int> y(3);
//count + value
//z 中有 3 个元素 都是 1
std::vector<int> z(3,1);
</code>
===Vector 的常用成员函数===
<code cpp>
//计算 vector 的大小
x.size();
// 查看 vector 是否为空
x.empty();
// 添加元素（运行期）
x.push_back(4);
// 删除元素
x.pop_back();
// index 访问
x[2]; //无安全保证
x.at(2); //越界访问会抛出异常

//成员 begin & end，指向第一个元素和最后一个元素
auto beg = x.begin();
auto e = x.end();
</code>
===Vector 的遍历===
<code cpp>
//成员函数 + 迭代器（类指针）
//注意 begin / end 的结果不再是指针，是 iterator
auto vBeg = x.begin();
auto vEnd = x.end();
while(vBeg != vEnd)
{
    std::cout << *vBeg << " ";
    vBeg++;
}
//range for
for (auto elem : x)
    {
         std::cout << elem << " ";
    }
</code>
===迭代器===
  * std 容器中，通常使用迭代器模拟代替指针
  * 迭代器可以：
    * 解引用
    * 下标访问会产生 *(x + index) 的行为
    * 可以移动，相减（必须指向同一个 vector）
==Vector 的比较==
  * 位数相同且元素相同，则相等
  * 如果一长一短，短 vector 与长 vector 对应位置内容相同，则长的较大
  * 否则按位比较，找到的第一组不相同元素中，较大元素所在的 vector 较大
===Vector 的其他细节===
  * 改变 vector 元素数量可能会导致迭代器失效
  * Vector 支持多维
<code cpp>
//元素是 Int vector 的 vector
std::vector<std::vector<int>> x;
</code>
  * 支持取地址并调用运算符（''->''）
<code cpp>
std::vector<int>* ptr = &x;
ptr->size(); //equal *(ptr).size()
</code>
  * size() 返回的是 ''size_type''
====std::string====
  * 特化自 ''std::basic_string<char>''
  * 可复制，可改变字符串长度
===string 的使用方法===
<code cpp>
//需要引入头文件
#include <string>
//初始化
std::string myStr = "helleworld";

//使用多次复制目标字符作为初始值
//结果是 'aaa'
std::string myStr2(3, 'a');
//拷贝初始化
std::string myStr3 = myStr;
std::string myStr4(myStr);

//比较尺寸size & empty
//比较 == > <，比较规则与 vector 同，按字符为单位比较
//赋值
std::string newStr;
newStr = myStr;
//拼接
newStr = myStr + myStr2;
newStr = myStr + "hellWorld";
//string + 的重载左边要求对象类型是 std::string，所以 c-string 不能放到加号左边
//error
newStr = "hello" + myStr;
//索引
myStr[0];
</code>
==转化 std::string 到 c-string==
<code cpp>
//返回指向一个 Null teminated(\0) 的 const char* 指针
myStr.c_str();
</code>