标准库算法

标准库算法

码农世界 2024-05-27 后端 67 次浏览 0个评论

欢迎访问我的博客首页。

标准库算法

  • 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 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 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);
    // fill
    std::fill(data.begin(), data.end(), '1');
    cout << data << endl;
    // fill_n
    end = std::fill_n(data.begin(), data.size(), '2');
    assert(end == data.end());
    cout << data << endl;
    // generate
    std::generate(data.begin(), data.end(), [&]() -> char {
        return '3';
    });
    cout << data << endl;
    // generate_n
    end = 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
    // transform
    std::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_copy
    std::replace_copy(src.begin(), src.end(), dest.begin(), '3', 'z');
    cout << dest << endl;
    // replace_copy_if
    std::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_ranges
    std::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;
    // replace
    std::string data5 = "123456";
    std::replace(data5.begin(), data5.end(), '3', 'c');
    cout << data5 << endl;
    // copy_backward
    std::string data6 = "123";
    std::string data7(4, 'z');
    std::copy_backward(data6.begin(), data6.end(), data7.end());
    cout << data6 << ", " << data7 << endl;
    // move_backward
    // inplace_merge
    std::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_partitioned
    std::string data1 = "1342";
    cout << std::is_partitioned(data1.begin(), data1.end(), [](char ch) {
        return (ch - '0') % 2 == 1;
    }) << endl;
    // partition_copy
    std::string data2(5, 'a');
    std::string data3(5, 'b');
    std::pair 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_point
    std::string::iterator it2 = std::partition_point(data1.begin(), data1.end(), [](char ch) {
        return (ch - '0') % 2 == 1;
    });
    assert(it2 - data1.begin() == 2);
    // stable_partition
    std::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;
    // remove
    std::string data1 = "121345";
    it = std::remove(data1.begin(), data1.end(), '1');
    cout << data1 << ", " << it - data1.begin() << endl;
    // remove_copy
    std::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;
    // rotate
    std::string data4 = "987a123";
    it = std::rotate(data4.begin(), data4.begin() + 3, data4.end());
    cout << data4 << ", " << it - data4.begin() << endl;
    // reverse
    std::string data5 = "123";
    std::reverse(data5.begin(), data5.end());
    cout << data5 << endl;
    // random_shuffle
    std::string data6 = "123";
    srand((unsigned)time(NULL));
    std::random_shuffle(data6.begin(), data6.end());
    cout << data6 << endl;
    // shuffle
    std::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_permutation
    std::string data1_1 = "123";
    std::string data1_2 = "213";
    cout << std::is_permutation(data1_1.begin(), data1_1.end(), data1_2.begin()) << endl;
    // next_permutation
    cout << 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() {
    // include
    std::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() {
    // min
    std::string data1 = "102";
    char ch = std::min({'1', '0', '2'});
    cout << ch << endl;
    // lexicographical_compare
    std::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() {
    // accumulate
    std::vector data1 = {1, 2, 3};
    cout << std::accumulate(data1.begin(), data1.end(), 100, [](int a, int b) {
        return a + b;
    }) << endl;
    // inner_product
    // partial_sum
    std::vector dest3;
    dest3.resize(10);
    std::partial_sum(data1.begin(), data1.end(), dest3.begin());
    print(dest3);
    // adjacent_difference
    std::adjacent_difference(data1.begin(), data1.end(), dest3.begin());
    print(dest3);
    // iota
    std::iota(data1.begin(), data1.end(), 0);
    print(data1);
}

    11. 参考

转载请注明来自码农世界，本文标题：《标准库算法》

百度分享代码，如果开启HTTPS请参考李洋个人博客
37815篇文章 站点 微博
每一天，每一秒，你所做的决定都会改变你的人生！

发表评论

快捷回复：

评论列表 （暂无评论，67人围观）参与讨论

还没有评论，来说两句吧...

Top