静态数组和动态数组 内存分布

数组是程序设计中是一个非常重要的概念。数组是一个用于收集大量类似数据的容器，
以及其每一个元素能被相同处理过程迭代来处理的一个抽象体。
创建数组一般有三种方式：全局/静态范围的数组，局部变量数组，申请堆空间来创建数组。
其中，全局/静态范围的数组，以及局部变量属于静态数组。
而申请堆空间来创建数组的属于动态数组。

1. a[7]与p1_a[7]是一样的么？
2. 静态两维数组的排列顺序
3. 动态两维数组的排列顺序
4. 数组与指针
5. 各种数组的声明方式
6. 静态数组和动态数组在内存的组织方式
7. 杂谈，不为人知的数组表达方式
8. 数组的迭代与性能影响

a[7]与p1_a[7]是一样的么？

int g_a[10];    // 全局变量数组

int main(int argc, char** argv)
{
    int a[10];    // 局部变量数组
    static int s_a[10];    // 静态局部变量数组
    int *p1_a, *p2_a;    // 数组指针

    // 为动态数组申请空间
    p1_a = (int*)malloc(sizeof(int) * 10);
    p2_a = new int[10];

    // 为数组赋值
    a[7] = 0;
    s_a[7] = 0;
    g_a[7] = 0;
    p1_a[7] = 0;
    p2_a[7] = 0;

    // 释放空间，并且将指针置0
    delete[] p2_a;
    free(p1_a);
    p1_a = p2_a = 0;
}  

静态两维数组的排列顺序

用简单的程序来验证一下：

int a[35];
int b[7][5];

a[0] = 4;
a[1] = 5;
a[34] = 6;
b[0][0] = 7;
b[0][1] = 8;
b[1][0] = 9;
b[6][4] = 10;  

如果对两维的概念比较清楚的话，再看两维的排列顺序就不难了
首先是一维的情况（在内存中a[0]和a[1]是连续的）

动态两维数组的排列顺序

int* pa;
int** pb;

// 申请空间
pa = new int[35];
pb = new int*[7];
for (int i = 0; i < 7; i++)
{
    pb[i] = new int[5];
}

// 赋值操作
pa[0] = 4;
pa[1] = 5;
pa[34] = 6;
pb[0][0] = 7;
pb[0][1] = 8;
pb[1][0] = 9;
pb[6][4] = 10;

// 释放空间
delete[] pa;
for (int i = 0; i < 7; i++)
{
    delete[] pb[i];
}
delete[] pb;  

汇编分析

动态数组在内存中的分布大致如下，首先来看看一维：（pa[0]和pa[1]还是连续的）

数组与指针

从最简单的开始：

int a[10];
int *pa = a;  

接下来考虑稍微复杂一点的静态两维数组：

int b[7][5];
int (*pb)[5] = b; // 声明和赋值写在同一行可能比较混乱，如果单独写的话，应该是 pb = b;
int (*pb1)[5] = b + 1; // 或者&b[1]
int *pvalue = (*b) + 1; // 或者&(*b)[1]
int *pvalue1 = (*pb) + 1; // 或者&(*pb)[1]  

而对于后者，可以理解为b是一个拥有 7个数组类型的数组，
每个数组类型又是一个拥有 5个int类型值的数组。

对于动态两维数组，因为其本身声明就是int **pb，所以也不存在什么编译器报错的问题。
而且对其做两次解引用（*求值操作），也确实根据地址求了两次值。
如果算上指针本身是地址，需要间接引用的话，所以一共是做了三次间接引用。

各种数组的声明方式

静态数组和动态数组在内存的组织方式

全局变量数组/静态局部变量数组

char* c1 = "abcde";
char c2[] = "abcde";

c1[0] = 'b'; // 错误
c2[0] = 'b'; // 正确  

局部变量数组

动态数组（数组指针）

int *pa, *pb;
pa = (int *)malloc(sizeof(int) * 10); // 正确
pb = new int[10]; // 正确  

MyClass *pa, *pb;
pa = (MyClass *)malloc(sizeof(MyClass) * 10); // 错误
pb = new MyClass[10]; // 正确  

#include <iostream>
using namespace std;

class MyClass
{
    public:
        MyClass() {_i = _s_i++; cout << "MyClass(). " << _i << endl;}
        ~MyClass() {cout << "~MyClass(). " << _i << endl;}
    private:
        int _i;
        static int _s_i;
};
int MyClass:: _s_i = 0;

int main(int argc, char** argv)
{
    MyClass *pa, *pb;
    cout << "[malloc]" << endl;
    pa = (MyClass *)malloc(sizeof(MyClass) * 10);
    cout << "[new]" << endl;
    pb = new MyClass[10];
    delete[] pb;
    pb = 0;
    free(pa);
    pa = 0;
}  

