2018-07-17-备战CCC-动态数组初步

前言

全新的系列，你没有体验过的船新版本——CCC备战篇，
之前跑去西雅图和微软的某系统工程师谈笑风生，说是明年暑假可以提供一个实习的机会......
要是有算法竞赛成绩会好看很多
行，佛了，开始CCC备战。
【把之前写了一半的词云搜集给暂停了，反正网上都是写好的源码】

0x01 Why chose 动态数组

有些时候想开一个数组，但是却不知道应该开多大长度的数组合适，
这种时候你一般有两种选择，一种是#define MAX 100000，

但是呢有古人云：“数组一炸天地灭”，所以我们可以换用动态数组 'vector' （或者在北美这边流行的java里面叫做 ‘ArrayList’）【顺便说一下这一句诗的下一句是换用搜索报平安】

因为我们需要用到的数组可能会根据情况变动。这时候我们就需要用到动态数组。
所谓动态数组，也就是不定长数组，数组的长度是可以根据我们的需要动态改变的。

动态数组的实现也不难，但是在 C++ 和 Java 里面有已经写好的标准模板库（Standard Template Library），就是我们常说的 STL 库，实现了集合、映射表、栈、队列等数据结构和排序、查找等算法。我们可以很方便地调用标准库来减少我们的代码量。

0x02 make 一个 动态数组

在C++中有现成的轮子来给你写【终于良心了一会，指针nmsl】，
只需要导入一个库，就可以自动完成动态数组的定义：

#include <vector>
using namespace std;
int main() {
    return 0;
}

现在我们来创建一个动态数组，

使用语句：

vector<int> vec

讲解，<>里面填写数据类型，vec为此动态数组名称，初始的动态数组是空的，

但是，可以初始化嘛？答案是肯定的~！

vector<vector<int>>vec(5,vector<int>(0))

这样的含义是：行数为5，列数为0，在行数已知列数未知的时候，使用这样子的语句进行初始化。

0x03 insert item！

在vector的末尾添加元素感觉就像Python list'中的append一样方便，
c++中使用push_back()方法来添加元素，

#include <vector>
using namespace std;
int main() {
    vector<int> vec;  // []
    vec.push_back(1); // [1]
    vec.push_back(2); // [1, 2]
    vec.push_back(3); // [1, 2, 3]
    return 0;
}

对比一下Python的:

vec=[] 
vec.append(1) #[1]
vec.append(2) #[1,2]
vec.append(3) #[1,2,3]

一样的简单明了是不是？

访问元素与获取长度

感谢STL库，现在基本上所有的操作都有现成写好的模板来给你使用~
举个粒子：

左边是C++的操作	右边是Python的
获取长度
size()	len()
迭代数组
for(int i=0;i<vec.size();++i)	for i in range(0,len(list))

标准的C++迭代输出动态数组的姿势：

#include <vector>
#include <stdio.h>
using namespace std;
int main() {
    vector<int> vec;  // []
    vec.push_back(1); // [1]
    vec.push_back(2); // [1, 2]
    vec.push_back(3); // [1, 2, 3]
    for (int i = 0; i < vec.size(); ++i) {
        printf("%d\n", vec[i]);
    }
    return 0;
}

有上面的代码我们又可以推到出一个结论：

• 动态数组的访问是靠下标[]来执行的
  那么修改呢，时候想链表那样要更改指针地址呢？

答案是false的，直接使用“=”赋值即可

#include <vector>
#include <stdio.h>
using namespace std;
int main() {
    vector<int> vec;  // []
    vec.push_back(1); // [1]
    vec.push_back(2); // [1, 2]
    vec.push_back(3); // [1, 2, 3]
    vec[1] = 3; // [1, 3, 3]
    vec[2] = 2; // [1, 3, 2]
    for (int i = 0; i < vec.size(); ++i) {
        printf("%d\n", vec[i]);
    }
    return 0;
}

0x04 清空内存

clear() 函数用于清空列表，类似于 del a[:]。【Python其实也有一个一模一样的clear()函数来用，说Py你是不是抄的C++】
但是C++很鸡肋的一点是C++不能直接回收内存，clear只是清空了这个动态数组而已，没有彻底的回收这个动态数组的内存，所有有时候如果碰到对内存要求比较变态的屑题目【闭眼张嘴】就要使用下面的姿势来释放内存了：

vector<int> v;
{
    vector<int> x;
    v.swap(x);
}

先创建一个空的动态数组x，然后使用vector.swap()命令来交换两个动态数组，因为写在大括号里面，所以不用担心说会不会遗留x下来，执行完就删除掉了呢~

