C++_STL源码阅读：算法篇 Algorithms

秒速五厘米 2022-05-25 13:52 176阅读 0赞

源码路径：STLport-5.2.1/stlport/stl

### numeric: ###

*  accumalate
 *  inner\_product
 *  partial\_sum
 *  adjacent\_differnence: 相邻两个元素之间的差值or加法
 *  power：计算x的n次方
 *  iota：并非属于STL，只是一个扩展，是的某个指定区间，从指定值\_val开始逐元素递增

其中，power算法可以简单讨论下：

*  方法1： 循环n次，x连乘，但这样比较低效， log(n)
 *  方法2： 二分，递归，但栈溢出
 *  方法3： 如STL实现，是对方法2的非递归写法；其中，n每次迭代后减半

### algobase ###

### algo： ###

*  for\_each 迭代遍历
 *  count\_if
 *  adjacent\_find 相邻两个相等元素的查找
 *  查找系列：find\_first\_of search\_n
 *  swap\_ranges
 *  transform
 *  replace | replace\_if | replace\_copy | replace\_copy\_if
 *  generate | generate\_n
 *  删除系列： remove | remove\_copy | remove\_if | remove\_copy\_if 注意，执行后内存未释放，只是把未删除元素compact提前了，即last指针前移，末尾几个元素还是占用了空间，即vector.size不变
 *  unique | unique\_copy
 *  reverse | rotate | reverse\_copy
 *  random系列，数据shuffle用：random\_sample | random\_shuffle
 *  partition 这是为了快速排序做准备的func，即“划分排序”是用到划分嘛
 *  sort partial\_sort 见下面
 *  merge | merge\_sort 归并排序

### set: ###

*  set\_union 取并集
 *  set\_intersection 取交集
 *  set\_difference 差集
 *  set\_symmetric\_difference A并B-A交B

排列组合：

*  next\_permutation 返回bool
 *  prev\_permutation
 *

### heap: ###

*  is\_heap

### other: ###

### 二分查找： ###

*  lower\_bound：第一个出现的位置，也即位置的下界
 *  upper\_bound：最后出现的位置，也即位置的上界
 *  equal\_range：基于lower\_bound，返回查找的目标区间
 *  binary\_search : 基于lower\_bound，返回是否存在，bool|false

### Sort： ###

*  partial\_sort 划分排序，就是快速排序； 怎么选pivot呢？采用median-of-three方法，即开头、中间、结尾三个元素，值大小处于中间的那个。
 *  insert\_sort：元素较少时或者大部分有序时，效率较高；
 *  introspective\_sort：1996，David R. Musser提出；可以自适应地从partial\_sort切换到heap\_sort；

Merge：归并排序

排列组合：

*  next\_permutation：直接在输入的vector原地生成新的排列组合；如果没有新的生成，返回false；
 *  pre\_permutation