歡迎訪問我的博客首頁。
標準庫算法
- 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);
}