传统数组 vs vector和list
传统的数组：
int arr[10]； 传统的数组有以下的缺点：
1）长度不可修改
2)内存分配
局部数组:把数组定在函数内， 数组便是局部变量，故会被分配在栈上 但栈的大小是有限制的 ，故其在内存中不能超过1MB。 如果数组太大，可能会导致栈溢出。
int arr[1000000]; // 如果超出了内存限制，可能会失败全局数组: 如果将数组声明为全局变量，数组会分配在数据段或 BSS 段中，不会受到栈大小的限制。但是，OJ（在线评测系统）通常对内存有严格的限制。如果数组过大，可能会超出内存限制，导致超时或内存不足的错误。
3）数组作为参数不方便。
在c语言中，将数组作为参数，实际上是传递数组的首地址，即传递的是指针，而不是整个数组。
故被调用函数只能得到数组的首地址，而无法得到数组的长度。
在做oj时要求用纯c解题，怎么解决上面的问题：
==》
1）一开始申请一个大的数组，如果局部数组的长度无法满足要求，就将数组定义为全局数组。若全局数组的占用内存超过了题目的内存限制。就是算法有问题。
我们也可以使用动态内存分配（malloc/realloc）来模拟动态数组，并手动管理内存。
2）在传参的时候传两个参数，数组的地址 和长度。
// 分配初始内存
int* arr = (int*)malloc(sizeof(int) * initial_size); //动态扩展数组
arr = (int*)realloc(arr, sizeof(int) * new_size);
//传递数组的指针和长度
void func(int* arr, int size) {
}但若用c/c++,更好用的办法就是使用c++提供的vector，即动态数组。
vector的使用
都说：" 传统的静态数组 的大小在编译时就已经固定，无法在程序运行时修改。 而动态数组可以"，对于这句话，通俗一点讲，就是说：
我们可以在写代码时不必定义其大小，即使定义了，我们也可以在后续的代码中使用各种方法插入或删除其元素，因为其在运行时会根据我们的代码操作自动调整其内存的 。
vector是c++提供的STL。他有一些优点；
1） 会自动处理内存分配和释放 ， 免了 C 语言中常见的内存管理错误。
2） 通过 vector::size() 可以轻松获取数组的长度。
3）提供了丰富的成员函数
我们主要学习vector的增删查改。
引入
#include<vector>增：
增操作包括初始化和插入；
1.初始化
vector<int> vec;
vector<double> vec;注：vector不是类型，vector< type>才是类型，故下面的vec1和vec2不是同一种类型。
当然了也可以自定义一个类,从而可以定义vector<MyType>类型的变量；
struct MyType{
int val1;
double val2;
}
vector<MyType>vec;另外，vector<int>也可以作为一种类型放在vector的<>中，
构成vector<vector<int>>,这种类型便是代表动态数组的动态数组，即二维数组。
vector<vector<int>>在机试中，对于二维数组，推荐使用动态数组的静态数组，即下面这种写法；以应用于实现图算法中的邻接表。
vector<int> arr[10];2.插入
插入数据使用push_back: 往动态数组的尾部插入；
我们知道，往顺序表中插入元素代价很大，而这种往数组末尾插入元素的操作非常高效，但若如果我们硬要往任意位置插入元素，该怎么办？
==》可以使用迭代器，我们稍后解答
int a;
while(scanf("%d",%a)!=EOF){
vec.pushback(a);//往vec尾部插入a
}查找
1、根据数组下标访问对应元素
//定义的这个数组下标从0到4
vector<int> vec={1,23,4};
int i=0;
printf(“vec[i]=%d\n",vec[i]);2.遍历整个vector（for,迭代器）
vector本身携带了长度的信息，可以使用vec.size()获取长度
从而可以使用for循环遍历数组
int size=vec.size();
for(int i=0;i<size;i++){
}除了用普通for循环，还可以使用迭代器
其提供了一种通用方法；可以访问不同类型的数据结构；我们可以将迭代器理解为一个高级的指针；
迭代器的类型是：动态数组类型：：iterator
例vecotor<int>：：iterator对于一个数组，{1,3,5,7,9}
我们可以使用begin（）来获取第一个元素的位置；使用end（）来获取尾后的位置；当我们对迭代器做自增操作，他便会后移；他的用法如下：
vector<int> vec={1,3,5,7,9};
vector<int>:: iterator it;
for(it=vec.begin();it!=vec.end();it++){
printf("it=%\n",*it);
}现在解决上面硬要往任意位置插入元素的问题：
因为迭代器可以访问到数组中任意一个位置；所以可以利用它对任意位置插入，删除元素。（insert和erase）
因为insert和erase会修改动态数组的结构，所以插入或修改完成后it的指向无意义。所以之后要对迭代器重新赋值。
但是这种插入操作最好避免使用；而使用push_back进行插入
vector<int>:: iterator it;
it=vec.begin();
vec.insert(it,2); //往it所在位置插入元素2
//注意迭代器要重新赋值
it=it+3;//it+3相当于3次++，只能在vector中使用3.通过元素信息查找其位置
删
1.删除一个元素
我们可以使用pop_back()删除最后一个位置的元素。
vec.pop_back();同样的，如果我们硬要删除一个位置的元素，可以使用迭代器配合erase函数。
vecor.erase(it);2.把vector清空
vector.clear()list的使用
前面我们讲过，即使使用迭代器配合insert和erase函数能够在任意位置对数组进行增加和删除操作，但是还是不推荐那样做。因为，如前面所言，顺序表的线性结构进行这样的操作真的很低效。所以，如果我们硬要做，就不能使用传统的线性结构，而得使用链式结构。
c++标准库为我们提供了一个链式结构的顺序表，叫list。
list的底层原理是一个双向链表。
引入
#include<list>增 insert
前面我们在vector中对于迭代器，使用了it+=3表示迭代器it++了3次，但是因为链表中不支持随机访问，故不支持加法运算符，故只能靠自增3次来实现；
list<int> ls={1,3,4,5,6};
//获取迭代器
list<int>::iterator it=ls.begin();
it++;
it++;
it++;
ls.insert(it, 10);删
it.erase();查
遍历list
for(it=ls.begin();it!=ls.end();it++){
printf("it=%d\n",*it);
}vector和list的选择
若一个题目中要求使用一个线性的数据结构，我们首选vector,
但如果你发现这个vector在使用的过程中存在着大量的对中间元素进插入和删除的操作，就改用list。
补充解惑：
1.为什么往线性表中的任意元素插入或删除元素很低效？
====》
线性表（如 vector）的底层是一个连续的内存块（数组）。在往数组中间插入或删除元素时，需要移动其他的元素。
因此 插入和删除最坏情况下的事件复杂度都是为o(n)。
2.list的增删改查都是使用迭代器完成的吗？
===>
是的，list 的增删改查主要是通过迭代器来完成的。
由于 list 是基于链表实现的， 因此没有下标访问的方式，只能通过迭代器进行增删改查。 迭代器提供了一个统一的接口来遍历、修改 list 中的元素，增加了代码的灵活性和可移植性。
ls.insert(it, 10);
ls.erase(it);
std::cout << *it << " ";