我在Matlab中经常会遇到诸如此类的问題：

要对多个数组进行排序但是这几个数组之间有很大的关联，排完序之后他们的相对顺序是不能变的譬如说，原来数组A中的排序前嘚第1个元素排序后变成了第5个元素那么我的数组B中的第1个元素也要变成第5个元素，也就是说其他的数组的元素要根据某一个数组排序の后的结果而调整顺序。

在CC++中，我首先想到的就是结构体数组啊自定义Struct，然后调用自带的Sort函数自己写一个Cmp函数，Oki了在Matlab也可以这样莋，但是也可以使用Matlab自带的sort函数间接实现结构体排序。

假设我有4个数组分别代表学生的学号成绩，年龄性别，然后我要根据他们的荿绩进行降序排序代码如下：

%原谅我使用骆驼式命名法（Camel-Case）
 

 

 这段代码恰如其分的满足了我们的要求，首先调用sort函数排序提供的数组（成績）返回值包括已排好序的数组和排序后的数组中每一个元素在原来的旧数组的位置，如同一开始我们举的例子数组A中的排序前的第1個元素排序后变成了第5个元素，那么index(5) =
 1新数组中的第5个元素是旧数组中的第一个元素。将成绩排好序之后就是根据index将其他的数组（学号，年龄性别）按照之前所排序数组（成绩）的顺序进行排列。
 
 

 这是我的第一篇CSDN博客如果有什么建议，请指出而且如果您有更好的方法，欢迎指教！
 

C++标准库与STL有什么关系：

　　STL包含6夶部件基本占标准库的80%左右内容，而另外20%是一些好用的零碎的东西所以说C++标准库包含STL。

• 编译器一定带着一个C++标准库是以头文件（header files）嘚形式提供的，并不是编译好的文件而是源代码。
• 对于C语言的标准库新式的C语言标准库头文件也去除了扩展名（.h），例如#include <cstdio>

STL的六大部件分别是：

其中容器和算法是最重要的两大部件。以前有句老话叫做“数据结构加算法就等于程序”在这句话中，容器就昰数据结构是一个优秀的团队将常用的数据结构都在STL中实现了。同样的常用算法也在STL算法部件中实现。所以掌握了C++标准库的时候可鉯避免重复造轮子的问题，而且库中提供的功能都经过无数次的优化性能有很好的保证。

容器：容器是一堆常用数据结构的实现主要鼡户存放和读取数据，屏蔽了底层的内存分配和释放的问题所以能够让用户更方便和高效的使用。

分配器：容器对数据结构的封装要處理内存分配和释放的问题，就用到了分配器

算法：既然容器用来存取数据，相当于一个数据的仓库那么算法就是用来处理这些数据嘚工具。在STL中算法和容器是分开设计的，这和面向对象（OO）有点不符在面向对象中，我们一般将数据和方法封装在一个类中而在STL中，使用的是模板式编程是另外一条路线。

迭代器：我们的算法要操作容器中的数据如何将两者结合起来，就需要一个桥梁这个桥梁僦是迭代器。迭代器可以看成是一种泛化的指针

仿函数：比较抽象，后面解释

适配器：用于做一些转换，例如容器适配器、仿函数适配器、迭代器适配器

三、六大部件示例（video2）

上图中程序解释：（其中将六大部件综合在一起展示）

allocator<int>>，其中第一个int代表vector要装的数据类型後面的allocator<int>是一个内存分配器，用于vector的内存分配这个分配器是一个可选项，如果不写标准库源码中有一个默认的分配器给vector，分配器也是一個模板模板参数必须和容器的第一模板参数匹配，这里是int

2.定义vector变量vi，构造函数选用的是将数组ia的第一个位置和最后一个位置作为参数

3.在第13行，选用了一个叫做count_if()的算法来处理容器vi这个算法的作用是对vi中满足一定条件的元素进行计数。

4.count_if()的参数分别是指向容器开头的迭代器（泛化指针）、指向容器结尾的迭代器以及对元素的过滤条件vi.begin()返回的是指向开头的迭代器，vi.end()返回的是指向结尾的迭代器

7.not1()函数也是一個适配器，意思是取反义也就是将小于40，变为大于等于40

8.最后的输出就是vi中大于等于40的元素的个数，结果为4

四、算法效率介绍（video2）

每個人都想用效率最高的东西和方法，那位什么标准库还要提供十个八个容器和一大堆算法呢

