之前一直想当然地认为，C++中调用swap函数交换a和b两个数组，只是将a和b两个数组的头指针交换而整个数组中元素在内存中的位置并没有变动。今天队友突然给我看了一个实验，让我大跌眼镜。经过反复的研究，得出结论——C++中调用swap函数交换数组a与数组b，实际上就是将其元素逐一交换，而非交换它们各自的头指针。

下面是实验代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int a[3]={1,2,3},b[3]={4,5,6};
int main()
{
	printf("a=%p b=%p\n",a,b);
	for(int i=0;i<3;++i)
	{
		printf("%d ",a[i]);
	}
	putchar('\n');
	for(int i=0;i<3;++i)
	{
		printf("%d ",b[i]);
	}
	putchar('\n');
	swap(a,b);
	printf("a=%p b=%p\n",a,b);
	for(int i=0;i<3;++i)
	{
		printf("%d ",a[i]);
	}
	putchar('\n');
	for(int i=0;i<3;++i)
	{
		printf("%d ",b[i]);
	}
	putchar('\n');
	return 0;
}

我们比较swap前后的数组a与数组b，发现它们的首地址始终未变，而其中元素的值发生了交换，如下图：

这一发现让我一度认为自己的地址输出方法有误，于是尝试了各种地址输出方案，发现都是一样的结果。

为此，我查阅了C++有关swap函数的官方文档（http://www.cplusplus.com/reference/algorithm/swap/），发现在C++11标准中，swap函数有两个重载函数——

这样的定义让我有些惊讶。按照上述定义，C++中调用swap函数交换数组，必须两个数组长度相等，否则会出现编译错误（一开始不信这个邪，将一个长度为3的数组与一个长度为4的数组进行交换，发现编译结果：）。而且我们可以从第二个函数中清晰地看出，“swap两个数组名称”与“用for循环遍历数组中每一个并swap对应的元素”等价。

到这里为止，我们问题的原因已经分析得很明显了，一切都是C++中STL模板库设计所致。

但是C++为何要遵循这样的设计？我们知道，如果交换两个长度为n的数组，直接交换他们的指针是最快速的方法（实际上在Java里我们也是这么做的），复杂度为O(1)。然而，如果我们逐一交换其中的元素，那么就会得到O(n)的复杂度，显然不优。

查阅了大量资料后，我总结出了两点设计原因，这两点原因告诉我们，C++模板库的设计相当合理，如果不是如此，那将会是一场灾难。

第一，C++数组的内存地址确定后不能再改变。这个特性继承于C语言，是一个接近硬件的设计。C++的数组名称和我们平时所说的指针其实有本质区别，它们表面上大多数用法相同，然而实际上则是千差万别。这里举一个小例子加以说明：

#include<cstdio>
using namespace std;
int main()
{
	int a=0;
	int*b=&a;
	int c[10];
	printf("%d %d",sizeof(b),sizeof(c));
	return 0;
}

运行结果：8 40

如果说数组名称与指针为同一事物，那么此处应当输出两个相同的数值，然而我们看到，输出结果一个是指针本身的长度，另一个是数组的全长。

指针指向的两个值是可以相互交换的，但是数组名称不可以。数组名称的实质其实是在将他们的数组信息（首位置、长度等）进行记录，这个记录是在底层实现，所以数组名称不属于我们可以声明的任何一类数据类型，我们无法交换其首地址指针。

第二，方法调用栈使C++数组交换只能采取这样的形式，否则灾难将会发生。下面是一段示例代码，解释了如果交换其地址将会发生的巨大灾难：

unsigned long long factorial(unsigned long long n)
{
	if(n==1)
	{
		return 1;
	}
	int a[10];
	//add swap between a here and a in last level
	return n*factorial(n-1);
}

稍懂算法的人都可以看出这是一个计算阶乘的递归函数，其原理简单便于我们理解。其中加了注释的地方代码并未明确写出，实际上我想做的是将递归上一层中的a数组与当前层中的a数组做一个指针交换（C中无此语法，故未写出）。

现在，我们看方法调用栈是如何调用factorial(2)的：

初始时，栈是空的：

首先，factorial(2)进栈，在栈中申请了一段空间存储a数组（为了区分，命名为a1）：

然后，factorial(1)进栈，在栈中申请了一段空间存储a数组（命名为a2）：

我们将a1与a2数组交换指针（假设存在此操作）：

图中红色箭头代表数组名称实际指向的内存位置。

由于factorial(1)已经是递归出口，所以下面开始出栈，将factorial(1)弹出方法调用栈后的情形：

可以看到目前的情况如上图所示——栈顶指针已经下移到factorial(2)上方，然而栈中元素却还是指向一个早已出栈的内存地址。

如果换在Java那样的十分灵活的垃圾收集机制和内存管理机制中，这样的情形是可以被接受的。然而，C++没有自己的垃圾收集机制，它会认为已经出栈的元素所在空间已经释放，一旦有新的元素进栈，就会立刻覆盖原有的a2数组内容，使得a1数组指针指向完全不正确的信息。（Java中，如果一个区域还有引用，JVM会避开此区域申请内存）

正是因为C++这样接近底层的定义方式，为了保障我们数据的安全性和可靠性，STL模板库才会做出将数组中元素值全部交换的“保险”做法，使得程序的正确性得以保证。

这样做的代价也很明显，数组交换的时间复杂度增加了，给想要方便的人增加了困扰。（比如在ACM竞赛中直接TLE等等）

如果想要更改这个swap函数的方式，首先我们必须修改C++底层的栈操作机制。会不会有一天有一个改良版的C出现呢？如果出现，那会是什么样子？我不能想象，这个问题实在太复杂了。于是我立刻又开始刷算法题去了……