Question

数组可以说是最简单的一种数据结构，它占据一块连续的内存并按照顺序存储数据。创建数组时，我们需要首先指定数组的容量大小，然后根据大小分配内存。即使我们只在数组中存储一个数字，也需要为所有的数据预先分配内存。因此数组的空间效率不是很好，经常会有空闲的区域没有得到充分利用。

由于数组中的内存是连续的，于是可以根据下标在O（1）时间读/写任何元素，因此它的时间效率是很高的。我们可以根据数组时间效率高的优点，用数组来实现简单的哈希表：把数组的下标设为哈希表的键值（Key），而把数组中的每一个数字设为哈希表的值（Value），这样每一个下标及数组中该下标对应的数字就组成了一个键值－值的配对。有了这样的哈希表，我们就可以在O（1）实现查找，从而可以快速高效地解决很多问题。面试题35第一个只出现一次的字母就是一个很好的例子。

为了解决数组空间效率不高的问题，人们又设计实现了多种动态数组，比如C++的STL中的vector。为了避免浪费，我们先为数组开辟较小的空间，然后往数组中添加数据。当数据的数目超过数组的容量时，我们再重新分配一块更大的空间（STL的vector每次扩充容量时，新的容量都是前一次的两倍），把之前的数据复制到新的数组中，再把之前的内存释放，这样就能减少内存的浪费。但我们也注意到每一次扩充数组容量时都有大量的额外操作，这对时间性能有负面影响，因此使用动态数组时要尽量减少改变数组容量大小的次数。

在C/C++中，数组和指针是相互关联又有区别的两个概念。当我们声明一个数组时，其数组的名字也是一个指针，该指针指向数组的第一个元素。我们可以用一个指针来访问数组。但值得注意的是，C/C++没有记录数组的大小，因此用指针访问数组中的元素时，程序员要确保没有超出数组的边界。下面通过一个例子来了解数组和指针的区别。运行下面的代码，请问输出是什么？

答案是输出20,4,4。data1是一个数组，sizeof（data1）是求数组的大小。这个数组包含5个整数，每个整数占4字节，因此总共是20字节。data2声明为指针，尽管它指向了数组data1的第一个数字，但它的本质仍然是一个指针。在32位系统上，对任意指针求sizeof，得到的结果都是4。在C/C++中，当数组作为函数的参数进行传递时，数组就自动退化为同类型的指针。因此尽管函数GetSize的参数data被声明为数组，但它会退化为指针，size3的结果仍然是4。