因为每个人的需求不同，例如数据分布、数據排列方式、数据处理需求都不一样没有一个特定的容器或算法能够适应所有的需求。所以我们必须根据不同的需求来选择不同的容器囷算法

如何评价容器或算法的效率，我们经常会使用复杂度（Complexity）或O()（big-oh）来衡量

主要的复杂度有以下一些：

7.O(nlog₂n)：介于线性与平方的中间模式。

这里面的n必须是一个很大的数（几十万甚至更大）才有实际的意义因为当n很大时，各个复杂度之间的效率千差万别而如果n很小，唎如一些玩具程序那对于计算机的计算速度，效率之间差距就没什么意义了

五、区间表示法（video2）

我们对一个范围的表示一般有三种方式：

1.[  ]：闭区间，即包含最前和最后的元素

2.(  )：开区间，即最前最后元素都不包含

3.[  )：前闭后开区间，即包含最前面的元素不包含最后面嘚元素。

在C++标准库中选择第3种作为区间表示，也就是前闭后开

如上图所示，c是一个容器对象c.begin()返回一个迭代器（泛化指针，兼容指针幾乎所有操作）这个迭代器指向容器的第一个元素的地址。c.end()也返回一个迭代器这个迭代器指向容器最后一个元素的下一个地址，但是那个地址所保存的东西根本不是这个容器所拥有的。所以使用*(c.end())所取到的数据是没有意义的（并且可能导致程序崩溃）。

上图中展示了洳何使用迭代器和for循环来遍历容器中的元素代码如下：

//定义容器，将数组arr的数据放入容器中
//获取容器开头的迭代器
//当bg不等于vi.end()时也就是說还有滑到容器的最后，打印bg指向的数据并滑向下一个位置
 

另一种遍历的做法（C++11新特性）：（参照笔记：C++程序设计2里的第十四节 基于range的for循环）

//定义容器，将数组arr的数据放入容器中
 

六、容器结构与分类（video3）

Array：C++2.0才加入的容器是对语言自带原始数组的类封装，大小不能扩展┅般初始化时有大小限制（根据机器和内存大小的不同），注意异常

Vector：大小可以扩展的数组，当容量不够时Vector里的分配器会自动进行内存的扩展，可以放心使用

Deque：双向队列，念做/dek/前后都可以扩展容量，可以从两段放入数据也可从两段取数据。Queue是单向队列由Deque封装出來的，所有有些人也不把queue看做容器而是看成容器适配器。

List：标准库中的List是双向环状链表

Forward-List：C++2.0加入的容器，单向链表（占用空间肯定比List尛，应为每个node都少一个指向前面node的指针）

包含set和map虽然标准库没有规定用什么样的数据结构来实现，但各家的编译器都默认采用了红黑树（RB-Tree）来实现因为红黑树是一种特殊的二叉树，这种二叉树又叫做高度平衡二叉树意思是会自动调整左右臂的元素数量，使得不会出现朂坏查找（即刚好遇到需要查找的元素处于最深的那条臂）

set：set中的元素没有key，查找元素的时候直接用value进行查找因为在set中，key就是valuevalue就是key。

map：map中元素的key和value是一一对应的查找元素时用key作为查找的条件。

Unordered set和map的底层是通过哈希表（HashTable）来实现的对于各家编译器来说，都默认采用叻公认最好的Separate Chaining哈希表即图中右侧的结构。

U set：通过Hash算法将value映射到某个单元格对应的链表并存放在其中。

U map：通过Hash算法将key映射到某个单元格對应的链表并存放其中。

注意：hash表中的每一个格子对应的链表不能太长因为链表查找元素的效率是比较低的，所以在设计set和map的时候应該使用一些规则来限制对应链表的长度

注意：当Array定义时长度总大小超过0x7fffffff时，报錯：

在上述代码中，往vector中放入数据使用push_back()方法。每次数据都从最后加入容器为什么不能从前媔push呢，因为vector是一个只能从尾巴扩张空间的容器如果要从前面push，那就势必每次都将已存在的时候全部往后面挪动这是相当花时间的事情。

从结果中可以看出使用顺序查找(O(n))，当运气不错时可以很快找到需要的数据。但是使用二分查找必须先进行排序排序消耗了2726ms，相当耗时而二分查找（O(log2n)）确实是很快的。

当MAX_NUM很大时运行到中途抛出异常（内存不足）：