[malloc]
[new]
MyClass(). 0
MyClass(). 1
MyClass(). 2
MyClass(). 3
MyClass(). 4
MyClass(). 5
MyClass(). 6
MyClass(). 7
MyClass(). 8
MyClass(). 9
~MyClass(). 9
~MyClass(). 8
~MyClass(). 7
~MyClass(). 6
~MyClass(). 5
~MyClass(). 4
~MyClass(). 3
~MyClass(). 2
~MyClass(). 1
~MyClass(). 0  

杂谈，不为人知的数组表达方式

int i = 4;
int a[10];
int j = 5;
int b[7][5];

0[a] = 6;
9[a] = 7;
0[b][0] = 1;
0[1[b]] = 2;
0[b[2]] = 3;

cout << (-1)[a] << endl;  

*a 等价于 *(a + 0) 等价于 a[0]
*(a + 5) 等价于 a[5]

好，让我们喘一口气，怪谈还没完呢～
看看最后一个cout输出语句：
cout << (-1)[a] << endl;
(-1)[a]根据刚才的知识我们可以得出： (-1)[a] = a[-1] ……等等，-1？编译器怎么没报错？？

在C/C++里当然不会报，因为报了就违背C/C++的设计目标了——多管不用管的
那么再把这个式子转换一下，可以得到*(a - 1)
按照指针的概念，也就是前一个元素的东西，
因为a[0]是数组头了，-1会指向哪里呢？猜猜看～
或许有人会说是i，因为按照书写的顺序，i在数组a上面。
但代码书写并非编译器的实现，根据编译器的实现，还有有没有开启优化，结果是不一样的
按照我目前手头的编译器（见文章的开头），采用DEBUG模式编译出来，输出的结果是5
也就是指向了j。

在80x86体系结构，Windows系列操作系统下，栈在内存中从大地址->小地址方向扩展。
换句话说，栈底在大地址，栈顶在小地址。
这样，压入参数的时候，i被压在了大地址上，也就是下方，
然后数组a压在i的上方，因为数组的顺序还是要沿着地址增长的方向扩展
所以a[0]在上方，a[9]在下方，
然后j又压在了a[0]的上方，所以a[-1]也就是j了。

再换句话说，这也就是所谓的栈溢出！
列出该程序执行该段程序时，栈的情况的话：

刚才我们在a[-1]，也就是j，现在我们把矛头转一下，直接对准返回地址。
按照栈的情况来看，返回地址用数组a来解释就是a[12]，稍微修改一下程序。
在函数结束前增加一行代码：
a[12] = 0;

顺利通过编译，嗯
执行……！调试器跳出，说有Access Violation
看一下当前EIP指针，果然等于0
程序也就这么被栈溢出给抹杀掉了（其实是操作系统抹杀了该程序，栈溢出的行为应该属于借刀杀人=v=）

不过一般非故意的栈溢出不会这么有针对性，都是循环失控导致的，这样会把栈一路上的地址全部破坏掉。
所以一般那些检查栈溢出的代码（DEBUG模式下有些编译器会插入），在栈帧两端设防，
一旦设防标志被破坏就认为发生了栈溢出，所以大多数非故意的栈溢出还是能够通过特定代码监测出来的:-)

数组的迭代与性能影响

#define MAX_I 1024 * 1024
#define MAX_J 1024 * 512
int a[MAX_I][MAX_J];
for (int i = 0; i < MAX_I; i++)
    for (int j = 0; j < MAX_J; j++)
        a[i][j] = 1;  

RDTSC
卷绕周期为172年
精度±0.001微妙（3.4GHz处理器）（受电源管理和乱序执行的影响）
秒转换：秒数 = 两次测试的差值 / 计算机CPU的频率

测试程序：

#define MAX_I 32 * 512
#define MAX_J 32 * 512
int g_array[MAX_I][MAX_J];

inline unsigned __int64 GetTick()
{
    __asm RDTSC 
}

int main(int argc, char** argv)
{
    __int64 t1;

    t1 = GetTick();
    for (int i = 0; i < MAX_I; i++)
        for (int j = 0; j < MAX_J; j++)
            g_array[i][j] = 1;
    cout << GetTick() - t1 << endl;

    t1 = GetTick();
    for (int j = 0; j < MAX_J; j++)
        for (int i = 0; i < MAX_I; i++)
            g_array[i][j] = 1;
    cout << GetTick() - t1 << endl;
}  

测试用机：
Intel(R) Core(TM)2 CPU T7400 2.16GHz 2.16GHz
2.00GB内存

通过测试可见，两种方式导致的性能差别几乎达到了10倍。
虽然现在机器越来越快，但不良的数据结构或者错误的算法导致的延迟还是存在的。
要消除各种耗时操作确实不是一项简单的事情，因为优化需要很多知识和经验。
由于主要还是讲数组的问题，这小节也不能扩展得太大，
至于如何优化程序结构，这还是一个比较大的主题，如果有机会的话就写写看吧^^