算法笔记_什么是数据结构_向量vector

P34 https://www.bilibili.com/video/av75509584?p=34

基本概念 抽象数据类型(ADT) vs 数据结构

汽车使用手册，在某种意义上，就是一种ADT，用户只需要关系如何使用它，不必关系内部的实现，内部的实现由生产者决定。

算法中，将向量的元素对应的索引，称之为“秩”。

disordered(): 返回逆序对的个数；若返回0，说明逆序对为0，该序列为有序序列。

search(X): 返回不超过X的最大的元素的秩（索引）。若X小于vector中最小的值，则返回-1。

自定义一个 vector 数据结构

向量源自，并且是脱胎于数组。

统一的采用模板式的方法，可以使数据结构的定义非常的规范，更重要的是，此后，他们可以互相的融合、组合，便捷的搭建更为复杂的数据结构。

存储空间扩容

采用加倍扩容

为什么不采用固定值扩容？

因为固定大小扩容的时间成本较大，平均分摊到每次，需要的时间复杂度为O(n)；

而倍增式的扩容，平均每次需要的时间复杂度为O(1)。详细分析如下。

总结: 倍增策略，是在空间上做出了一些牺牲（使用率仍大于50%），来换取时间复杂度上的巨大收益。

平均复杂度 vs 分摊复杂度

整体考虑连续操作。

无序向量

比对：能够比较元素之间是否相等。

元素  [ ] 访问

采用 [ ] 的方式访问向量元素时，至关重要的方式是 “秩” 的概念；这种方式也称之为 “循秩访问”。

元素插入

插入注意点：移动需要移动的元素时，是从后往前依次的移动顺序。

元素删除

区间删除注意点：移动需要移动的元素时，是从前往后依次的移动顺序。原因：避免因为移动区间有重叠部分，导致无意间元素被覆盖。

  

遍历

通过函数对象的方式，对向量元素进行遍历的方法，通用性更强。

重载一个结构体的 “ ( ) ” 操作符，使之看上去或者说使用上去，类似于一个函数。

有序向量

比较：元素之间谁大谁小。

找出向量中的逆序对

去除有序向量中的重复元素

复制元素：直接复制到位，而不是每发现一个重复的，删除一个。

二分查找

二分查找：减而治之版

建议小技巧：以下算法，在比较时，用的都是 “