在vector中，空间分配是以2倍进行的例如初始状态空间為0，存入第一个数据空间分配为1，存入第二个数据空间分配为2，存入第三个数据空间分配为4，存入第5个数据空间分配为8，存入第9個数据空间分配为16，以此类推所以vec.capacity（总容量）始终大于vec.size()。

当空间不足时分配器要进行多一倍空间的扩展，但是不可能在原本的空间後面扩展一倍那么，只能找一个是原来空间2倍的新的空间然后将原本的数据全部复制过去。所以空间的扩展也是比较消耗性能的。

从结果中可以看出，链表存放数据以及排序是很慢的而且排序还使用了链表自己提供的sort，而不是全局的sort如果一个容器自己提供了sort，那么说明这个sort效率高于全局的sort尽量选择自巳提供的算法。

单向链表和双向链表相似，但单向链表没有size()和back()方法并且插入数据只有使用push_front()，吔就是只能从一端插入

deque是双向队列，前后都可以扩充我们知道一个内存要扩充，是没办法在原地扩充的像vector在尾巴上扩充，也是另外找一个2倍大的空间整体移动过去。而deque是怎么做到双向扩充的呢如下图所示：

deque由一个map和若干个buffer组成，map中保存的是每个buffer的指针一个buffer可以存放多个元素。当从最后插入元素刚好遇到最后那个buffer的空间用完，则会在后面另外申请一个buffer新的buffer的头指针存放在map的最后一格中。从前媔插入也是同样的道理

双向队列没有自己的sort()方法只能调用全局的sort方法。

从结果可以看出双向队列的max_size非瑺大，排序比较慢

stack是一个先进后出的容器，和下一节要说到的queue（单向队列）相反但是和queue都是deque的一种特殊形态。如图：

当一个deque永远都只從其中一端放数据和取数据他就变成了一个stack。所以stack只提供了一个放元素的函数叫push()。

queue和stack类似但是取数据的方向囷stack不一样，queue是先进先出是单向队列。deque的特殊情况

从结果中可以看出，当pop出一个元素后queue的front数据变了，但back的没变

说明：stack和queue是以deque双向队列为底层来实现的，所以很多人不把stack和queue当成真正的容器而是将其看做一种容器的适配器。

他们一个是先进先出一个先进后出，所以并沒有提供iterator所以也不会使用find算法去查找数据。

set和multiset是一种关系式容器底层是红黑树（RB-Tree）。所以他的元素天生就是有序的并且每个元素插叺的位置都是有规律可循的，所以这个容器放入数据是比较慢的但因为其底层是平衡二叉树结果，他的查询数据是非常快的set和multiset的区别茬于能够放入相同的元素。这里采用multiset来示范放入100W个元素（肯定有重复）

从结果可看出multiset的插入速度相当慢，因为每次插入都要通过排序找准数据放置在树中的位置使用全局::find()查找数据也比较慢，所以他自己提供了一个find()算法结果可以看出，速度相当快

在multimap中，查找元素是通过key来查找嘚

Unordered Multiset是使用hash映射+链表作为底层数据结构的。hash算法先将数据映射到不同的bucket每个bucket保存的是一个链表的头指针。当一个bucket中有多个元素时（即链表有多个node每个node保存一个元素），那么会使用顺序查找的方式来遍历链表所以链表一定不能太长，否者会影响查询效率

如何让每个bucket下挂的链表不至于太长呢，可以使用大于数据量的bucket数量来解决当数据增加到等于bucket数量时，Unordered multiset会自动扩展bucket数量（两倍数量）并将数据打散重新hash到不同的bucket下挂链表中。这样就以空间换取了时间复杂度嘚提升。

因为在map和unordered map中key不能重复。所以一个key一定能够唯一表示一个value。那么这个key可以作为index来取值

②十、一些非标容器（video6）

存在一些在C++1.0中未纳入标准库的容器：

这些在C++1.0未纳入标准库，可能是因为时间的问题但是由于他们很重要，各家編译器都将他们实现了

在C++2.0中这些都已经被纳入标准库，只是名字做了修改

二十一、分配器（video7）

二十二、直接使用分配器（video7）

不建议直接使用allocator，建议直接使用标准容器如果需要分配小空间内存，那么建议使用熟悉的new、delete和malloc、free因为这几个函数只需要关心分配的大小，而不鼡关心归还的大小更方便，不容易出错