C++ STL入门与实践：向量、set与string操作详解

本篇C++语言STL学习笔记详细介绍了《算法笔记》中关于C++标准模板库(STL)的几个核心概念和用法，旨在帮助准备PAT相关考试的读者提升基础技能。主要内容涵盖了vector、set和string三种常用容器。 1. **vector**： - 引用头文件：`#include <vector>`，使用`std`命名空间。 - 定义：vector是一个动态数组，可以变长，如`vector<int> name;` 或 `vector<vector<int>> name;`。`vector vi[100];` 是一种旧的创建方式，但不推荐。 - 元素访问：通过下标`vi[i]`或迭代器`vector::iterator it`进行访问。例如，`it = vi.begin()`获取第一个元素地址，`*(vi.begin()+i)`与`vi[i]`等效。注意仅在vector和string中支持`it += 3`这样的操作。 - 常用函数： - `push_back()`：在末尾添加元素，时间复杂度O(1)。 - `pop_back()`：删除末尾元素，O(1)。 - `size()`：返回元素个数，O(1)。 - `clear()`：清空所有元素，时间复杂度O(N)。 - `insert()`和`erase()`：分别用于插入和删除元素，时间复杂度根据具体操作不同，可能为O(N)。 2. **set**： - 特点：自动有序递增，且不含重复元素。 - 定义：如`set<int> set_name;`。 - 访问：仅通过迭代器`set::iterator it`，不能像vector那样使用下标。 - 常用函数： - `insert(x)`：插入元素，时间复杂度O(logN)。 - `find(value)`：查找元素，时间复杂度O(logN)。 - `erase()`：删除指定元素，时间复杂度取决于删除位置，可能为O(1)或O(logN)。 - 常见用途：自动去重并保持升序排列。 3. **string**： - 引用头文件：`#include <string>`（注意与`string.h`的区别）。 - 定义：如`string str;`。 - 访问：可以通过下标访问单个字符，也可以用`cin`和`cout`输入输出整个字符串。 - 注意：set不支持对string类型的元素进行操作。 总结来说，这篇学习笔记涵盖了C++ STL中的关键数据结构及其操作，包括vector的动态数组特性、set的无序存储和去重功能以及string的字符串处理。这些知识点对于理解和解决许多实际问题至关重要，尤其在编程算法和数据结构的场景中。理解并熟练运用STL能够大大提高编程效率和代码质量。