STL模板类

容器底层实现

vector

：底层数据结构是数组，支持快速随机访问。
- 使用三个指针分别指向容器对象的起始字节位置，最后一个元素的末尾字节和容器所占内存空间的末尾字节。
- 当前容量用完时，vector启用现在的内存空间，重新申请更大的内存空间，将旧内存空间中的数据，按原有顺序移动到新的内存空间，最后将旧的内存空间释放。
list

：底层数据结构为双向链表，支持快速增删。
- 各元素占用的存储空间（节点）是独立的、分散的，它们之间的线性关系通过指针来维持。
- 双向链表的各个节点中存储的不仅仅是元素的值，还应包含 2 个指针，分别指向前一个元素和后一个元素。
deque

（双向队列）：是一种双开口的分段连续空间的数据结构，支持首尾（中间不能）快速增删，也支持随机访问。
- 底层数据结构为一个中央控制器和多个缓冲区，deque的迭代器包括4个内容：迭代器当前所指元素，此迭代器所指的缓冲区的头，缓冲区尾，管控中心。
- 可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。
- deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：
stack

：底层一般使用deque实现（也可能用list），不可随机访问，也不提供迭代器。
queue

：底层一般使用deque实现（也可能用list），不可随机访问，也不提供迭代器。（stack和queue其实是适配器,而不叫容器，因为是对容器的再封装）

priority_queue

：使用vector和deque来存储元素，堆heap为处理规则来管理底层容器的实现。

// 默认优先输出大数据
priority_queue<int> pq;
priority_queue<int, vector<int>, less<int>> pq;

// 优先输出小数据
priority_queue<int, vector<int>, greater<int>> pq;

// 自定义输出，优先输出x小的，x相同优先输出y小的
struct cmp{
    bool operator()(Node a, Node b){
        if(a.x == b.x) return a.y>b.y;
        return a.x>b.x;
    }
};

priority_queue<Node, vector<Node>, cmp>pq;

set

：底层数据结构为红黑树，有序，不重复。

set<int> s; 
// 返回一对迭代器，分别表示第一个大于或等于给定关键值的元素(lower_bound)和 第一个大于给定关键值的元素(upper_bound)。
// 返回类型是pair。如果哪个不存在，值等于end()。
auto pr = s.equal_range(3);
cout << *pr->first << endl;
cout << *pr->second << endl;
auto lp = s.lower_bound(12);
auto lp = s.upper_bound(12);

// 删除定位器iterator指向的值
erase(iterator);
//删除定位器first和second之间的值
erase(first,second);
//删除键值key_value的值
erase(key_value);

multiset

：底层数据结构为红黑树，有序，可重复。

multiset<int> ms = { 1,2,6,2,4,3,3,8 };
// 返回元素3的个数
ms.count(3);

map

：底层数据结构为红黑树，有序，不重复。
multimap

：底层数据结构为红黑树，有序，可重复。
unordered_map

：底层数据结构为hash表，无序，不可重复。
hash_set

：底层数据结构为hash表，无序，不重复。
hash_multiset

：底层数据结构为hash表，无序，可重复。
hash_map

：底层数据结构为hash表，无序，不重复。
hash_multimap

：底层数据结构为hash表，无序，可重复。

不同操作的时间复杂度

map, set, multimap, multiset均使用红黑树实现，不同操作的时间复杂度近似为O(logN)。
hash_map, hash_set, hash_multimap, hash_multiset使用哈希表实现，不同操作的时间复杂度为O(1)，最坏情况是O(N)。
list操作函数的时间复杂度都为O(1)。
vector和deque操作函数insert和erase时间复杂度为O(n)，其他都为O(1)。

对比

unordered_map和hash_map

本质是相同的，一般选择使用unordered_map的原因：
- 因为标准化的推进，unordered_map原来属于boost分支和std::tr1中，而hash_map属于非标准容器。
- 两者速度差不多，但是unordered_map支持string做key，也可用复杂对象作为key。
map和unordered_map
- map：
  - 优点：map内部实现是红黑树，有序性是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作，其复杂度为logN。
  - 缺点：空间占用率高，因为每一个节点都需要额外保存父节点，孩子节点以及红/黑性质，使得每一个节点都占用大量的空间。
  - 适用：对于那些有顺序要求的问题，用map会更高效一些。
