上海微信网站制作哪家专业,找人开发一个app多少钱,给 小企业 建设网站,类似于建设通的网站C STL#xff08;Standard Template Library#xff09;是C标准库中的一个重要组成部分#xff0c;提供了丰富的模板函数和容器#xff0c;用于处理各种数据结构和算法。在STL中#xff0c;排序、算数和集合算法是常用的功能#xff0c;可以帮助我们对数据进行排序、统计…C STLStandard Template Library是C标准库中的一个重要组成部分提供了丰富的模板函数和容器用于处理各种数据结构和算法。在STL中排序、算数和集合算法是常用的功能可以帮助我们对数据进行排序、统计、查找以及集合操作等。
STL提供的这些算法能够满足各种数据处理和分析的需求。通过灵活使用这些算法我们可以高效地对数据进行排序、查找和聚合操作提高代码的性能和可读性。在实际编程中根据具体问题的需求选择合适的算法能够更好地发挥STL的优势提高程序的效率。
9.1 堆排序算法
Sort_heap 算法函数用于对堆容器进行排序。sort_heap的用法如下
templateclass RandomAccessIterator
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);其中first、last是随机访问迭代器表示待排序的堆容器的范围。sort_heap函数将[first, last]范围的堆容器排序并将排序后的结果存储在相同的容器中。
读者需要注意sort_heap函数执行前必须先使用make_heap函数对容器进行堆化然后再利用堆排序算法对其进行排序。
sort_heap函数通过重复执行pop_heap操作来实现排序。pop_heap操作从堆顶提取元素将该元素放到容器的末尾位置然后重新调整剩余元素的顺序使之形成新的堆结构。重复执行pop_heap操作就可以将堆容器中的所有元素按照递增顺序排序。
#include iostream
#include algorithm
#include vectorusing namespace std;void MyPrint(int val){ cout val ; }int main(int argc, char* argv[])
{vectorint var {45,76,89,32,11,23,45,9,0,3};for_each(var.begin(), var.end(), MyPrint);cout endl;// 建立堆make_heap(var.begin(), var.end());// 如果堆建立成功,则执行排序if (is_heap(var.begin(), var.end())){// 开始对堆排序sort_heap(var.begin(), var.end());}for_each(var.begin(), var.end(), MyPrint);system(pause);return 0;
}9.2 局部排序与复制
Partial_sort 算法函数用于对指定区间的元素进行部分排序。partial_sort的用法如下
templateclass RandomAccessIterator
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);其中first、last是随机访问迭代器表示待排序序列的范围middle是迭代器表示指定的部分排序位置。partial_sort函数将[first, last]范围内的元素进行部分排序使得从[first, middle)的元素按照递增顺序排列其余元素不保证有序。也就是说middle之前的元素是排过序的middle之后的元素未排序。
由于该函数使用的是堆排序算法。在实现排序功能前partial_sort函数首先将元素按照一定规则生成部分堆然后重复执行pop_heap操作将堆顶元素放到middle前重新调整剩余元素的顺序使之形成新的堆结构。重复执行pop_heap操作就可以将[first, middle)范围内的元素按照递增顺序排列。
该算法可实现对容器中部分元素进行排序还可以将结果拷贝到其他容器中如下是一个简单的局部排序与排序拷贝案例。
#include iostream
#include algorithm
#include vectorusing namespace std;void MyPrint(int val){ cout val ; }int main(int argc, char* argv[])
{int iArray[] { 3, 4, 8, 23, 56, 3, 89, 0, 32, 6 };const int len sizeof(iArray) / sizeof(int);// 输出排序前的顺序for_each(iArray, iArray len, MyPrint);cout endl;// 局部排序,将数组中的前6个元素进行排序,后面的不排列int middle 5; // 指定排序索引,索引从0开始partial_sort(iArray, iArray middle, iArray len);for_each(iArray, iArray len, MyPrint);cout endl;// 排序并拷贝元素,将iArray中前5个元素排序后拷贝到var中vectorint var(6);partial_sort_copy(iArray, iArray 5, var.begin(), var.end());for_each(iArray, iArray 5, MyPrint);system(pause);return 0;
}9.3 快速排序算法
Sort 算法函数用于对序列进行排序。sort的用法如下
templateclass RandomAccessIterator
void sort(RandomAccessIterator first, RandomAccessIterator last);其中first、last是随机访问迭代器表示待排序的序列的范围。sort函数将[first, last]范围内的元素按照递增顺序排序并将排序后的结果存储在相同的容器中。sort函数在执行前需要保证所排序的元素类型支持运算符。
sort函数使用的是快速排序算法在实现排序功能前sort函数首先会选择[first, last]范围内的一个元素作为分割基准元素然后按照分割基准元素将范围内的元素分为两个序列其中一个序列的元素均小于基准元素另一个序列的元素均大于等于基准元素。然后对两个序列分别递归调用sort函数不断进行分割和排序直到分割出的序列长度为1排序就完成了。
#include iostream
#include algorithm
#include vector
#include functionalusing namespace std;void MyPrint(int val){ cout val ; }int main(int argc, char* argv[])
{// 从小到大排序int iArray[] { 56, 43, 22, 1, 34, 7, 89, 0, 43, 56 };const int len sizeof(iArray) / sizeof(int);sort(iArray, iArray len);for_each(iArray, iArray len, [](int val){cout val ; });cout endl;// 从大到小排序vectorint var { 45, 76, 33, 21, 7, 89, 0, 34, 5, 7 };sort(var.begin(), var.end(), greaterint());for_each(var.begin(), var.end(), MyPrint);system(pause);return 0;
}9.4 稳定排序算法
Stable_sort 算法函数用于对序列进行稳定排序。stable_sort的用法如下
templateclass RandomAccessIterator
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);其中first、last是随机访问迭代器表示待排序的序列的范围。stable_sort函数将[first, last]范围内的元素按照递增顺序排序并保证相等元素的相对顺序不变将排序后的结果存储在相同的容器中。
stable_sort函数使用的是归并排序算法具有良好的稳定性可以保证相等元素的相对顺序不变。在实现排序功能前stable_sort函数首先将序列从中间分成两个子序列然后分别对两个子序列进行排序最后归并两个排序好的子序列形成一个完整的排序序列。
#include iostream
#include algorithm
#include vectorusing namespace std;struct Student{int id;char *name;int score;Student(int _id, char* _name, int _score){id _id; name _name; score _score;}
};void MyPrint(Student val)
{cout val.id val.name val.score endl;
}bool CompByScore(Student x, Student y)
{// 按照学生的成绩从小到大进行排序return x.score y.score ? 1 : 0;
}int main(int argc, char* argv[])
{vectorStudent var;var.push_back(Student(1, keey, 90));var.push_back(Student(2, marry, 82));var.push_back(Student(3, lisa, 70));stable_sort(var.begin(), var.end(), CompByScore);for_each(var.begin(), var.end(), MyPrint);system(pause);return 0;
}9.5 容器归并算法
Merge 算法函数用于将两个已排序的序列合并成一个有序序列。merge的用法如下
templateclass InputIterator1, class InputIterator2, class OutputIterator
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);其中first1、last1、first2、last2是输入迭代器表示待合并的两个已排序序列的范围result是输出迭代器表示合并后的有序序列的目标位置。merge函数将已排序的两个序列按照递增顺序合并成一个新的有序序列输出到result所指向的迭代器位置并将输出结果的尾后迭代器作为函数的返回值返回。
merge函数使用的是归并排序算法在实现合并功能前merge函数首先将输入序列分成若干个小的段将不同段之间的元素合并成一个有序段然后再将合并后的所有段依次合并完成最终的排序结果。
该算法可以实现将两个具有相同升降方向的有序序列(必须有序)合并成另一个有序序列。
#include iostream
#include algorithm
#include functionalusing namespace std;void MyPrint(int val){ cout val ; }int main(int argc, char* argv[])
{// 按照升序方式将两个序列合并int iArray1[3] { 1, 2, 3 };int iArray2[7] { 4, 5, 6, 7, 8, 9, 10 };int result[10];merge(iArray1, iArray1 3, iArray2, iArray2 7, result);for_each(result, result 10, MyPrint);cout endl;// 按照降序方式将两个序列合并int iArray3[5] { 30, 20, 15, 9, 2 };int iArray4[4] { 10, 5, 3, 1 };int result2[9];merge(iArray3, iArray3 5, iArray4, iArray4 4, result2, greaterint());for_each(result2, result2 9, MyPrint);cout endl;// 内部归并排序,这里只给出降序排列代码,升序排列与第一个案例相同int iArray5[] { 100, 80, 60, 40, 20, 10, 90, 70, 50, 30 };const int len sizeof(iArray5) / sizeof(int); // 数组元素总长度int middle 6; // 选择一个切割中位数下标inplace_merge(iArray5, iArray5 middle, iArray5 len, greaterint());for_each(iArray5, iArray5 len, MyPrint);system(pause);return 0;
}9.6 容器区间查找算法
Bound 算法函数用于查找序列中指定值的边界位置。bound的用法如下
templateclass ForwardIterator, class T
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T value);templateclass ForwardIterator, class T
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T value);其中first、last是迭代器表示待查找的序列的范围value是需要查找的元素的值。lower_bound函数返回指向序列中第一个不小于value的元素的迭代器如果所有元素都小于value则返回lastupper_bound函数返回指向序列中第一个大于value的元素的迭代器如果所有元素都不大于value则返回last。
读者需要注意该函数函数执行前需要保证所输入的序列本身已经是已排序的序列并且元素类型支持运算符。
bound函数使用的是二分查找算法可以高效地找到指定值的边界位置。lower_bound函数首先将序列分成若干个小的区间每个区间内的元素都不大于value然后在这些区间中继续执行二分查找操作直到定位到第一个不小于value的元素位置。upper_bound函数和lower_bound函数类似只是在找到不小于value的元素时继续向前遍历直到定位到第一个大于value的元素位置。
#include iostream
#include algorithmusing namespace std;int main(int argc, char* argv[])
{int iArray[] { 3, 6, 9, 12, 13, 18, 20, 27, 55, 44};const int len sizeof(iArray) / sizeof(int);// lower_bound 找出不小于某值的有序数组下确界元素int *result1 lower_bound(iArray, iArray len, 16);cout lower_bound *result1 endl;// upper_bound 找出大于某值的有序数组上确界元素int *result2 upper_bound(iArray, iArray len, 20);cout upper_bound *result2 endl;// equal_range 找出可插入某值的区间元素pairint*, int* range equal_range(iArray, iArray len, 5);cout lower_bound *range.first endl;cout upper_bound *range.second endl;system(pause);return 0;
}9.7 最大值/最小值算法
min_element和max_element 算法函数用于查找序列中的最小元素和最大元素。它们的用法如下
templateclass ForwardIterator
ForwardIterator min_element(ForwardIterator first, ForwardIterator last);templateclass ForwardIterator
ForwardIterator max_element(ForwardIterator first, ForwardIterator last);其中first和last是迭代器表示待查找的序列的范围。min_element函数返回指向序列中最小元素的迭代器max_element函数返回指向序列中最大元素的迭代器。
读者需要注意min_element和max_element函数执行前需要保证所输入的序列本身已经是已排序的序列。另外为了实现更高效的运行时间C STL中提供了另一个函数模板来查找最大或最小值。它可以在部分或未排序的序列中查找最大或最小的元素
template class ForwardIterator, class Compare
ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp);template class ForwardIterator, class Compare
ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp);其中comp是一个可调用函数或函数对象用于指定元素的比较方法。min_element和max_element函数的功能与之前相同只是增加了一个参数comp用于指定元素的比较方法。
总之min_element和max_element函数是C STL中非常实用的查找函数可以方便地查找序列中的最小元素和最大元素并支持自定义的比较方法实现各种元素查找和排序等操作。
#include iostream
#include algorithm
#include listusing namespace std;int main(int argc, char* argv[])
{listint ls { 1, 4, 5, 6, 7, 2, 3, 4, 9, 7, 6 };// 返回链表最小元素cout *min_element(ls.begin(), ls.end()) endl;// 返回链表最大元素cout *max_element(ls.begin(), ls.end()) endl;// 剩余 max /min 比较cout max(100, 30) endl;cout min(1, -10) endl;system(pause);return 0;
}9.8 交集/并集/差集算法
set_intersection、set_union和set_difference 算法函数分别用于求两个集合的交集、并集和差集。它们的用法如下
templateclass InputIterator1, class InputIterator2, class OutputIterator
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);templateclass InputIterator1, class InputIterator2, class OutputIterator
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);templateclass InputIterator1, class InputIterator2, class OutputIterator
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);其中first1、last1、first2、last2是输入迭代器表示待运算的两个集合的范围result是输出迭代器表示运算结果的位置。set_intersection函数返回两个集合的交集set_union函数返回两个集合的并集set_difference函数返回两个集合的差集。这些函数将运算结果复制到由result指定的迭代器范围内并返回一个指向输出序列尾后位置的迭代器。
读者需要注意函数执行前需要保证输入的两个集合已经是有序的集合并且元素类型支持运算符。
set_intersection、set_union和set_difference函数使用的是归并排序的思想可以高效地计算两个集合的交集、并集和差集。具体实现方式为从输入集合的第一个元素开始遍历将两个集合中相同的元素复制到输出序列中set_intersection将所有元素包括重复元素复制到输出序列中set_union将只存在于第一个集合中的元素复制到输出序列中set_difference。
#include iostream
#include algorithm
#include vector
#include iteratorusing namespace std;int main(int argc, char* argv[])
{vectorint var1 { 1,2,3,4,5,23 };vectorint var2 { 1,2,3,4,5,6,7,8,9,10 };vectorint vTarget;// ------------------------------------------------// 求 var1 与 var2 的交集// ------------------------------------------------// 分配最小空间vTarget.resize(min(var1.size(), var2.size()));vectorint::iterator itEnd;itEnd set_intersection(var1.begin(), var1.end(), var2.begin(), var2.end(), vTarget.begin());// 拷贝与打印出来copy(vTarget.begin(), itEnd, ostream_iteratorint(cout, ));cout endl;// ------------------------------------------------// 求 var1 与 var2 的并集// ------------------------------------------------// 分配最大空间vTarget.resize(var1.size()var2.size());vectorint::iterator itEnd1;itEnd1 set_union(var1.begin(), var1.end(), var2.begin(), var2.end(), vTarget.begin());// 拷贝与打印出来copy(vTarget.begin(), itEnd1, ostream_iteratorint(cout, ));cout endl;// ------------------------------------------------// 求 var1 与 var2 的差集// ------------------------------------------------// 分配最大数组的空间vTarget.resize(max(var1.size(),var2.size()));vectorint::iterator itEnd2;itEnd2 set_difference(var1.begin(), var1.end(), var2.begin(), var2.end(), vTarget.begin());// 拷贝与打印出来copy(vTarget.begin(), itEnd2, ostream_iteratorint(cout, ));system(pause);return 0;
}9.9 求容器上/下排列组合
next_permutation和prev_permutation算法函数用于获取一个序列的下一个或上一个排列。它们的用法如下
templateclass BidirectionalIterator
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);templateclass BidirectionalIterator
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);其中first和last是双向迭代器表示待排列的序列的起始和终止位置。next_permutation函数将序列转换为下一个排列prev_permutation函数将序列转换为上一个排列如果没有下一个或上一个排列则返回false否则返回true。
next_permutation和prev_permutation函数使用的是字典序算法即通过比较相邻的排列从而找到下一个或上一个排列。具体实现方式为从序列的最后一个元素开始遍历找到第一个满足a[i]a[i1]的元素a[i]然后在i的右边找到最小的元素a[j]使得a[j]a[i]将a[i]和a[j]互换位置最后将i右边的元素按升序排列从而得到下一个排列。prev_permutation函数实现方式类似只是将上述步骤中的和反转即可。
该算法用于对区间元素进行组合排列选择一个字典顺序更大或更小的排列。
#include iostream
#include algorithmusing namespace std;void MyPrint(int x) { cout x ; }// 排序函数
template class BidirectionalIter
void nextPermu_sort(BidirectionalIter first, BidirectionalIter last)
{// 利用较大的组合返回truewhile (next_permutation(first, last)){}
}int main(int argc, char* argv[])
{int iArray[] { 3, 5, 8, 1, 8, 9, 3, 2, 1, 9 };const int len sizeof(iArray) / sizeof(int);// 下一排列组合next_permutation(iArray, iArray len);for_each(iArray, iArray len, MyPrint);cout endl;// 上一排列组合prev_permutation(iArray, iArray len);for_each(iArray, iArray len, MyPrint);system(pause);return 0;
}9.10 容器元素求和算法
accumulate、inner_product和partial_sum 算法函数分别用于计算序列中的累加和、内积和和部分和序列。它们的用法如下
templateclass InputIterator, class T
T accumulate(InputIterator first, InputIterator last, T init);templateclass InputIterator1, class InputIterator2, class T
T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init);templateclass InputIterator, class OutputIterator
OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result);其中first、last、first1、last1、first2是输入迭代器表示待计算的序列范围init是计算的初始值result是输出迭代器表示计算结果的位置。accumulate函数返回序列中元素的累加和inner_product函数返回序列的内积和partial_sum函数返回序列的部分和序列。这些函数将计算结果复制到由result指定的迭代器范围内并返回一个指向输出序列尾后位置的迭代器。
需要说明的是accumulate和inner_product函数可以接受一个自定义的二元操作符比如加法、乘法等从而实现各种自定义的累加和和内积和的计算。partial_sum函数不需要自定义操作符固定使用加法运算。
accumulate、inner_product和partial_sum函数使用的都是迭代算法在遍历序列时进行累加和、内积和和部分和的计算。具体实现方式为遍历序列中的元素根据特定的操作符将每个元素进行累加、相乘或相加从而得到总体的累加和、内积和或部分和序列。
#include iostream
#include numeric
#include algorithmusing namespace std;void MyPrint(int x) { cout x ; }int multiply(int x, int y) { return x*y; }int main(int argc, char* argv[])
{// 求数组元素相加之和int iArray[5] {1,2,3,4,5};cout accumulate(iArray, iArray 5, 0) endl;// 求数组元素的内积int iArray1[3] { 2, 5, 4 };int iArray2[3] { 10, 6, 5 };cout inner_product(iArray1, iArray1 3, iArray2, 0) endl;// 部分元素求和int iArray3[5] { 1, 2, 3, 4, 5 };int result[5];partial_sum(iArray3, iArray3 5, result);for_each(iArray3, iArray3 5, MyPrint);cout endl;// 求阶乘int result1[5];partial_sum(iArray3, iArray3 5, result1,multiply);for_each(result1, result1 5, MyPrint);system(pause);return 0;
}本文作者 王瑞 本文链接 https://www.lyshark.com/post/bba79f2e.html 版权声明 本博客所有文章除特别声明外均采用 BY-NC-SA 许可协议。转载请注明出处
