基础容器--数组

数组

序列型容器

数组代表内存里一组连续的同类型的存储区,可以用来把多个存储区合并成一个整体。比如:int arr[10] = {1,2,3,4,5,6,7,8};

数组声明:

  • int arr[10];
  • 类型名int表示数组里所有元素的类型
  • 整数10表示数组里包含的元素个数
  • 数组元素个数不可以改变,是常量

使用注意:

  • 每个元素都有下标,标识一个元素在当前数组容器中的位置。通过下标可以直接访问数组内任意元素
  • 下标从零开始
  • 超过范围的下标不可以使用,会内存错误。一定要注意,内存溢出是程序中经常出现的BUG
  • 数组名和下标可以表示数组里的元素,如a[2]表示第三个元素
  • 数组定义中的类型可以是除引用之外的任意类型,引用是不能赋值的,所以没有引用数组:int& a[10]错误

数组优点:

  • 可以编写循环程序,依次处理数组里的所有元素;
  • 循环变量依次代表所有有效下标;

数组使用常见错误:off-by-one error(差一错误)

考虑一个问题,假定整数x满足边界条件x>=16且x<=37,那么此范围内的整数x可能的取值有多少?这个问题思考有两个基本原则:

  1. 首先考虑最简单的情况(特例),然后将结果外推;
  2. 仔细计算边界问题;

特例:x的上界与下界重合,即x>=16与x<=16,显然其中的x个数为1;那么假定下界位low,上界位high;当low与high重合,个数为1,即共有high-low+1个元素。那么外推,这里共有37-16+1=22个元素。 最容易出错的地方就是+1,很容易就仅仅计算high-low。

  我们可以抽象出一个编程技巧来规避这个错误:用数学上的左闭右开[,)区间表示,上述问题可以看作[16,38),即38-16=22。C++中,我们编程也遵循这个原则,从0开始,使用非对称区间,让下界可以取到值,上界取不到值。这样设计程序,可以直接用上界-下界来取得范围大小;当取值范围为空的时候,上界值=下界值;即使取值范围为空,上界值也永远不可能小于下界值。

1
2
3
4
5
6
7
8
9
10
11
//推荐的方式:
for(int index=0;index < 10;++index)
{
cout<<a[index]<<" ";
}

//不推荐的方式
for(int index=0;index <= 9;++index)
{
cout<<a[index]<<" ";
}

  

结论--C语言设计数组下标的原则:从0开始,使用非对称区间[,);让下界可以取到值,上界取不到值;这样设计的好处:

  1. 取值的范围大小可以直接上界-下界;
  2. 如果这个取值范围为空,上界值=下界值;
  3. 即使取值范围为空,上界值永远不可能小于下界值;

初始化

  定义数组时,可以为其元素提供一组用逗号分隔的初值,用{}括起来,称为初始化列表。数组元素初始化时若没有显式提供元素初值,则元素会被向普通变量一样初始化:

  1. 全局的数组变量,元素初始化为0;
  2. 函数内部的局部内置类型数组,元素无初始化;如果只初始化部分元素,剩余元素也会被初始化为0;
  3. 数组类型不是内置类型,则无论在哪里定义,自动调用其默认的构造函数为其初始化,若该类无默认构造函数则会报错;

增删改查

  • 在尾部添加和删除操作,时间复杂度为O(1)。只需要操作尾部元素即可,对与其他元素没有干扰。
  • 在数组中间进行添加和删除操作,时间复杂度为O(n)。在中间操作,会对其他元素造成影响,操作元素后面的每一个元素都需要进一步操作
  • 数组的访问用遍历很高效,时间复杂度为O(1);
  • 数组的查找复杂度一般为O(n),取决于数组的容量(数组容量很大的时候并不适合遍历查找,时间复杂度太高,可以用二分查找);
1
2
3
4
5
6
//下标访问
a[2] = 5;