- unorder_map
  - 优点：内部实现是哈希表，因此其查找速度非常的快，复杂度为O(1)。
  - 缺点：更改哈希表的大小，重构哈希表比较耗费时间。
  - 适用：对于查找问题，unordered_map会更加高效一些。
hash_map与map
- 存储结构：hash_map以hashtable为底层，而map以RB-TREE为底层。
- 构造函数：hash_map需要hash function和等于函数，而map需要比较函数。
- 总的说来，hash_map查找速度比map快，而且查找速度基本和数据量大小无关，属于常数级别。而map的查找速度是logn级别。但不一定常数就比log小，而且hash_map还有hash function耗时。
- 适用情况：如果考虑效率，特别当元素达到一定数量级时，用hash_map。考虑内存，或者元素数量较少时，用map。
unorder_map, map和hash_map
- 运行效率方面：unordered_map最高，hash_map其次，而map效率最低单提供了有序的序列。
- 占用内存方面：hash_map内存占用最低，unordered_map其次(数量少时优于hash_map），而map占用最高。
vector和list

：均为序列式容器，其中的元素不一定有序，但都可以被排序。
- 适用对象：vector适用对象数量变化少，简单对象，随机访问元素频繁的情况；list适用对象数量变化大，对象复杂，插入和删除频繁的情况。
- 存储方式： vector使用连续的内存空间进行存储；list使用非连续的内存空间进行存储。
vector, list, deque适用情况
- 如果需要高效的随即存取，而不在乎插入和删除的效率，使用vector。
- 如果需要大量的插入和删除，而不关心随即存取，则应使用list。
- 如果需要随即存取，而且关心两端数据的插入和删除，则应使用deque。
set和map
- 联系：Map,Set属于标准关联容器，底层数据结构使用红黑树；时间复杂度均为红黑树的时间复杂度，插入删除查找近似为O(logN)。
- 适用对象：map适合存储一个数据字典，并要求方便地根据key找value；set适合查找一个元素是否在某集合内存中。
- 存储方式：Set节点只含有Key，Key不重复；Map节点有一个Key和Value两个元素,Key不重复,Value可以重复。
- 元素改变：set不能直接改变元素值。因为这样会打乱原有的顺序。要改变元素只能先删除旧元素，再插入新元素。存取元素只能通过迭代器，从迭代器的角度看，元素值是常数。map可以通过key改变value的值。

PS：看问题使用哪个容器，一般权衡查找速度，数据量和内存使用。

其他

vector的扩容机制及优化方法
- 扩容机制：每当capacity() == size()，就以1.5/2倍自动扩容（该数字根据编译器变化）；可以使用reserve手动扩容。
- 扩容倍数：使用2倍扩容时，每次扩容，我们释放掉的内存连接起来的大小，都小于即将要分配的内存大小。而1.5倍扩容到一定程度后，可以复用之前释放的碎片空间。
- 优化方法：vector的初始的扩容方式代价太大,初始扩容效率低，需要频繁增长，不仅操作效率比较低，而且频繁的向操作系统申请内存容易造成过多的内存碎片，所以这个时候需要合理使用resize()和reserve()方法提高效率减少内存碎片。
- 内存回收：使用clear()和erase()两个函数只是清空元素，但不回收内存。先使用clear()再使用swap()，释放空间并且回收内存。
STL的迭代器iterator
- iterator相当于指向节点的指针，指向的内存没有变，迭代器就不会失效。
- 而对于vector，每次删除或插入后，iterator有可能失效，因为vectoe可能申请了新的内存，原内存被释放了。
为何map和set的插入删除效率比其他序列容器高？因为不需要内存拷贝和内存移动。
STL中排序算法sort

的实现：STL中的sort()，在数据量大时，采用快排quicksort，分段递归；一旦分段后的数量小于某个门限值，改用插入排序Insertion sort，避免quicksort深度递归带来的过大的额外负担，如果递归层次过深，还会改用heapsort(堆排序)。
vector的resize和reserve
- resize两种用法
  - resize(n)：调整容器的长度大小，使其能容纳n个元素；如果n小于容器的当前的size，则删除多出来的元素；否则，添加采用值初始化的元素。
  - resize(n，t)：多一个参数t，将所有新添加的元素初始化为t。
- reserve只有一种用法reserve(n)，预分配n个元素的存储空间。
- resize是改变容器的大小，并且创建对象，因此，调用这个函数之后，就可以引用容器内的对象了，因此当加入新的元素时，用operator[]操作符，或者用迭代器来引用元素对象。
- reserve是容器预留空间，但并不真正创建元素对象，在创建对象之前，不能引用容器内的元素，因此当加入新的元素时，需要用push_back()/insert()函数。
vector的capacity和size
- capacity()指容器在必须分配新存储空间之前可以存储的元素总数，可以说是预分配存储空间的大小。
- size()函数返回实际元素的数量。

数据结构

平衡二叉树
- 是二叉搜索树，中序遍历得到有序集合。
- 左右两个子树的高度差(平衡因子)的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
- 平衡因子（平衡度）：结点的平衡因子是结点的左子树的高度减去右子树的高度。因此平衡二叉树就是每个结点的平衡因子都为 1、－1、0 的二叉排序树。
- 平衡二叉树的目的是为了减少二叉查找树层次，提高查找速度。
- 时间复杂度：O(logN)，查找快，插入和删除较慢。
- 增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
红黑树

：弱平衡二叉树
- 通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍。
- 节点着色规则
  - 每个节点非红即黑
  - 根节点是黑的
  - 每个叶节点（叶节点即树尾端NULL指针或NULL节点，被称为黑哨兵）都是黑的
  - 如果有一个节点是红的，那么其子节点都是黑的
  - 对于任意节点，其到叶子节点的每条路径都包含相同数目的黑色节点
- 由于它的设计，任何不平衡都会在三次旋转之内解决。
- 时间复杂度：O(logN)，查找、插入和删除都较快。
平衡二叉树和红黑树

适用情况
- 由于维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。
- 相对于要求严格的AVL树来说，红黑树的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，我们就用红黑树。
- 如果应用场景中对插入删除不频繁，只是对查找要求较高，那么AVL还是较优于红黑树。
哈希表

：是一种根据设定的映射函数f(key)将一组关键字映射到一个有限且连续的地址区间上，并以关键字在地址区间中的“像”作为元素在表中的存储位置的一种数据结构。
哈希（散列）函数
- 直接定址法：关键字或关键字的某个线性函数值就是哈希地址。
- 除数取余法：取关键字被某个值p取余，得到哈希地址。
- 数字分析法：当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为哈希地址。仅适用于所有关键字都已知的情况下，根据实际应用确定要选取的部分，尽量避免发生冲突。
- 平方取中法：先计算出关键字值的平方，然后取平方值中间几位作为哈希地址。
- 随机数法：选择一个随机函数，把关键字的随机函数值作为它的哈希值。通常当关键字的长度不等时用这种方法。
- 折叠法：将关键字分为位数相同的几部分，然后取这几部分的叠加和（舍去进位）作为哈希地址。用于关键字位数较多，并且关键字中每一位上数字分布大致均匀。
哈希冲突

解决方法
- 开放定址法
  
  ：当关键字的哈希地址p发生冲突时，以p为基础，产生另一个哈希地址p1，p1再重复就继续产生，直到不冲突。
  - 线性探测再散列：如果发生冲突，就往后找没有元素的位置。
  - 平方探测再散列：如果发生冲突，放到(冲突+1平方)的位置，如果还发生冲突，就放到(冲突-1平方)的位置；如果还有人就放到(冲突+2平方)的位置，以此类推，要是负数就倒序数。
  - 双重散列法：使用了两个散列函数，探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+h1(d)], T[d + 2*h1(d)]，…，等。
