首页 > 编程语言 >【信奥赛·C++基础语法】CSP-J C++ STL 标准模板库 - 算法

【信奥赛·C++基础语法】CSP-J C++ STL 标准模板库 - 算法

时间：2024-10-19 20:17:55浏览次数：3  
标签：std begin STL 信奥赛 C++ int 算法 vec include

序言

标准模板库（STL）的算法部分提供了一系列强大的工具，用于对各种容器中的数据进行操作。这些算法可以大大提高编程效率，减少代码重复，使程序更加简洁、高效和可读。无论是处理简单的数据结构还是复杂的大规模数据，STL 算法都能发挥重要作用。

一、STL 算法的分类

  1. 排序算法
  • 快速排序（ std::sort ）及特点：
  • std::sort 是一种高效的排序算法，通常采用快速排序实现，时间复杂度为平均 O(nlogn)。它可以对各种容器中的元素进行排序，并且可以自定义比较函数来改变排序的顺序。
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    std::sort(vec.begin(), vec.end());
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}
  • 稳定排序（ std::stable_sort ）及应用场景：
  • std::stable_sort 也是一种排序算法，与 std::sort 不同的是，它在排序过程中会保持相等元素的相对顺序。这在某些需要保持元素原始顺序的场景中非常有用，例如对包含多个相同元素的容器进行排序。
#include <iostream>
#include <algorithm>
#include <vector>

struct Person {
    std::string name;
    int age;
};

bool compareByAge(const Person& p1, const Person& p2) {
    return p1.age < p2.age;
}

int main() {
    std::vector<Person> people = {{"Alice", 25}, {"Bob", 30}, {"Charlie", 25}};
    std::stable_sort(people.begin(), people.end(), compareByAge);
    for (const Person& p : people) {
        std::cout << p.name << " " << p.age << std::endl;
    }
    return 0;
}
  1. 查找算法
  • 线性查找（ std::find ）的用法和局限性：
  • std::find 用于在给定范围内查找指定元素。它会依次遍历范围内的每个元素，直到找到目标元素或到达范围的末尾。线性查找的时间复杂度为 ，在大规模数据中效率较低。
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto it = std::find(vec.begin(), vec.end(), 3);
    if (it!= vec.end()) {
        std::cout << "找到了元素 3" << std::endl;
    } else {
        std::cout << "未找到元素 3" << std::endl;
    }
    return 0;
}
  • 二分查找（ std::binary_search ）的条件和优势：
  • std::binary_search 用于在已排序的范围内进行二分查找。它的时间复杂度为 ，比线性查找效率更高。但是，使用二分查找的前提是范围必须是已排序的。
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    bool found = std::binary_search(vec.begin(), vec.end(), 3);
    if (found) {
        std::cout << "找到了元素 3" << std::endl;
    } else {
        std::cout << "未找到元素 3" << std::endl;
    }
    return 0;
}
  1. 遍历算法
  • std::for_each 的多种使用方式：
  • std::for_each 可以对给定范围内的每个元素应用一个函数。可以使用函数对象、lambda 表达式或普通函数作为参数。
#include <iostream>
#include <algorithm>
#include <vector>

void printElement(int num) {
    std::cout << num << " ";
}

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    // 使用普通函数
    std::for_each(vec.begin(), vec.end(), printElement);
    std::cout << std::endl;

    // 使用 lambda 表达式
    std::for_each(vec.begin(), vec.end(), [](int num) {
        std::cout << num * 2 << " ";
    });
    std::cout << std::endl;
    return 0;
}
  1. 修改算法
  • std::transform 的功能和实际案例：
  • std::transform 可以将一个范围内的元素进行转换，并将结果存储在另一个范围内。它可以使用函数对象、lambda 表达式或普通函数作为转换函数。
#include <iostream>
#include <algorithm>
#include <vector>

int square(int num) {
    return num * num;
}

int main() {
    std::vector<int> vec1 = {1, 2, 3, 4, 5};
    std::vector<int> vec2(vec1.size());
    // 使用普通函数
    std::transform(vec1.begin(), vec1.end(), vec2.begin(), square);
    for (int num : vec2) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 使用 lambda 表达式
    std::vector<int> vec3(vec1.size());
    std::transform(vec1.begin(), vec1.end(), vec3.begin(), [](int num) {
        return num + 10;
    });
    for (int num : vec3) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}
  • std::fill 的应用场景：
  • std::fill 可以用指定的值填充一个范围内的元素。它通常用于初始化容器或设置特定的值。
 

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec(5);
    std::fill(vec.begin(), vec.end(), 10);
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}
  1. 其他算法
  • std::reverse 的作用和示例：
  • std::reverse 可以反转给定范围内的元素顺序。
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::reverse(vec.begin(), vec.end());
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}
  • std::copy 的不同用法：
  • std::copy 可以将一个范围内的元素复制到另一个范围内。它可以用于复制容器中的元素，或者将一个容器的部分元素复制到另一个容器中。
 

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec1 = {1, 2, 3, 4, 5};
    std::vector<int> vec2(vec1.size());
    std::copy(vec1.begin(), vec1.end(), vec2.begin());
    for (int num : vec2) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::vector<int> vec3;
    std::copy(vec1.begin(), vec1.begin() + 3, std::back_inserter(vec3));
    for (int num : vec3) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