0x05 其他高级姿势

C++ 关于vector的官方母语文档，嘤语好的同志们可以去看看，

1.PNG
注意左边的列表，有没有发现几个熟悉的身影？
似李，Python 列表！

虽然这些命令竞赛中没有被要求掌握，但是.....嘿嘿嘿这么好用的命令再竞赛中简直就是作弊般的存在，
比如动态快速排序，而且可以直接使用swap来交换，惊了

其他高级姿势：
1.push_back 在数组的最后添加一个数据
2.pop_back 去掉数组的最后一个数据
3.at 得到编号位置的数据
4.begin 得到数组头的指针
5.end 得到数组的最后一个单元+1的指针
6front 得到数组头的引用
7.back 得到数组的最后一个单元的引用
8.max_size 得到vector最大可以是多大
9.capacity 当前vector分配的大小
10.size 当前使用数据的大小
11.resize 改变当前使用数据的大小，如果它比当前使用的大，者填充默认值
12.reserve 改变当前vecotr所分配空间的大小
13.erase 删除指针指向的数据项
14.clear 清空当前的vector
15.rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)
16.rend 将vector反转构的结束指针返回(其实就是原来的begin-1)
17.empty 判断vector是否为空
18.swap 与另一个vector交换数据【注意这里不是值】
例子：pop_back() 与 empty()判空 的用法【个人认为比较最重要的两个】

// vector::pop_back
#include <iostream>
#include <vector>
using namespace std;
int main ()
{
  vector<int> myvector;
  int sum (0);
  myvector.push_back (100);
  myvector.push_back (200);
  myvector.push_back (300);

  while (!myvector.empty())//如果当前动态数组不为空 
  {
    sum+=myvector.back();//sum+=最后一项 
    myvector.pop_back();//最后一项弹出 
  }

  cout << "所有项的和为" << sum <<endl;  

  return 0;
}
输出：所有项的和为600

例子：擦除erase的用法（和del类似）

#include <iostream>
#include <vector>
using namespace std;
int main ()
{
  vector<int> myvector;

  //制作一些数据(from 1 to 10)
  for (int i=1; i<=10; i++) myvector.push_back(i);

  //擦除第六个数据 
  myvector.erase (myvector.begin()+5); //begin+5=第六个哈哈哈奇怪的写法 

  //擦除前三个数据 
  myvector.erase (myvector.begin(),myvector.begin()+3);//区间的实现->(0,2) 

  cout << "myvector contains:";
  for (int i=0; i<myvector.size(); ++i)//经典的迭代
        cout << ' ' << myvector[i];//下表访问的实现
  cout <<endl;

  return 0;
}

警告：不要把 for (int i=0; i<myvector.size(); ++i)写成 for (int i=0; i<=myvector.size(); i++)，不然会出现数组越界访问到随机数的情况

例子：insert插入方法配合end()和*it 工作

#include<vector>  
#include<iostream>  
using namespace std;  
 
int main()  
{  
    vector<int> v(3);  
    v[0]=2; //v[0]是第0个元素 
    v[1]=7;  
    v[2]=9;  
    v.insert(v.begin(),8);//在最前面插入新元素。  
    v.insert(v.begin()+2,1);//在迭代器中第二个元素前插入新元素  
    v.insert(v.end(),3);//在向量末尾追加新元素。  
 
    v.insert(v.end(),4,1);//在尾部插入4个1
 
    int a[] = {1,2,3,4};
    v.insert(v.end(),a[1],a[3]);//在尾部插入a[1]个a[3]
 
    /*vector<int>::iterator it;  
    for(it=v.begin(); it!=v.end();it++)  
    {  
        cout<<*it<<" ";  
    }
    */
    for(int i=0; i<v.size(); ++i)
    {
        cout<<v[i]<<" "; 
    }  
    cout<<endl;
 
    return 0;
}  
 输出：8 2 1 7 9 3 1 1 1 1 4 4

PS：注释掉的那段迭代方法看不懂，要谁谁用去

例子：初始化一个二维动态数组
很多时候，我们要使用动态数组来存储一开始未知数量的数据时，往往都是在程序中得到行数和列数，然后再对数组进行初始化。可是，如果我们只知道行或者列其中的一个数量，可以进行动态数组初始化吗？
答案是可以的。如果我们知道行数，那么初始化可以如此写：vector<vector<type>>Name(row,vector<type>(0))。这样的含义是：行数为row，列数为0。那如何对这个数组赋值呢？例如简单做一个已知3行，但是不知道每行列数的二维矩阵M：

    vector<vector<int>>M(3,vector<int>(0));//初始化M，行为3，列为0
    vector<int>N(3)；
    for(int i=0;i<3;i++){
    N.push_back(i+1);
    }
    for(int i=0;i<M.size();i++){
    for(int j=0;j<N[i];j++){
    M[i].push_back(1);
    }
    }