- 链地址法
  
  ：将所有关键字为同义词的结点链接在同一个单链表中。
- 再哈希法
  
  ：同时构造多个不同的哈希函数，当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，增加了计算时间。
- 建立一个公共溢出区
  
  ：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

排序算法

时间空间复杂度

在这里插入图片描述

排序原理

插入排序：每次将一个待排序的数据，跟前面已经有序的序列的数字一一比较找到自己合适的位置，插入到序列中，直到全部数据插入完成。
冒泡排序：通过交换使相邻的两个数变成小数在前大数在后，这样每次遍历后，最大的数就“沉”到最后面了。重复N次即可以使数组有序。
- 改进1：在某次遍历中如果没有数据交换，说明整个数组已经有序。因此通过设置标志位来记录此次遍历有无数据交换就可以判断是否要继续循环。
- 改进2：记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。
选择排序：数组分成有序区和无序区，初始时整个数组都是无序区，然后每次从无序区选一个最小的元素直接放到有序区的最后，直到整个数组变有序区。
堆排序：通过插入和删除完成排序。堆的插入和删除非常类似直接插入排序，只不是在二叉树上进行插入过程。
桶排序：第一步根据数字的个位分配到每个桶里，在桶内部排序，然后将数字再输出（串起来）；然后根据十位分桶，继续排序，再串起来。直至所有位被比较完，所有数字已经有序。