二、算法的参数和返回值

  1. 理解各种算法的输入参数类型和含义。
  • 迭代器的作用和不同类型迭代器的区别：
  • 迭代器是 STL 算法的重要参数，它用于指定算法操作的范围。不同类型的迭代器具有不同的功能，例如输入迭代器只能用于读取数据，输出迭代器只能用于写入数据，而双向迭代器和随机访问迭代器则可以进行更复杂的操作。
  • 函数对象和 lambda 表达式在算法中的应用：
  • 函数对象和 lambda 表达式可以作为算法的参数，用于指定算法的操作方式。它们可以提供更灵活的编程方式，避免编写大量的重复代码。
#include <iostream>
#include <algorithm>
#include <vector>

class MultiplyByTwo {
public:
    int operator()(int num) const {
        return num * 2;
    }
};

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::vector<int> vec2(vec.size());
    // 使用函数对象
    std::transform(vec.begin(), vec.end(), vec2.begin(), MultiplyByTwo());
    for (int num : vec2) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 使用 lambda 表达式
    std::vector<int> vec3(vec.size());
    std::transform(vec.begin(), vec.end(), vec3.begin(), [](int num) {
        return num * 3;
    });
    for (int num : vec3) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}
  1. 分析算法的返回值类型及如何利用返回值。
  • 一些算法返回迭代器，例如 std::find 返回找到的元素的迭代器，或者范围的结束迭代器如果未找到。可以通过检查返回值是否等于结束迭代器来判断是否找到了目标元素。
  • 其他算法可能返回布尔值，如 std::binary_search 返回是否找到目标元素的布尔值。

三、算法与容器的结合

  1. 在不同容器（如 vector 、 list 、 set 等）上应用各种算法。
  • 不同的容器具有不同的特性，例如 vector 是动态数组，支持随机访问； list 是双向链表，插入和删除元素效率高； set 是有序集合，不允许重复元素。在不同的容器上应用算法时，需要考虑容器的特性对算法效率的影响。
#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
#include <set>

int main() {
    // 在 vector 上应用算法
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::sort(vec.begin(), vec.end());
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 在 list 上应用算法
    std::list<int> lst = {5, 4, 3, 2, 1};
    lst.sort();
    for (int num : lst) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 在 set 上应用算法
    std::set<int> s = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    for (int num : s) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}
  1. 考虑容器特性对算法效率的影响。
  • 例如，在 vector 上进行随机访问的算法效率较高，而在 list 上进行随机访问的算法效率较低。在选择算法时，需要根据容器的特性来选择最适合的算法。
  1. 处理容器中自定义类型数据时算法的使用方法。
  • 当容器中存储自定义类型的数据时，需要为自定义类型提供合适的比较函数、赋值运算符等，以便算法能够正确地操作这些数据。
#include <iostream>
#include <algorithm>
#include <vector>

struct Person {
    std::string name;
    int age;
};

bool compareByAge(const Person& p1, const Person& p2) {
    return p1.age < p2.age;
}

int main() {
    std::vector<Person> people = {{"Alice", 25}, {"Bob", 30}, {"Charlie", 25}};
    std::sort(people.begin(), people.end(), compareByAge);
    for (const Person& p : people) {
        std::cout << p.name << " " << p.age << std::endl;
    }
    return 0;
}

四、高级用法和技巧

  1. 组合多个算法实现复杂功能。
  • 例如先排序再查找：
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec = {5, 3, 8, 2, 1};
    std::sort(vec.begin(), vec.end());
    auto it = std::find(vec.begin(), vec.end(), 3);
    if (it!= vec.end()) {
        std::cout << "找到了元素 3" << std::endl;
    } else {
        std::cout << "未找到元素 3" << std::endl;
    }
    return 0;
}
  1. 利用算法的自定义比较函数。
  • 可以为算法提供自定义的比较函数，以满足特定的排序或查找需求。
#include <iostream>
#include <algorithm>
#include <vector>

struct Person {
    std::string name;
    int age;
};

bool compareByAge(const Person& p1, const Person& p2) {
    return p1.age < p2.age;
}

int main() {
    std::vector<Person> people = {{"Alice", 25}, {"Bob", 30}, {"Charlie", 25}};
    std::sort(people.begin(), people.end(), compareByAge);
    for (const Person& p : people) {
        std::cout << p.name << " " << p.age << std::endl;
    }
    return 0;
}
  1. 算法在大规模数据处理中的优化策略。
  • 可以考虑使用并行算法或其他优化技术来提高算法在处理大规模数据时的效率。