初始化内容：
1

1 1

1 1 1

0x06 多维动态数组

二维的vector就是一个vector里面在套一个vector。

vector<vector<int> > v2d

特别注意：里面的vector<int>后面有一个空格，这个空格不能到少，因为在没有开启 c++11 的情况下，会被识别成一个>>。

接下来我们给第一维赋值，第一维是一个一维的vector，

for(int i=0;i<5;++i)
{
    v2d.push_back(vector<int>());//注意这里有一个括号
}

我们让第 i 行第 j 列的元素的值为 i∗j。

for(int i=0;i<v2d.size();++i)
{
    for(int j=0;j<5;++j)
    {
        v2d[i].push_back(i*j);
    }
}

这里就很奇怪了，并没有看见想二维数组那样的[x][y]两个下表啊，明明那就是一个一维的动态数组呢？
其实不是的，可能有一些难以理解，但是如果用Python的代码写一遍马上就神清气爽了【因为Python是一个动态分配内存的语言，所有的列表都是默认的动态数组】

v2d[i][j]=[] #等于vector<vector<int> 
for i in range(0,len(v2d)): #想一想这里返回的是什么的长度？
    for j in range(0,5):
        v2d[i].append(i*j)

先来解答一下前面的问题，有Python终端的同志们可以试一试定义一个样式为[[],[],[]]的标准多维数组，然后len它：

2.PNG
顺便推销云端Python终端cmd执行的bat脚本

现在明白了，之所以没有写成v2d[i][j]，是因为动态数组的添加不是靠下标来是实现的，不然也就失去了动态数组的优势【你都知道了数组的大小了还用动态数组干甚？】

最后我们输出5*5的序列：

for(int i=0;i<v2d.size();++i)
    {
        for(int j=0;j<v2d[i].size();++j)
        {
            cout<<v2d[i][j]<<" ";
        }
        cout<<endl;
    }

警告：对于第二个j的迭代，终止条件应该是：v2d[i].size()，不要忘记是第i项的大小，不是v2d的大小
用Python举一个上面易错的例子：

>>> v2d[0].append(4)
>>> print(len(v2d[0]))
4

那么这里为什么又开始使用下标了呢，因为我们在遍历这个二维数组啊不是添加项目，对于添加项目，元素的总数是未知的，因为题目没给啊，但是对于遍历输出的话就是已知了，因为题目叫你输出全部啊，留下来不输出的给谁看呢？
【如果你要是觉得充满指针的代码很Beautiful的话也可以翻到前面的一段注释掉的迭代找到执政迭代器的代码，反正我是不喜欢】

测试代码：

#include <iostream>
#include<vector>
using namespace std;

int main() {
    vector<int> v;
    for(int i=1;i<=10;++i)
    {
        v.push_back(i*i);
    }
    for(int i=0;i<v.size();++i)
    {
        cout<<v[i]<<" ";
    }
    cout<<endl;
    vector<vector<int> > v2d;
    for(int i=0;i<5;++i)
    {
        v2d.push_back(vector<int>());
    }
    for(int i=0;i<v2d.size();++i)
    {
        for(int j=0;j<5;++j)
        {
            v2d[i].push_back(i*j);
        }
    }
    
    for(int i=0;i<v2d.size();++i){
        for(int j=0;j<v2d[i].size();++j){
            cout<<v2d[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}
输出：
1 4 9 16 25 36 49 64 81 100       
0 0 0 0 0                                                                                                                      
0 1 2 3 4 
0 2 4 6 8                                                                                                                                             
3 6 9 12       
0 4 8 12 16                                                                                                                                                                                                                   Process exited with code 0

后记

我痛，STL秀的我眼瞎，怕不是吸收了Py的精华，

前CCC竞赛一等奖

海星，距离CCC还有8个月？？【一数下一跳哦，还以为明天就要比赛了】
RP++吧各位；

参考：
关于vector二维动态数组初始化
vector - C++ Reference - Cplusplus.com
C++ vector 容器浅析| 菜鸟教程

最后的最后

球球你们mark一下吧，说不定会碰到小姐姐呢？
真的会碰到小姐姐，你们每一条访问我在谷歌统计上都会看的啦~
【跳出率75%，nmsl】