适用情况和其他问题

排序算法的

性能取决于什么

？

取决于算法中比较和交换的次数以及是否需要额外的空间用于存放临时值（如果数据很大会遇上空间不够的问题就会出错）。
什么样的排序算法是

稳定

的？
- 稳定其实就是在比较过程中，关键字（数组元素的值）相同的两个元素不会发生交换。有时候比较的关键字不是那些对象的唯一属性，也许比较的关键字相同但是对象的其他属性不同，如果这时交换了关键字（数组元素的值）相同的两个对象，那么对象的其他属性也会跟着变化，那就不好了。
- 判断的方法
  
  其实就是如果排序是在相邻两元素间进行，就不可能发生关键字（数组元素的值）相同的两个元素交换的事情，而如果是跳跃（间隔）的排序，显然算法并不知道会不会有相同的关键字在当前元素的前面或后面，它就会交换。
适用情况
- 冒泡排序几乎是最差的排序。
- 快排的最坏情况
  
  ，这个时候的时间复杂度是O(n^2)，且递归深度为n,所需的占空间为O(n)。
- 堆排序不会出现快排那样最坏情况，且堆排序所需的辅助空间比快排要少，但是这两种算法都不是稳定的，要求排序时是稳定的，可以考虑用归并排序。
- 从大量的N个数据中
  
  找最大/最小的k个元素
  
  使用堆排序。
- 随机数排序时，当数据集非常少时，插入类排序要比比较类排序快。数据量较少不适合用递归的排序方法。
- 基本有序
  
  数据排序时，在数据量较少的情况下，插入排序胜过其他排序。
- 不管数据是随机还是基本有序，
  
  数据量越大
  
  ，快排的优势越明显。
- 数据
  
  随机分布
  
  的时候，快速排序平均时间最短。

其他问题

求海量数据（10亿）中最小的10000个数据。
- 先拿10000个数建堆，然后一次添加剩余元素，如果大于堆顶的数（10000中最小的），将这个数替换堆顶，并调整结构使之仍然是一个最小堆，这样，遍历完后，堆中的10000个数就是所需的最大的10000个。建堆时间复杂度是O（mlogm），算法的时间复杂度为O（nmlogm）（n为10亿，m为10000）。
- 优化的方法：可以把所有10亿个数据分组存放，比如分别放在1000个文件中。这样处理就可以分别在每个文件的10^6个数据中找出最大的10000个数，合并到一起在再找出最终的结果。
- 较好的解法：分治+Trie树/hash+小顶堆。
计算机怎么计算三角函数值
- 泰勒公式

原文链接：https://blog.csdn.net/almost_afei/article/details/115101979

算法数据结构汇总

目录

STL模板类

容器底层实现

不同操作的时间复杂度

对比

其他

数据结构

排序算法

时间空间复杂度

排序原理

适用情况和其他问题

其他问题

目录

STL模板类

容器底层实现

不同操作的时间复杂度

对比

其他

数据结构

排序算法

时间空间复杂度

排序原理

适用情况和其他问题

其他问题

你可能也喜欢