传统数组 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 << " ";