-
C++标准库算法整理
目录
8.2、std::lexicographical_compare
8.3、std::lexicographical_compare_three_way
11.4、std::set_symmetric_difference
15.2、std::max_element、std::min_element
25.2.2、std::transform_exclusive_scan
25.2.3、std::transform_inclusive_scan
1、数值操作
1.1、std::accumulate
元素累加。
1.2、std::inner_product
计算两个范围的内积。
1.3、std::partial_sum
累加求和。
1.4、std::exclusive_scan
序列的累计运算。此函数接受一个范围的输入序列，并将计算结果存储到另一个容器中。它通过对每个元素应用一个二元操作符，将当前元素与其前面的所有元素进行计算，并将计算结果累计到输出容器中。
- int main(int argc, char *argv[])
- {
- QVector<int> vec = {2,3,4,5,6};
- QVector<int> result(vec.size());
- //第一个元素就是初始值1， 从第二个开始依次乘以前面的数，最后一个元素不进行计算;前一次的结果会做为后一次的第一个参数
- std::exclusive_scan(vec.begin(), vec.end(), result.begin(), 1, [](int a,int b){return a * b;});
- qDebug() << result;//1 1*2 1*2*3 1*2*3*4 1*2*3*4*5
- }
1.5、std::inclusive_scan
对一个序列中的元素进行累积操作。结果是计算出一个新的序列，新序列中的每个元素都是原序列中当前位置以及之前位置的元素的累积和。
- #include
- #include
- #include
- int main(int argc, char *argv[])
- {
- QVector<int> numbers = {1, 2, 3, 4, 5};
- QVector<int> result(numbers.size());
- std::inclusive_scan(numbers.begin(), numbers.end(), result.begin());
- // 使用 qDebug 输出每个元素的累积和
- qDebug() << "累积和：";
- for (const auto& num : result) {
- qDebug() << num;
- }
- }
- /*
- 累积和：
- 1
- 3
- 6
- 10
- 15
- */
1.6、std::reduce
在范围内进行归约操作，并返回结果。（将一系列的输入元素通过重复应用某个操作符将它们合并成一个简单的结果）它可以用于对一个范围内的元素进行求和、求积、最大值、最小值等操作。
- //例1：求和
- QVector<int> numbers = {1, 2, 3, 4, 5};
- int sum = std::reduce(numbers.begin(), numbers.end(), 0);
- qDebug() << "Sum:" << sum;
- //例2：找到 QStringList 中最长的字符串
- QString longest = std::reduce(words.begin(), words.end(), QString(),[](const QString ¤t, const QString &next)
- {
- return current.length() > next.length() ? current : next;
- });
- //例3：将 QMap 的值相加
- int totalScore = std::reduce(scores.begin(), scores.end(), 0,[](int current, const QString &, int score)
- {
- return current + score;
- });
2、相邻元素
2.1、std::adjacent_difference
计算指定范围内的相邻元素的差值，并将结果存储到另一个范围中。
2.2、std::adjacent_find
在指定范围内查找相邻的重复元素，并返回第一个匹配的元素的迭代器。
2.3、std::unique
移除指定范围内的连续重复元素，返回一个新的范围。
2.4、std::unique_copy
类似于 std::unique，但是它将移除的重复元素复制到另一个容器。
3、是否满足条件
3.1、std::all_of
判断指定范围内的所有元素是否都满足指定条件。
3.2、std::any_of
判断指定范围内的任意一个元素是否满足指定条件。
3.3、std::none_of
判断指定范围内的所有元素是否都不满足指定条件。
4、二分查找
4.1、std::binary_search
在已排序范围内进行二分查找，判断指定的值是否存在。
4.2、std::bsearch
与 std::binary_search 功能相似，用于在 C 风格数组中进行二分查找。
- int compare(const void* a, const void* b) {
- return (*(int*)a - *(int*)b);
- }
- int main(int argc, char *argv[])
- {
- int arr[] = {2, 5, 8, 12, 18, 23, 28, 32};
- int key = 18;
- int size = sizeof(arr) / sizeof(arr[0]);
- int* found = (int*)std::bsearch(&key, arr, size, sizeof(int), compare);
- if(found != nullptr) {
- qDebug() << "在数组中找到元素！"<<*found;
- } else {
- qDebug() << "在数组中未找到元素！";
- }
- return 0;
- }
- //在数组中找到元素！ 18
4.3、std::lower_bound
获取序列中大于等于某元素的第一个元素。
4.4、std::upper_bound
与std::lower_bound类似。获取序列中大于某元素的第一个元素。
4.5、std::equal_range
在已排序范围内查找某个值的等值区间。
5、限制范围
5.1、std::clamp
将指定的值限制在给定的范围内，返回最接近的边界值。c++17以上才支持。
- #include
- int main(int argc, char *argv[])
- {
- int value = 20;
- int minValue = 5;
- int maxValue = 15;
- int clampedValue = std::clamp(value, minValue, maxValue);
- qDebug() << "范围限制后的值：" << clampedValue;
- return 0;
- }
6、复制
6.1、std::copy
将指定范围内的元素复制到另一个范围中。
6.2、std::copy_if
将满足指定条件的元素从指定范围中复制到另一个范围中。
6.3、std::copy_backward
将指定范围内的元素逆向复制到另一个范围中。
6.4、std::copy_n
将指定数量的元素从指定范围复制到另一个范围中。
7、计数
7.1、std::count
计算指定范围内等于给定值的元素的个数。
7.2、std::count_if
计算指定范围内满足给定条件的元素的个数。
8、比较
8.1、std::equal
判断两个范围内的元素是否相等。
8.2、std::lexicographical_compare
按字典顺序比较两个范围。
8.3、std::lexicographical_compare_three_way
与std::lexicographical_compare类似，二者区别：
- std::lexicographical_compare 比较两个范围的元素，并确定它们在字典序上的相对顺序。它返回一个布尔值，指示第一个范围是否在字典序上小于第二个范围。
- std::lexicographical_compare_three_way 进行三路比较，比较两个范围的元素在字典序上的关系。它返回一个三路比较的结果，表示两个范围在字典序上的关系：小于、等于或大于。
9、填充元素
9.1、std::fill
用指定的值填充给定范围内的元素。
9.2、std::fill_n
用指定的值填充给定范围内的前 n 个元素。
9.3、std::generate
用生成器函数生成给定范围内的元素。
- #include
- #include
- #include
- #include
- int main(int argc, char *argv[])
- {
- QVector<int> numbers(10); // 定义一个包含10个元素的向量
- std::random_device rd; // 随机设备，用于生成随机数种子
- std::mt19937 gen(rd()); // 随机数引擎，用于生成随机数
- std::generate(numbers.begin(), numbers.end(), [&gen]() {
- return gen() % 100; // 生成0-99的随机数
- });
- for (const auto& num : numbers) {
- std::cout << num << " ";
- }
- std::cout << std::endl;
- }
9.4、std::generate_n
用生成器函数生成给定范围内的前 n 个元素。
9.5、std::iota
用依次递增的值填充给定范围。
10、查找、搜索
10.1、std::find
查找指定值的元素。
10.2、std::find_if
查找满足特定条件的元素。
10.3、std::find_if_not
查找不满足特定条件的元素。
10.4、std::find_end
查找最后一次出现另一个范围的位置。
10.5、std::find_first_of
查找第一个与指定范围中的任何一个元素匹配的元素。
10.6、std::search
搜索一个子序列，并返回指向第一个匹配子序列的迭代器。
10.7、std::search_n
搜索连续出现指定数量的某个值，并返回指向这段连续值的迭代器。
10.8、std::mismatch
在两个范围中查找第一个不匹配的元素，并返回一个包含指向两个范围中不匹配元素的迭代器的 std::pair 对象。
- int main(int argc, char *argv[])
- {
- QVector<int> vec1 = {1, 2, 3, 4};
- QVector<int> vec2 = {1, 2, 5, 4, 6};
- auto result = std::mismatch(vec1.begin(), vec1.end(), vec2.begin());
- if (result.first != vec1.end() && result.second != vec2.end()) {
- qDebug() << "第一个不匹配的元素:";
- qDebug() << "vec1: " << *(result.first);
- qDebug() << "vec2: " << *(result.second);
- } else {
- qDebug() << "范围没有不匹配的元素";
- }
- }
11、集合操作
11.1、std::includes
是否包含。
11.2、std::set_difference
差集。
11.3、std::set_intersection
交集。
11.4、std::set_symmetric_difference
对称差集。
11.5、std::set_union
并集。
12、合并
12.1、std::inplace_merge
将一个序列中两个有序的子序列合并成一个有序的子序列。
12.2、std::merge
将两个已排序的范围合并为一个已排序的范围。
13、堆
堆是一个完全二叉树：堆中的所有层级都是完全填满的，最后一层可以部分填满，而且所有节点都尽可能靠左排列。
堆中每个节点的值都满足堆特性：即每个节点的值都大于或小于它的子节点（取决于堆是最大堆还是最小堆）。
根据堆特性的不同，堆可以分为两种类型：
- 最大堆（Max Heap）：在最大堆中，每个节点的值都大于或等于其子节点的值。因此，根节点是堆中的最大值。
- 最小堆（Min Heap）：在最小堆中，每个节点的值都小于或等于其子节点的值。因此，根节点是堆中的最小值。
13.1、std::make_heap
将一个范围转换为堆结构。
13.2、std::is_heap
判断给定范围内的元素是否满足堆的特性。
- #include
- #include
- #include
- int main(int argc, char *argv[])
- {
- QVector<int> vec = {4, 7, 9, 10, 5, 8};
- // 检查整个容器是否满足堆的特性（默认为最大堆）
- bool isHeap = std::is_heap(vec.begin(), vec.end());
- qDebug() << "Is heap:" << (isHeap ? "true" : "false");
- std::make_heap(vec.begin(), vec.end()); // 将容器转换为堆
- // 再次检查整个容器是否满足堆的特性
- isHeap = std::is_heap(vec.begin(), vec.end());
- qDebug() << "Is heap:" << (isHeap ? "true" : "false");
- qDebug() << vec;
- }
13.3、std::push_heap
将指定范围内的元素插入到容器中，并调整剩余元素的顺序，使其符合堆的规则。
13.4、std::pop_heap
将容器中的最大元素移动到末尾，并调整剩余元素的顺序，使其符合堆的规则。
- #include
- #include
- #include
- int main(int argc, char *argv[])
- {
- QVector<int> numbers = {4, 2, 8, 5, 1, 7};
- // 将容器转换为堆
- std::make_heap(numbers.begin(), numbers.end());
- // 插入新元素并调整堆结构
- numbers.push_back(3);
- std::push_heap(numbers.begin(), numbers.end());
- qDebug() << "堆排序前: " << numbers;
- // 弹出堆顶元素（最大值）
- std::pop_heap(numbers.begin(), numbers.end());
- int max = numbers.back();
- numbers.pop_back();
- qDebug() << "弹出的最大值: " << max;
- qDebug() << "堆排序后: " << numbers;
- }
13.5、std::sort_heap
将堆范围转换为有序范围。
- QVector<int> vec = {9, 4, 6, 2, 1, 8, 5};
- std::make_heap(vec.begin(), vec.end()); // 创建一个最大堆
- qDebug() << "最大堆初始状态："<std::sort_heap(vec.begin(), vec.end()); // 使用 sort_heap 进行堆排序qDebug() << "堆排序后的数组："<
13.6、std::is_heap_until
确定范围内的元素是否构成堆，并返回指向不满足堆属性的第一个元素的迭代器。
- QVector<int> vec = {9, 4, 6, 2, 1, 8, 5};
- auto iter = std::is_heap_until(vec.begin(), vec.end());
- if (iter != vec.end()) {
- int index = std::distance(vec.begin(), iter);
- qDebug() << "不满足堆属性的元素位置：" << index;
- } else {
- qDebug() << "整个范围满足堆属性";
- }
第5个元素8不满足小于其父节点6的要求。
14、排列
14.1、std::is_permutation
检查序列是否是另一序列的排列。
14.2、std::next_permutation
重新排列范围内的元素，返回按照字典序排列的下一个值较大的组合。
14.3、std::prev_permutation
和std::next_permutation类似不过每次返回按字典序排序的相对当前序列较小的值。
15、最值
15.1、std::max 、std::min
返回两个值中较大、较小者。
15.2、std::max_element、std::min_element
查找最大值、最小值的位置。
15.3、std::minmax
查找最小和最大元素，返回一个包含最小和最大元素的 std::pair 对象。
15.4、std::minmax_element
同时找到给定范围内的最小和最大元素，返回一个包含指向最小和最大元素的迭代器的 std::pair 对象。
- std::vector<int> vec = {4, 2, 1, 5, 3};
- auto result = std::minmax_element(vec.begin(), vec.end());
- auto minIter = result.first;
- auto maxIter = result.second;
- std::cout << "最小元素: " << *minIter << std::endl;
- std::cout << "最大元素: " << *maxIter << std::endl;
16、移动元素
16.1、std::move
将指定范围内的元素转移到另一个位置。
- #define debug qDebug()<<
- int main(int argc, char *argv[])
- {
- QVector
vec; - for (int i = 0; i < 5; ++i)
- {
- vec.append(QString("xx%1").arg(i)); // 向 QVector 中添加元素
- }
- vec.resize(10); // 调整 QVector 的大小为 10
- debug "vec:" << vec; // 输出 QVector 初始状态
- std::move(vec.begin(), vec.begin() + 2, vec.end() - 2); // 使用 std::move 移动元素
- debug "vec:" << vec; // 输出移动后的 QVector
- }
16.2、std::move_backward
与 std::move 类似，但是它以反向顺序进行移动。用于将元素的值从一个范围内的位置移动到另一个范围内的位置，并保持原始顺序的逆序。
- #define debug qDebug()<<
- int main(int argc, char *argv[])
- {
- QList<int> sourceVec = {1, 2, 3, 4, 5};
- QList<int> destVec;
- destVec.reserve(5); // 预分配内存空间
- for (int i = 0; i < 5; ++i)
- {
- destVec.append(0); // 在列表末尾添加元素
- }
- debug destVec;
- std::move_backward(sourceVec.begin(), sourceVec.end()-1, destVec.end());
- debug sourceVec;
- debug destVec;
- return 0;
- }
17、排序
17.1、不完全排序
17.1.1、std::nth_element
不完全排序。
17.2、部分排序
17.2.1、std::partial_sort
部分排序，使得排序后的前一部分元素符合特定的顺序。
17.2.2、std::partial_sort_copy
部分排序，并将排序结果复制到另一个容器中。
17.3、快速排序
17.3.1、std::qsort
对给定范围内的元素进行快速排序。参数为数组。
17.3.2、std::sort
对指定范围内的元素进行排序。
- #include
- #include
- #include
- bool compare(int a, int b) {
- return a > b; // 降序排序
- }
- int main() {
- std::vector<int> nums = {5, 2, 8, 3, 1};
- // 对容器中的元素进行降序排序
- std::sort(nums.begin(), nums.end(), compare);
- // 输出结果
- for (const auto& num : nums) {
- std::cout << num << " ";
- }
- std::cout << std::endl;
- return 0;
- }
17.4、稳定排序
17.4.1、std::stable_sort
对指定范围内的元素进行稳定排序。
17.5、判断是否有序
17.5.1、std::is_sorted
判断序列是否有序。
17.6、最长有序子序列
17.6.1、std::is_sorted_until
查找初始最长有序子序列。
18、按条件划分
18.1、std::stable_partition
将满足条件的元素放到前面，不满足条件的元素放到后面。
18.2、std::partition
和stable_partition类似，但不会保证结果序列在原来序列的相对顺序，并返回一个指向满足条件的最后一个元素的迭代器。
18.3、std::partition_copy
类似于 std::partition，但是将满足条件和不满足条件的元素分别复制到两个不同的容器中。
18.4、std::partition_point
在已划分的有序区间中查找第一个不满足某个条件的元素。
18.5、std::is_partitioned
检查一个范围是否被划分为满足指定条件的元素和不满足指定条件的元素两个部分。
19、移除
19.1、std::remove
移除指定范围内的元素，返回一个新的范围，其中被移除的元素被放置在范围的末尾。但此函数并不是真正地删除元素，而是将元素移动到范围尾部并返回新的范围。
63.2、std::remove_if
与 std::remove 类似，但是它可以使用一个谓词来决定是否要移除元素。
63.3、std::remove_copy
类似于 std::remove，但是它将移除的元素复制到另一个容器。
63.4、std::remove_copy_if
类似于 std::remove_if，它将移除元素的副本复制到另一个容器。
20、替换
20.1、std::replace
用指定的新值替换给定范围内的所有旧值。
20.2、std::replace_if
类似于 std::replace，但是它可以使用一个谓词来决定是否要替换值。
20.3、std::replace_copy
类似于 std::replace，但是它将替换的副本复制到另一个容器。
20.4、std::replace_copy_if
类似于 std::replace_if，它将替换元素的副本复制到另一个容器。
21、反转元素
21.1、std::reverse
反转给定范围内的元素顺序。
21.2、std::reverse_copy
类似于 std::reverse，但是它将反转的副本复制到另一个容器。
22、循环右移
22.1、std::rotate
将给定范围内的元素循环右移。
22.2、std::rotate_copy
类似于 std::rotate，但是它将循环右移的副本复制到另一个容器。
23、随机操作
23.1、随机采样
23.1.1、std::sample
从指定的范围中随机选择一定数量的元素，并将选中的元素存储到另一个容器中。
- #include
- #include
- #include
- #include
- int main(int argc, char *argv[])
- {
- QVector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
- QVector<int> sampledNumbers(5); // 存储抽样结果的容器
- // 随机数引擎和分布器
- std::random_device rd;
- std::mt19937 gen(rd());
- // 执行抽样
- std::sample(numbers.begin(), numbers.end(), sampledNumbers.begin(), 5, gen);
- // 输出抽样结果
- qDebug() << "Sampled numbers:"<}
23.2、随机重排
23.2.1、std::shuffle
随机重新排列给定范围内的元素，可以指定自定义的随机数引擎。
24、交换
24.1、std::swap
std::swap 函数是一个通用的交换函数，可以用于交换绝大多数类型的对象。它的实现会通过移动语义或拷贝语义来保证高效的值交换。类的交换函数。
24.2、std::swap_ranges
交换两个范围内的元素。
24.3、std::iter_swap
交换两个迭代器指向的元素。
25、对每个元素应用指定操作
25.1、for_each
25.1.1、std::for_each
对给定范围内的每个元素应用指定的操作。
25.1.2、std::for_each_n
对给定范围内的前 n 个元素应用指定的操作。
- #include
- #include
- int main()
- {
- int numbers[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
- int count = 5;
- std::for_each_n(numbers, count, [](int number) {
- std::cout << number << std::endl;
- });
- return 0;
- }
25.2、transform
25.2.1、std::transform
对指定范围内的元素应用一个函数进行处理，并将结果存储到另一个容器中。
25.2.2、std::transform_exclusive_scan
这个各种资料的解释让人越看越糊涂，直接看代码：
- int main(int argc, char *argv[])
- {
- QVector<int> input = {1, 2, 3, 4, 5};
- QVector<int> output(input.size());
- // 定义一个二元操作函数，用于将相邻元素相加
- auto binary_op = [](int a, int b) {
- return a + b;
- };
- // 定义一个一元操作函数，用于将元素加倍
- auto unary_op = [](int a) {
- return a * 2;
- };
- std::transform_exclusive_scan(input.begin(), input.end(), output.begin(),
- 0, binary_op, unary_op);
- // 使用 qDebug 输出结果
- qDebug() << "转换和前缀扫描的结果："<}
即进行了两步：
1、unary_op作用于每个元素后，
2、用binary_op累积（什么是累积可查看上面std::inclusive_scan的说明）操作新元素（不含当前值）。
即：{1, 2, 3, 4, 5} -> {2, 4, 6, 8, 10} -> {0, 2, 6（即2+4）, 12（2+4+6）,20（即2+4+6+8）}
参数4是初始值：
25.2.3、std::transform_inclusive_scan
与std::transform_exclusive_scan类似的，不同之处在于不能设置初始值和累积时包括当前值。
25.2.4、std::transform_reduce
可以对指定范围内的元素进行变换，并将结果归约为单个值。
“归约”是指将一个序列中的元素经过某种操作（例如相加、相乘等），最后得到一个单独的结果。
- int main(int argc, char *argv[])
- {
- // 创建一个包含整数的 Qt 容器
- QVector<int> nums = {1, 2, 3, 4, 5};
- // 定义一个变换函数对象，将元素的平方返回
- auto square = [](int num) { return num * num; };
- auto plus = [](int a, int b) { return a + b; };
- // 使用自定义的归约函数对象对容器中的元素进行变换和归约操作
- int sumOfSquares = std::transform_reduce(nums.begin(),
- nums.end(),
- 0,
- plus,
- square);
- // 输出结果
- qDebug() << "容器元素的平方和：" << sumOfSquares; //55
- }
此代码首先对{1, 2, 3, 4, 5}的每个元素执行square即平方操作，得到{1, 4, 9, 16, 25}，再对此序列中的元素执行plus即相加的操作。
26、算法执行策略
- std::execution::seq：顺序执行，即算法按照顺序运行，不进行并行化。
- std::execution::par：并行执行，即算法可以并行化运行，以提高性能。
- std::execution::par_unseq：并行且无序执行，即算法可以并行化运行，并且运行结果无序。
- std::execution::unseq：无序执行，即算法可以进行优化，包括并行化和指令重排。
用法示例：
- #include
- int main(int argc, char *argv[])
- {
- std::vector<int> vec = {1, 2, 3, 4, 5};
- // 使用并行执行策略对向量中的每个元素进行平方操作
- std::for_each(std::execution::par, vec.begin(), vec.end(),
- [](int& num) { num = num * num; });
- // 输出结果
- for (int num : vec) {
- std::cout << num << " ";
- }
- std::cout << std::endl;
- }
27、策略控制器
- std::execution::sequenced_policy：算法应该以顺序的方式执行，即算法在一个线程中按照顺序依次执行，不会并行化或无序化操作。这种策略保证了算法的结果与输入的迭代器顺序保持一致。
- std::execution::parallel_policy：算法应该以并行的方式执行，即算法会尽可能地在多个线程中并行执行，以提高执行效率。并行执行策略充分利用多核处理器的能力，并允许多个线程同时处理不相关的任务。
用法示例：
- #include
- #include
- #include
- #include
- int main() {
- std::vector<int> vec = {1, 2, 3, 4, 5};
- // 使用并行执行策略对向量中的每个元素进行输出
- std::for_each(std::execution::parallel_policy, vec.begin(), vec.end(),
- [](int num) {
- std::cout << num << " ";
- });
- std::cout << std::endl;
- return 0;
- }
-
相关阅读:
IDEA创建Sping项目只能勾选17和21，却无法使用Java8
Mongoose应用和文件上传
window 安装多个版本的nodejs值版本控制工具nvm
CSDN---Markdown编辑器：基本语法知识
ZZNUOJ_Java语言从非零基础到入门讲解
成都力寰璨泓科技有限公司抖音小店品质保障
LeetCode·134.加油站·贪心
Android随笔-线程池
大数据学习笔记1.3 Linux用户操作
springboot - 手写spring mvc
- 原文地址：https://blog.csdn.net/kenfan1647/article/details/133305591
