【C++】C++中的计时、多维数组、排序

十九、C++的计时、多维数组、排序

1、计时
计时就是计算完成某个操作或执行某个代码所需要的时间。
计时的作用：希望某些事在特定时间发生；评估性能；做基准测试；查看代码运行有多快，也就是代码运行需要的时间。

在C++11标准之前，C++在语言层面是没有计时的。如果需要计时就得借助操作系统平台提供的API，比如windows的QueryPerformanceCounter。
C++11标准出来后，C++11新标准提供了和日期时间相关的库：chrono标准库。这个库可以实现计时功能，而不必再去使用操作系统平台库。

chrono标准库提供的是精度最高为纳秒级的计时接口。由于是C++标准库中提供的功能，所以可以很好地跨平台使用。

chrono库主要包含了三种类型：时间间隔Duration、时钟Clocks和时间点Time point。这里就不展开了。这里只说明如何计时即可。     

2、C++多维数组
就是二维数组、三维数组、四维数组等等统称多维数组。
关于数组的基础知识，建议你先看 【C++】深度理解C++数据类型：常量、变量、数组、字符串、指针、函数_c++ 字符串常量-CSDN博客 和 【C++】静态数组array、动态数组vector创建及优化_c++ array和vector-CSDN博客 中的数组部分。本小部分可以说是查漏补缺的小部分。

二维数组就是数组的组数(a array of array)，三维数组是数组的数组的数组(a array of array of array)。。。
就是多维数组是低维数组的集合。而数组就是内存块，而处理内存块最简单的策略就是使用指针。比如用一个指针，指向数组在内存中的开头位置。这就是我们处理数组的方式。下面是二维数组的创建和删除过程：

这是上面二维数组在内存中的抽象图：

下面是三维数组的创建和删除的代码：

这是上面三维数组在内存中的抽象图：

至此大家有没有发现，上面处理高维数组的方法非常容易造成内存碎片问题，因为一个个数组都是零散分布在堆内存中的，有的隔得很近有的很远，anyway都是随机分配的。以上面的三维数组为例，其实上面的三维数组只占用了64个int类型的内存。如果这64x4=256个字节是一整个连续的内存块，这样就可以把这个三维数组放到一个连续的内存缓冲区，而不是像上面那样单独创建了8个缓冲区，每个缓冲区有32个字节。当一个数组读写完毕后，还得跳到内存的另外一个位置读写下一个数组，这回导致cache miss（缓存不命中），也是意味着我们得浪费时间从ram中获取数据。如果这个8个32字节的数据都分配在一起，cache hits(缓存命中)就会高很多。所以我们一般都把高维数组放到一维数组中，具体做法如下：

上图的三层for循环要比上上图的三次for循环快得多。因为上上图的for循环，每次都要跳出循环去到不同地方的内存中写入数据，而上图的for循环不需要，因为都在内存中的同一行。

所以我们一般要避免使用高维数据。比如你要存储一张图片，图片数据一般都是三维或者四维的，此时你没必要用三维数组或者四维数组去存储图片，你完全可以用一维数组去存储，这样要好得多。

3、C++中的排序
【C++】深度理解C++数据类型：常量、变量、数组、字符串、指针、函数_c++ 字符串常量-CSDN博客 这篇博文的最好两个例子，一个是冒泡排序，一个是快速排序，感兴趣的同学可以自行查阅。

数据结构决定了存储数据的方式。 如果我们现在处理的是C++内置集合类型，比如std::array、std::vector,那我们就没必要自己去写排序算法，使用std::sort这个C++内置的排序函数即可。下面展示一下C++中的std::sort排序函数：

sort排序没有返回值，排序的复杂度是N*LogN。