标准库算法
欢迎访问我的博客首页。
标准库算法
- 1. 查找对象的算法
- 2. 其它只读算法
- 3. 二分搜索算法
- 4. 写容器元素的算法
- 5. 划分与排序算法
- 6. 通用重排操作
- 7. 排列算法
- 8. 有序序 列的 集合算法
- 9. 最 小值和 最大值
- 10. 数值算法
- 11. 参考
Pred 表示返回值为布尔类型的可调用对象。
1. 查找对象的算法
序列无需有序。
/* 简单查找算法 */
find(beg, end, val) // 查找指定值。返回迭代器。
find_if(beg , end, unaryPred) // 查找指定值。返回迭代器。
find_if_not(beg, end, unaryPred) // 查找指定值。返回迭代器。
count(beg, end, val) // 统计指定值出现的次数。返回整数。
count_if(beg, end, unaryPred) // 统计指定值出现的次数。返回整数。
all_of(beg, end, unaryPred) // 是否全部满足条件。返回布尔。
any_of(beg, end, unaryPred) // 是否有值满足条件。返回布尔。
none_of(beg, end, unaryPred) // 是否都不满足条件。返回布尔。
/* 查找重复值的算法 */
adjacent_find(beg, end) // 第一次出现相邻位置相等的地方。返回迭代器。
adjacent_find(beg, end, binaryPred) // 第一次出现相邻位置相等的地方。返回迭代器。
search_n(beg, end, count, val) // 第一次连续出现 count 个 val 的地方。返回迭代器。
search_n(beg, end, count， val, binaryPred) // 第一次连续出现 count 个 val 的地方。返回迭代器。
/* 查找子序列的算法 */
search(beg1, end1, beg2, end2) // 第二个序列在第一个序列中，第一次出现的地方。返回迭代器。
search(beg1, end1, beg2, end2, binaryPred) // 第二个序列在第一个序列中，第一次出现的地方。返回迭代器。
find_first_of(beg1, end1, beg2, end2) // 第二个序列中任一元素在第一个序列中出现的地方。返回迭代器。
find_first_of(beg1, end1, beg2, end2, binaryPred) // 第二个序列中任一元素在第一个序列中出现的地方。返回迭代器。
find_end(beg1, end1, beg2, end2) // 第二个序列在第一个序列中，最后一次出现的地方。返回迭代器。
find_end(beg1, end1, beg2, end2, binaryPred) // 第二个序列在第一个序列中，最后一次出现的地方。返回迭代器。
例子。
void test_1() {std::string data1 = "12365478911789";std::string data2 = "789";std::string::iterator it;int n;// find。第一次出现 '7' 的位置：data[6]。it = std::find(data1.begin(), data1.end(), '7');cout << it - data1.begin() << endl;// count。'1' 出现的次数：3。cout << std::count(data1.begin(), data1.end(), '1') << endl;// all_of。所有元素都大于 '0'：1。n = std::all_of(data1.begin(), data1.end(), [](char ch) -> bool {return ch > '0';});cout << n << endl;// adjacent_find：第一次出现相邻元素相等的地方：data[9]。it = adjacent_find(data1.begin(), data1.end());cout << it - data1.begin() << endl;// search_n：第一个连续出现 2 个 '1' 的地方：data[9]。it = search_n(data1.begin(), data1.end(), 2, '1', [](char ch1, char ch2) {return ch1 == ch2;});cout << it - data1.begin() << endl;// search。查找子序列：data_sub 在 data1 中第一次出现的地方：a[6]。it = std::search(data1.begin(), data1.end(), data2.begin(), data2.end());cout << it - data1.begin() << endl;// find_first_of。data_sub 的任意一个(不是第一个)元素在 data1 中首次出现的位置：6、7 或 8。it = std::find_first_of(data1.begin(), data1.end(), data2.begin(), data2.end());cout << it - data1.begin() << endl;// find_end。查找子序列：data_sub 在 data1 中最后一次出现的地方：a[11]。it = std::find_end(data1.begin(), data1.end(), data2.begin(), data2.end());cout << it - data1.begin() << endl;
}
2. 其它只读算法
介绍。
for_each(beg, end, unaryOp) // 遍历。返回可调用对象。
mismatch(beg1, end1, beg2) // 两个序列第一次出现不对应相等的地方。返回一对迭代器。
mismatch(beg1, end1, beg2, binaryPred) // 两个序列第一次出现不对应相等的地方。返回一对迭代器。
equal(beg1, end1, beg2) // 两个序列是否相等。返回布尔。
equal(beg1, end1, beg2, binaryPred) // 两个序列是否相等。返回布尔。
例子。
void test_2() {// for_each。逐个处理元素，如输出、修改。std::string data1 = "12345";std::for_each(data1.begin(), data1.end(), [](char &ch) {ch += 1;});cout << data1 << endl;// mismatch。第一次出现不对应相等的地方。std::string data2_1 = "12345";std::string data2_2 = "12365";std::pair<std::string::iterator, std::string::iterator> it = std::mismatch(data2_1.begin(), data2_1.end(), data2_2.begin());cout << it.first - data2_1.begin() << ", " << it.second - data2_2.begin() << endl;// equal。是否完全与第一个序列一样。cout << std::equal(data2_1.begin(), data2_1.end(), data2_2.begin()) << endl;
}
3. 二分搜索算法
序列需有序。
lower_bound(beg, end, val) // 第一个大于等于 val 的位置。返回迭代器。
lower_bound(beg, end, val, comp) // 第一个大于等于 val 的位置。返回迭代器。
upper_bound(beg, end, val) // 第一个大于 val 的位置。返回迭代器。
upper_bound(beg, end, val, comp) // 第一个大于 val 的位置。返回迭代器。
equal_range(beg, end, val) // 同时求 lower_bound 和 upper_bound。返回一对迭代器。
equal_range(beg, end, val, comp) // 同时求 lower_bound 和 upper_bound。返回一对迭代器。
binary_search(beg, end, val) // 是否存在指定值。返回布尔。
binary_search(beg, end, val, comp) // 是否存在指定值。返回布尔。
例子。
void test_3() {std::string data = "133556";// lower_bound。第一个大于等于 val 的地方。cout << std::lower_bound(data.begin(), data.end(), '3') - data.begin() << endl; // data[1]。cout << std::lower_bound(data.begin(), data.end(), '4') - data.begin() << endl; // data[3]。cout << std::lower_bound(data.begin(), data.end(), '5') - data.begin() << endl; // data[3]。// upper_bound。第一个大于 val 的地方。cout << std::upper_bound(data.begin(), data.end(), '3') - data.begin() << endl; // data[3]。cout << std::upper_bound(data.begin(), data.end(), '4') - data.begin() << endl; // data[3]。cout << std::upper_bound(data.begin(), data.end(), '5') - data.begin() << endl; // data[5]。// equal_range。同时求 lower_bound 和 upper_bound。std::pair<std::string::iterator, std::string::iterator> it;it = std::equal_range(data.begin(), data.end(), '3');cout << it.first - data.begin() << ", " << it.second - data.begin() << endl; // data[1], data[3]。it = std::equal_range(data.begin(), data.end(), '4');cout << it.first - data.begin() << ", " << it.second - data.begin() << endl; // data[3], data[3]。it = std::equal_range(data.begin(), data.end(), '5');cout << it.first - data.begin() << ", " << it.second - data.begin() << endl; // data[3], data[5]。// binary_search。cout << std::binary_search(data.begin(), data.end(), '3') << endl; // True。cout << std::binary_search(data.begin(), data.end(), '4') << endl; // false。
}
4. 写容器元素的算法
介绍。
/* 只写不读元素的算法 */
fill(beg, end, val) // 赋值。返回空。
fill_n(dest, cnt, val) // 赋值。返回迭代器。
generate(beg, end, Gen) // 赋值。返回空。
generate_n(dest, cnt, Gen) // 赋值。返回迭代器。
/* 使用输入迭代器的写算法 */
copy(beg, end, dest) // 拷贝。
copy_if(beg, end, dest, unaryPred) // 拷贝。
copy_n(beg, n, dest) // 拷贝。
move(beg, end, dest) // 移动。
transform(beg, end, dest, unaryOp) // 处理、拷贝。
transform(beg, end, beg2, dest, binaryOp) // 处理、拷贝。
replace_copy(beg, end, dest, old_val, new_val) // 替换、拷贝。
replace_copy_if(beg, end, dest, unaryPred, new_val) // 替换、拷贝。
merge(beg1, end1, beg2, end2, dest) // 合并有序序列得到第三个有序序列。
merge(beg1, end1, beg2, end2, dest, comp) // 合并有序序列得到第三个有序序列。
/* 使用前向迭代器的写算法 */
iter_swap(iter1, iter2) // 交换两个序列的一个元素。
swap_ranges(beg1, end1, beg2) // 交换两个序列的一段元素。
replace(beg, end, old_val, new_val) // 使用 new_val 替换一段值。
replace_if(beg, end, unaryPred, new_val)
/* 使用双向迭代器的写算法 */
copy_backward(beg, end, dest) // 向目的序列尾部拷贝。
move_backward(beg, end, dest) // 向目的序列尾部移动。
inplace_merge(beg, mid, end) // 对包含两个有序序列的序列排序。
inplace_merge(beg, mid, end, comp) // 对包含两个有序序列的序列排序。
例子。
void test_4() {std::string data;std::string::iterator end;data.resize(2);// fillstd::fill(data.begin(), data.end(), '1');cout << data << endl;// fill_nend = std::fill_n(data.begin(), data.size(), '2');assert(end == data.end());cout << data << endl;// generatestd::generate(data.begin(), data.end(), [&]() -> char {return '3';});cout << data << endl;// generate_nend = std::generate_n(data.begin(), data.size(), [&]() -> char {return '4';});assert(end == data.end());cout << data << endl;std::string src = "12345";std::string dest(4, '0');// copy。如果 dest 容量耗尽则停止拷贝。std::copy(src.begin(), src.end(), dest.begin()); // "1234"。cout << dest << endl;// move// transformstd::transform(src.begin(), src.end(), dest.begin(), [](char ch) {return ch + 1;});cout << dest << endl;std::string src2 = "22222";std::transform(src.begin(), src.end(), src2.begin(), dest.begin(), [](char ch1, char ch2) {return ch1 + ch2 - '0';});cout << dest << endl;// replace_copystd::replace_copy(src.begin(), src.end(), dest.begin(), '3', 'z');cout << dest << endl;// replace_copy_ifstd::replace_copy_if(src.begin(),src.end(),dest.begin(),[](char ch) {return ch == '3';},'z');cout << dest << endl;// merge。两个输入序列要么都是升序要么都是降序。std::string data1 = "12468";std::string data2 = "12345";dest.resize(20);std::merge(data1.begin(), data1.end(), data2.begin(), data2.end(), dest.begin());cout << dest << endl;// iter_swap。交换两个迭代器所指元素。std::iter_swap(data1.begin() + 3, data2.end() - 1);cout << data1 << " " << data2 << endl;// swap_rangesstd::string data3 = "123";std::string data4 = "abcdef";std::string::iterator it;it = std::swap_ranges(data3.begin(), data3.end(), data4.begin());assert(it - data4.begin() == data3.size());cout << data3 << ", " << data4 << endl;// replacestd::string data5 = "123456";std::replace(data5.begin(), data5.end(), '3', 'c');cout << data5 << endl;// copy_backwardstd::string data6 = "123";std::string data7(4, 'z');std::copy_backward(data6.begin(), data6.end(), data7.end());cout << data6 << ", " << data7 << endl;// move_backward// inplace_mergestd::string data8 = "135246";std::inplace_merge(data8.begin(), data8.begin() + 3, data8.end(), [](char ch1, char ch2) {return ch1 < ch2;});cout << data8 << endl;
}
5. 划分与排序算法
介绍。
/* 划分算法 */
is_partitioned(beg, end, unaryPred) // 满足谓词的元素在前，不满足的在后？
partition_copy(beg, end, dest1, dest2, unaryPred)// 分别拷贝满足谓词的元素和不满足的元素。
partition_point(beg, end, unaryPred)// 满足谓词的最后一个元素的尾后迭代器。
stable_parition(beg, end, unaryPred)// 稳定排序：满足谓词的元素在前。
partition(beg, end, unaryPred)// 不稳定排序：满足谓词的元素在前。
/* 排序算法 */
sort(beg, end)
stable_sort(beg, end)
sort(beg, end, comp)
stable_sort(beg, end, comp)
is_sorted(beg, end)
is_sorted(beg, end, comp)
is_sorted_until(beg, end)// 乱序开始的位置。
is_sorted_until(beg, end, comp)// 乱序开始的位置。
partial_sort(beg, mid, end)// 仅排序到 mid。
partial_sort(beg, mid, end, comp)
partial_sort_copy(beg, end, destBeg, destEnd)
partial_sort_copy(beg, end, destBeg, destEnd, comp)
nth_element(beg, nth, end)// 排序，使 nth 前的元素都比它小，后面的都比它大。
nth_element(beg, nth, end, comp)
例子。
void test_5() {// is_partitionedstd::string data1 = "1342";cout << std::is_partitioned(data1.begin(), data1.end(), [](char ch) {return (ch - '0') % 2 == 1;}) << endl;// partition_copystd::string data2(5, 'a');std::string data3(5, 'b');std::pair<std::string::iterator, std::string::iterator> it =std::partition_copy(data1.begin(), data1.end(), data2.begin(), data3.begin(), [](char ch) {return (ch - '0') % 2 == 1;});assert(it.first - data2.begin() == 2);assert(it.second - data3.begin() == 2);cout << data2 << ", " << data3 << endl;// partition_pointstd::string::iterator it2 = std::partition_point(data1.begin(), data1.end(), [](char ch) {return (ch - '0') % 2 == 1;});assert(it2 - data1.begin() == 2);// stable_partitionstd::string data4 = "12345";it2 = std::stable_partition(data4.begin(), data4.end(), [](char ch) {return (ch - '0') % 2 == 1;});assert(it2 - data4.begin() == 3);cout << data4 << endl;// partition。不保证相对位置不变，比如结果可能是 13524，也可能是 31542 等。std::string data5 = "12345";it2 = std::stable_partition(data5.begin(), data5.end(), [](char ch) {return (ch - '0') % 2 == 1;});assert(it2 - data5.begin() == 3);cout << data5 << endl;// sort// is_sorted_until。第一个有序序列的长度。std::string data6 = "zabc";it2 = std::is_sorted_until(data6.begin(), data6.end());assert(it2 - data6.begin() == 1);// partial_sort。找出最小的 3 个元素放到开头，后面的元素相对位置可能会被打乱。std::string data7 = "abxyzcghds";std::partial_sort(data7.begin(), data7.begin() + 3, data7.end());cout << data7 << endl;// partial_sort_copy。根据目标容器的容量按元素大小顺序拷贝过去，原容器内的元素不变。std::string data8 = "abxyzcghds";std::string data9;data9.resize(3);std::partial_sort_copy(data8.begin(), data8.end(), data9.begin(), data9.end());cout << data8 << ", " << data9 << endl;// nth_element。a[2] 前面的元素都比 a[2] 小，后面的元素都比 a[2] 大。std::string data10 = "7036281549";std::nth_element(data10.begin(), data10.begin() + 2, data10.end());cout << data10 << endl;
}
6. 通用重排操作
介绍。
/* 使用前向迭代器的重排算法 */
remove(beg, end, val)
remove_if(beg, end, unaryPred)
remove_copy(beg, end, dest, val)
remove_copy_if(beg, end, dest, unaryPred)
unique(beg, end)
unique(beg, end, binaryPred)
unique_copy(beg, end, dest）
unique_copy_if(beg, end, dest, binaryPred)
rotate(beg, mid, end)
rotate_copy(beg, mid, end, dest)
/* 使用双向迭代器的重排算法 */
reverse(beg, end)
reverse_copy(beg, end, dest）
/* 使用随机访问迭代器的重排算法 */
random_shuffle(beg, end)
random_shuffle(beg, end, rand)
shuffle(beg, end, Uniform_rand)
例子。
void test_6() {std::string::iterator it;// removestd::string data1 = "121345";it = std::remove(data1.begin(), data1.end(), '1');cout << data1 << ", " << it - data1.begin() << endl;// remove_copystd::string data2 = "121345";std::string dest2;dest2.resize(10);it = std::remove_copy(data2.begin(), data2.end(), dest2.begin(), '1');assert(it - dest2.begin() == 4);cout << dest2 << endl;// unique。仅处理相邻且相等的元素。std::string data3 = "144422355";it = std::unique(data3.begin(), data3.end());assert(it - data3.begin() == 5);cout << it - data3.begin() << endl;cout << data3 << endl;// rotatestd::string data4 = "987a123";it = std::rotate(data4.begin(), data4.begin() + 3, data4.end());cout << data4 << ", " << it - data4.begin() << endl;// reversestd::string data5 = "123";std::reverse(data5.begin(), data5.end());cout << data5 << endl;// random_shufflestd::string data6 = "123";srand((unsigned)time(NULL));std::random_shuffle(data6.begin(), data6.end());cout << data6 << endl;// shufflestd::string data7 = "123";std::shuffle(data7.begin(), data7.end(), std::random_device());cout << data7 << endl;
}
7. 排列算法
介绍。
is_permutation(beg1, end1, beg2)
is_permutation(beg1, end1, beg2), binaryPred)
next_permutation(beg, end)
next_permutation(beg, end, comp)
prev_permutation(beg, end)
prev_permutation(beg, end, comp)
例子。
void test_7() {// is_permutationstd::string data1_1 = "123";std::string data1_2 = "213";cout << std::is_permutation(data1_1.begin(), data1_1.end(), data1_2.begin()) << endl;// next_permutationcout << std::next_permutation(data1_1.begin(), data1_1.end()) << ", " << data1_1 << endl;cout << std::prev_permutation(data1_1.begin(), data1_1.end()) << ", " << data1_1 << endl;
}
8. 有序序 列的 集合算法
介绍。
includes(beg, end, beg2 , end2)
includes(beg, end, beg2, end2, comp)
set_union(beg, end, beg2, end2, dest)
set_union(beg, end, beg2, end2, dest, comp)
set_intersection(beg, end, beg2, end2, dest)
set_intersection(beg, end, beg2, end2, dest, comp)
set_difference(beg, end, beg2, end2, dest)
set_difference(beg, end, beg2, end2, dest, comp)
set_symmetric_difference(beg, end, beg2, end2, dest）
set_symmetric_difference(beg, end, beg2, end2, dest, comp)
例子。
// 必须有序。
void test_8() {// includestd::string data1_1 = "123456";std::string data1_2 = "15";cout << std::includes(data1_1.begin(), data1_1.end(), data1_2.begin(), data1_2.end()) << endl;// set_union。求交集。std::string data2_1 = "0134679";std::string data2_2 = "125689";std::string dest2;dest2.resize(10);std::set_union(data2_1.begin(), data2_1.end(), data2_2.begin(), data2_2.end(), dest2.begin());cout << dest2 << endl;// set_intersection。求并集。std::string dest3;dest3.resize(10);std::set_intersection(data2_1.begin(), data2_1.end(), data2_2.begin(), data2_2.end(), dest3.begin());cout << dest3 << endl;// set_difference。差集。// set_symmetric_difference。
}
9. 最 小值和 最大值
介绍。
min(val1, val2)
min(val1, val2, comp)
min(init_list)
min(init_list, comp)
max(val1, val2)
max(val1, val2, comp)
max(init_list)
max(init_list, comp)
minmax(val1, val2)
minnmax(val1, val2, comp)
minmax(init_list)
minmax(init list, comp)
min_element(beg, end)
min_element(beg, end, comp)
max_element(beg, end)
max_element(beg, end, comp)
minmax_element(beg, end)
minmax_element(beg, end, comp)
/* 字典序比较 */
lexicographical_compare(beg1, end1, beg2, end2)
lexicographical_compare(beg1, end1, beg2, end2, comp)
例子。
void test_9() {// minstd::string data1 = "102";char ch = std::min({'1', '0', '2'});cout << ch << endl;// lexicographical_comparestd::string data2_1 = "012";std::string data2_2 = "001";cout << std::lexicographical_compare(data2_1.begin(), data2_1.end(), data2_2.begin(), data2_2.end()) << endl;
}
10. 数值算法
介绍。
accumulate(beg, end, init)
accumulate(beg, end, init, binaryOp)
inner_product(beg1, end1, beg2, init）
inner_product(beg1, end1, beg2, init, binOp1, binOp2)
partial_sum(beg, end, dest）
partial_sum(beg, end, dest, binaryOp)
adjacent_difference(beg, end, dest)
adjacent_difference(beg, end, dest, binaryOp)
iota(beg, end, val)
例子。
void test_10() {// accumulatestd::vector<int> data1 = {1, 2, 3};cout << std::accumulate(data1.begin(), data1.end(), 100, [](int a, int b) {return a + b;}) << endl;// inner_product// partial_sumstd::vector<int> dest3;dest3.resize(10);std::partial_sum(data1.begin(), data1.end(), dest3.begin());print(dest3);// adjacent_differencestd::adjacent_difference(data1.begin(), data1.end(), dest3.begin());print(dest3);// iotastd::iota(data1.begin(), data1.end(), 0);print(data1);
}