STL基础--算法（已排序数据的算法，数值算法）
2024-03-19 15:45:24
已排序数据的算法
- Binary search, merge, set operations
- 每个已排序数据算法都有一个同名的更一般的形式
vector vec = {8,9,9,9,45,87,90}; // 7 items
1. 二分法搜索
// 搜索元素
bool found = binary_search(vec.begin(), vec.end(), 9);
vector<int> s = {9, 45, 66};
bool found = includes(vec.begin(), vec.end(), // Range #1
s.begin(), s.end()); // Range #2
// s的所有元素是否都在vec中
// vec和s都必须已排序
// 搜索位置
itr = lower_bound(vec.begin(), vec.end(), 9); // vec[1]
// 搜索第一个可插入的位置，插入后仍然是排序的
itr = upper_bound(vec.begin(), vec.end(), 9); // vec[4]
// 寻找最后一个可插入的位置，插入后仍然保持排序
pair_of_itr = equal_range(vec.begin(), vec.end(), 9);
// 返回第一个和最后一个位置
2. 合并
vector<int> vec = {8,9,9,10};
vector<int> vec2 = {7,9,10};
merge(vec.begin(), vec.end(), // Input Range #1
vec2.begin(), vec2.end(), // input Range #2
vec_out.begin()); // Output
//vec和vec2都必须已排序
// 重复的元素保留
// vec_out: {7,8,9,9,9,10,10}
vector<int> vec = {1,2,3,4,1,2,3,4,5} // vec中两部分都已排序
inplace_merge(vec.begin(), vec.begin()+4, vec.end());
// vec: {1,1,2,2,3,3,4,4,5}
3. 集合操作
// - 输入数据都必须已排序
// - 结果也是排序的
vector<int> vec = {8,9,9,10};
vector<int> vec2 = {7,9,10};
vector<int> vec_out[5];
set_union(vec.begin(), vec.end(), // Input Range #1
vec2.begin(), vec2.end(), // input Range #2
vec_out.begin()); // Output
// 并集，两者都有的元素在结果中只保留一个
// vec_out: {7,8,9,9,10}
set_intersection(vec.begin(), vec.end(), // Input Range #1
vec2.begin(), vec2.end(), // input Range #2
vec_out.begin()); // Output
// 交集，两者都有的元素才保存在结果中vec_out
// vec_out: {9,10,0,0,0}
vector<int> vec = {8,9,9,10};
vector<int> vec2 = {7,9,10};
vector<int> vec_out[5];
set_difference(vec.begin(), vec.end(), // Input Range #1
vec2.begin(), vec2.end(), // input Range #2
vec_out.begin()); // Output
// 差集，vec有且vec2没有的元素保存
// vec_out: {8,9,0,0,0}
set_symmetric_difference(vec.begin(), vec.end(), // Input Range #1
vec2.begin(), vec2.end(), // input Range #2
vec_out.begin()); // Output
// 交集的补集，只有其中1方有的元素
// vec_out: {7,8,9,0,0}
数值算法
- Accumulate, inner product, partial sum, adjacent difference
1. 累积
int x = accumulate(vec.begin(), vec.end(), 10); //默认 +
// 10 + vec[0] + vec[1] + vec[2] + ...
int x = accumulate(vec.begin(), vec.end(), 10, multiplies<int>()); //自定义运算
// 10 * vec[0] * vec[1] * vec[2] * ...
2. 内积
//vector<int> vec = {9,60,70,8,45,87,90}; // 7 items
int x = inner_product(vec.begin(), vec.begin()+3, // Range #1
vec.end()-3, // Range #2
10); // Init Value
// 10 + vec[0]*vec[4] + vec[1]*vec[5] + vec[2]*vec[6]
int x = inner_product(vec.begin(), vec.begin()+3, // Range #1
vec.end()-3, // Range #2
10, // Init Value
multiplies<int>(),
plus<int>());
// 10 * (vec[0]+vec[4]) * (vec[1]+vec[5]) * (vec[2]+vec[6])
3. 部分和
partial_sum(vec.begin(), vec.end(), vec2.begin());
// vec2[0] = vec[0]
// vec2[1] = vec[0] + vec[1];
// vec2[2] = vec[0] + vec[1] + vec[2];
// vec2[3] = vec[0] + vec[1] + vec[2] + vec[3];
// ...
partial_sum(vec.begin(), vec.end(), vec2.begin(), multiplies<int>());
4. 邻差
adjacent_difference(vec.begin(), vec.end(), vec2.begin());
// vec2[0] = vec[0]
// vec2[1] = vec[1] - vec[0];
// vec2[2] = vec[2] - vec[1];
// vec2[3] = vec[3] - vec[2];
// ...
adjacent_difference(vec.begin(), vec.end(), vec2.begin(), plus<int>());
最新文章
- 学习微信小程序之css6
- ZOJ Problem Set - 1109 Language of FatMouse
- 【Swift学习】Swift编程之旅（三）
- ASP.NET MVC使用jQuery实现Autocomplete
- stringstream操纵string小总结
- 利用apply和arguments复用方法
- HTML5火焰文字特效DEMO演示---转载
- Erlang-基础篇
- Java 容器（集合）
- 深入理解ASP.NET的内部运行机制(转)
- 【风马一族_Android】Android 前端内容1
- 前端自动化工具:Grunt使用教程
- 更改cmd语言（chcp）
- json datetime转换问题
- 分布式配置管理--百度disconf搭建过程和详细使用
- Oracle100w数据大表割接
- Python算法与数据结构--求所有子数组的和的最大值
- numpy的基础运算-【老鱼学numpy】
- oracle存储过程 out cursor
- Spring Boot 2 (六)：使用 Docker 部署 Spring Boot 开源软件云收藏