五、常见错误和陷阱

  1. 迭代器失效的情况及避免方法。
  • 在修改容器时可能导致的迭代器失效问题。例如，在 vector 中插入或删除元素时，可能会导致指向该容器的迭代器失效。为了避免迭代器失效，可以使用返回的新迭代器或者重新获取迭代器。
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto it = vec.begin();
    vec.insert(it + 2, 10);
    // 这里 it 已经失效，需要重新获取迭代器或者使用返回的新迭代器
    it = vec.begin();
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}
  1. 函数对象和 lambda 表达式的错误使用。
  • 例如，函数对象的参数类型不匹配、lambda 表达式的捕获列表错误等。
  1. 参数类型不匹配导致的编译错误。
  • 在使用算法时，需要确保参数的类型正确匹配。如果参数类型不匹配，可能会导致编译错误。

六、最佳实践

  1. 根据不同场景选择合适的算法。
  • 考虑算法的时间复杂度、空间复杂度、容器特性等因素，选择最适合的算法来解决问题。
  1. 提高算法效率的方法和注意事项。
  • 例如，避免不必要的复制、选择合适的数据结构等。
  1. 代码可读性和可维护性方面的考虑。

标签：std,begin,STL,信奥赛,C++,int,算法,vec,include
From： https://blog.csdn.net/w_yunlong/article/details/143054519

相关文章

  • （新！）c++多态
    C++ 多态多态按字面的意思就是多种形态。当类之间存在层次结构，并且类之间是通过继承关联时，就会用到多态。C++多态意味着调用成员函数时，会根据调用函数的对象的类型来执行不同的函数。下面的实例中，基类Shape被派生为两个类，如下所示：实例#include<iostream>usingnames......
  • 洛谷知识点——C++ 11 实现一次性输出多行文本
    完整语法是R"deli(...)deli"。（其中deli并不是固定的，那里其实是一个用户自定义的字符序列，最多16个基本字符，不可含反斜线，空格和小括号。）故P1000超级玛丽游戏解法为#include<iostream>usingnamespacestd;intmain(){cout<<R"(********......
  • C++基础
    1、注释单行注释：//这是注释多行注释：/*这是注释*/2、变量 数据类型变量名=变量初始值； 3、常量宏常量：通常在文件开头定义#define常量名常量值const修饰的静态变量，表示一个常量，不可修改。const数据类型常量名=常量值#include<iostream>usingna......
  • 「图::连通」详解并查集并实现对应的功能 / 手撕数据结构（C++）
    目录概述成员变量创建销毁根节点访问路径压缩启发式合并复杂度Code概述并查集，故名思议，能合并、能查询的集合,在图的连通性问题和许多算法优化上着广泛的使用。这是一个什么数据结构呢？一般来讲，并查集是由一系列集合组成的集合群。其中，每个集合都有一个根节点，它的......
  • 学习记录，这该死的c++
    最近还是比较懈怠，除了老师布置的作业其他的也是匆匆过一眼至于代码方面最主要的问题还是不理解该怎么表达。总的来说还是要在多沉淀。为什么会有知道敲代码但是不知道该怎么成功表达这个问题啊？还是不能把代码敲得精简一些可以来个人教我怎么敲关系符号吗？运用的还不是很熟练......
  • 【C++贪心】2086. 喂食仓鼠的最小食物桶数|1622
    本文涉及知识点C++贪心LeetCode2086.喂食仓鼠的最小食物桶数给你一个下标从0开始的字符串hamsters，其中hamsters[i]要么是：‘H’表示有一个仓鼠在下标i，或者’.’表示下标i是空的。你将要在空的位置上添加一定数量的食物桶来喂养仓鼠。如果仓鼠的左边或右边......
  • 南沙C++信奥赛陈老师解一本通题 1286：怪盗基德的滑翔翼
    ​【题目描述】怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。有一天，怪盗基德像往常一样偷走了一颗珍贵的钻石，不料却被柯南小朋友识破了伪......
  • C++之子类继承与父类构造
    C++之子类继承与父类构造文章目录C++之子类继承与父类构造1.问题引出2.原则3.解析3.1单一继承3.1.1父类无参构造函数3.1.1.1子类无定义构造函数3.1.1.2子类定义构造函数3.1.2父类存在无参构造函数和有参构造函数3.1.3父类仅存在有参构造函数3.2链式继承3.3多继承......
  • 【C++】C++中的继承，看这一篇就够了
    【C++】C++中的继承，看这一篇就够了一.继承的概念及定义继承的概念继承定义继承关系和访问限定符继承基类成员访问方式的变化二.基类和派生类对象赋值转换三.继承中的作用域四.派生类的默认成员函数五.继承与友元六.继承与静态成员七.复杂的菱形继承及菱形虚拟继承......
  • 移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——13.map&&set(无习题）
    C++中的set和map容器详细总结1.概述C++标准模板库（STL）提供了多种关联容器，用于管理键值对和集合的数据。其中，set和map是最常用的两种关联容器。set用于存储唯一的元素集合，而map则用于存储键值对，其中每个键都是唯一的。它们都使用红黑树（自平衡二叉搜索树）作为底......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99