//指针访问
int* p = a;
*(p+2) = 5;
1
2
3
4
5
6
7
8
9
//寻找a[]中第一个值为3的目标:
int len = sizeof(a)/sizeof(a[0]);
for(int index = 0; index < len; ++index)
{
if(a[index] == 3)
{
return index;
}
}

  

二维数组

二维数组是包含行列两个维度的数组。二维数组的初始化既可以按行初始化,也可以顺序初始化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int ia[3][4] = {
{0,1,2,3},
{4,5,6,7},
{8,9,10,11}
};

int ia[3][4] = {0,1,2,3,4,5,6,7,8,9,10,11};


//只初始化每行第一个元素,其余元素为0:
int ia[3][4] = {{0}, {4}, {8}};

//只初始化第一行元素,其余元素默认为0:
int ia[3][4] = {0, 3, 6, 9};

//如果对二维数组所有元素赋值,则第一维(行数)可以省略
//只有第一维可以省略,哪怕是100维的数组也只能忽略第一维
int ia[][3] = {123456}; //相当于int ia[2][3] = {1,2,3,4,5,6}

二维数组访问:

1
2
3
4
5
6
7
8
9
int a[2][4] = {{1,2,3,4},{5,6,7,8}};
for(int row = 0; row < 2; ++row) //行
{
for(int col = 0; col < 4; ++col) //列
{
cout<<a[row][col]<<" ";
}
cout<<endl;
}

  二维数组我们一般按照一行一行的遍历,虽然可以进行一列一列的遍历的,但是实际操作中不建议这么做:因为循环需要满足“空间局部性”:在一个小的时间窗口内,访问的地址越接近越好,这样执行的速度快;也就是说我们一般把最长的循环放在内层,最短的循环放在最外层,以减少CPU跨切循环的次数。

  本质上所有数组在内存中都是一维线性的。不同的预言采用的存储方式不同,有的采用行有限存储,有的采用列有限存储。C/C++中采用行优先顺序存储。

二维数组动态声明:

1
2
3
4
5
6
7
8
9
10
11
//a[m][n]
int **a = new int*[m];
for(int i = 0; i < m; i++){
a[i] = new int[n];
}

//动态声明的数组需要释放内存:
for(int i = 0; i < m; ++i){
delete []a[i];
}
delete []a;

  

C++新型数组--vector

Vector是面向对象方式的动态数组。

动态是指容量不固定:我们经常使用的简单的数组,因为定义的时候就有固定容量,所以无法实现动态扩容插入元素。使用vector容器,可以轻松实现动态扩容添加元素。

面向对象是C++的特性,vector封装了一系列的方法,我们创建vecor的对象可以方便的使用。

添加

  使用vector容器,可以轻松实现动态扩容插入元素,传统的C数组容量有限,vector可以动态管理扩容。

  • push_back,尾添加
  • insert,任意位置添加(效率不高)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<vector>
using namespace std;

int main()
{
vector<int> vec = { 1,2,3,4 };

//尾添加
vec.push_back(5); //尾添加,不会出现下标越界 {1,2,3,4,5}


//指定位置添加
//insert方法,传入位置和值
vec.insert(--vec.end(), 6); //{1,2,3,4,6,5}
return 0;
}

遍历

1
2
3
4
for(int index = 0;index < vec.size(); ++index)
{
cout<<vec[index]<<endl;
}

  我们可以使用vector中的capacity()方法来查看vector当前的容量,用size()的方法来查看已经存储的元素的个数。这两者有区别,容量是指容器可以容纳元素的个数,数量是已经存储的数据个数;

删除

  • vec.pop_back(); //尾删除
  • vec.eraser(pos); //指定位置删除

  要注意如果打算使用eraser的方法进行尾删除,要注意end()的位置。数组的区间往往是左闭右开,end()指向的是尾元素的后面的地址,并不是尾元素自身。

1
2
vec.pop_back();
vec.eraser(vec.end()-1); //这两者等价