Chapter 16 string 类和标准模板库
16.1 string 类
我们在第 4 章已经初步接触了 C++ 标准库中的 string 类。与 C 语言风格的、以空字符结尾的字符数组（C-风格字符串）相比，string 类提供了更强大、更安全、更方便的字符串处理方式。
优点:
- 自动内存管理:
string对象会自动管理存储字符串所需的内存，无需手动分配和释放，避免了许多 C 风格字符串常见的内存错误（如缓冲区溢出）。 - 丰富的操作: 提供了大量的成员函数用于字符串的查找、拼接、比较、修改、插入、删除等操作。
- 安全性: 成员函数通常会进行边界检查（如
at()方法），或者提供明确定义的操作行为。 - 与 STL 兼容: 可以方便地与标准模板库 (STL) 中的算法和容器一起使用。
string 类实际上是模板类 basic_string<char> 的一个 typedef（类型别名）。它定义在 <string> 头文件中。
1 |
16.1.1 构造字符串
创建 string 对象有多种方式（构造函数）：
- 默认构造函数: 创建一个空字符串。
1
std::string s1; // s1 是一个空字符串 ""
- *从 C 风格字符串 (const char)**: 用一个 C 风格字符串来初始化
string对象。1
2
3std::string s2 = "Hello"; // 从字符串字面值初始化
const char* c_str = "World";
std::string s3(c_str); // 从 const char* 变量初始化 - 复制构造函数: 用另一个
string对象来初始化。1
2std::string s4 = s2; // s4 的内容是 "Hello"
std::string s5(s4); // s5 的内容也是 "Hello" - 从 C 风格字符串的部分内容: 用 C 风格字符串的前
n个字符初始化。1
2const char* long_cstr = "Programming";
std::string s6(long_cstr, 7); // 用 "Programming" 的前 7 个字符初始化 s6，内容是 "Program" - 从
string对象的部分内容 (子字符串): 用另一个string对象的子字符串初始化。1
2std::string s7 = "Example String";
std::string s8(s7, 8, 6); // 从 s7 的索引 8 开始，取 6 个字符初始化 s8，内容是 "String" - 填充构造函数: 用
n个重复的字符c初始化。1
std::string s9(10, '-'); // s9 的内容是 "----------"
- 从迭代器范围: 用一对指向字符序列的迭代器（例如来自另一个容器或 C 风格数组）来初始化。
1
2
3
4
5char char_array[] = {'T', 'e', 's', 't'};
std::string s10(char_array, char_array + sizeof(char_array)); // s10 内容是 "Test"
std::vector<char> char_vec = {'D', 'a', 't', 'a'};
std::string s11(char_vec.begin(), char_vec.end()); // s11 内容是 "Data" - 使用初始化列表 (C++11):
1
2std::string s12 = {'I', 'n', 'i', 't'}; // s12 内容是 "Init"
std::string s13 {"List"}; // s13 内容是 "List"
示例:
1 |
|
16.1.2 string 类输入
从输入流（如 cin）读取数据到 string 对象主要有两种方式：
使用
operator>>:行为类似于读取 C 风格字符串或基本数据类型。
它会跳过开头的所有空白字符（空格、制表符、换行符）。
然后读取非空白字符，直到遇到下一个空白字符为止。
读取的内容（不包括结尾的空白字符）存储在
string对象中。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main() {
std::string word1, word2;
std::cout << "Enter two words separated by space: "; // 例如输入 "Hello World"
std::cin >> word1 >> word2;
std::cout << "Word 1: " << word1 << std::endl; // 输出 "Hello"
std::cout << "Word 2: " << word2 << std::endl; // 输出 "World"
// 演示跳过空白
std::stringstream ss(" LeadingSpaces Word");
std::string temp;
ss >> temp;
std::cout << "After skipping spaces: " << temp << std::endl; // 输出 "LeadingSpaces"
return 0;
}
使用
getline()函数:用于读取一整行输入，直到遇到指定的分隔符（默认为换行符
\n）。不会跳过开头的空白字符。
读取的内容（不包括分隔符本身）存储在
string对象中。分隔符会从输入流中被读取并丢弃。
*函数原型:**
1
2
3
4
std::istream& getline(std::istream& is, std::string& str, char delim = '\n');1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main() {
std::string line1, line2;
std::cout << "Enter a line of text: ";
// 注意：如果之前有 >> 操作，可能需要清除缓冲区中的换行符
// std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
getline(std::cin, line1); // 读取整行，直到按 Enter
std::cout << "Enter another line: ";
getline(std::cin, line2);
std::cout << "Line 1: " << line1 << std::endl;
std::cout << "Line 2: " << line2 << std::endl;
return 0;
}
混合使用 >> 和 getline() 的问题:
当 >> 读取输入后，它会将导致读取结束的空白字符（通常是换行符）留在输入缓冲区中。如果紧接着调用 getline()，它会立即读到这个换行符，认为读取到空行，然后结束。
解决方法: 在 >> 之后、getline() 之前，清除缓冲区中残留的换行符。常用的方法是使用 cin.ignore()：
1 |
|
16.1.3 使用字符串
string 类提供了丰富的成员函数来操作字符串：
赋值: 使用
operator=。1
2
3
4
5std::string s1 = "Initial";
std::string s2;
s2 = s1; // s2 内容变为 "Initial"
s2 = "New Value"; // s2 内容变为 "New Value"
s2 = 'C'; // s2 内容变为 "C"拼接/连接: 使用
operator+或operator+=。可以与string对象、C 风格字符串或单个字符拼接。1
2
3
4
5std::string first = "John";
std::string last = "Doe";
std::string full = first + " " + last; // full 是 "John Doe"
first += "athan"; // first 变为 "Johnathan"
full += '!'; // full 变为 "John Doe!"比较: 使用关系运算符 (
==,!=,<,>,<=,>=)。比较是按字典顺序进行的。1
2
3
4
5
6
7
8std::string str1 = "Apple";
std::string str2 = "Banana";
if (str1 < str2) { // true
std::cout << str1 << " comes before " << str2 << std::endl;
}
if (str1 == "Apple") { // true
std::cout << "str1 is Apple" << std::endl;
}获取长度/大小: 使用
length()或size()方法（两者等价）。返回字符串中的字符数。1
2
3std::string msg = "Hello";
std::cout << "Length: " << msg.length() << std::endl; // 输出 5
std::cout << "Size: " << msg.size() << std::endl; // 输出 5访问字符:
operator[]: 提供快速访问，但不进行边界检查。访问越界是未定义行为。at(): 提供边界检查的访问。如果索引越界，会抛出std::out_of_range异常。1
2
3
4
5
6
7
8
9
10
11
12std::string word = "World";
char first_char = word[0]; // 'W'
char last_char = word[word.length() - 1]; // 'd'
// word[5] = '!'; // 危险！越界访问，未定义行为
try {
char c = word.at(1); // 'o'
word.at(0) = 'J'; // word 变为 "Jorld"
c = word.at(10); // 越界，将抛出异常
} catch (const std::out_of_range& oor) {
std::cerr << "Out of Range error: " << oor.what() << std::endl;
}
查找:
string提供了多种查找方法：find(substr, pos=0): 从索引pos开始查找子串substr第一次出现的位置。rfind(substr, pos=npos): 从索引pos向前查找子串substr最后一次出现的位置。find_first_of(chars, pos=0): 从pos开始查找chars中任何一个字符第一次出现的位置。find_last_of(chars, pos=npos): 从pos向前查找chars中任何一个字符最后一次出现的位置。find_first_not_of(chars, pos=0): 从pos开始查找第一个不在chars中的字符的位置。find_last_not_of(chars, pos=npos): 从pos向前查找最后一个不在chars中的字符的位置。所有查找方法如果找到，返回匹配的起始索引；如果找不到，返回
std::string::npos(一个静态成员常量，通常是-1或最大无符号整数值)。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int main() {
std::string text = "The quick brown fox jumps over the lazy dog.";
std::string search_str = "the";
std::string vowels = "aeiouAEIOU";
size_t pos = text.find(search_str); // 查找 "the"
if (pos != std::string::npos) {
std::cout << "'" << search_str << "' found at index: " << pos << std::endl; // 输出 35
} else {
std::cout << "'" << search_str << "' not found." << std::endl;
}
pos = text.find("The"); // 查找 "The"
if (pos != std::string::npos) {
std::cout << "'The' found at index: " << pos << std::endl; // 输出 0
}
pos = text.find_first_of(vowels); // 查找第一个元音
if (pos != std::string::npos) {
std::cout << "First vowel '" << text[pos] << "' found at index: " << pos << std::endl; // 输出 'e' at 2
}
pos = text.find_first_not_of(" "); // 查找第一个非空格
if (pos != std::string::npos) {
std::cout << "First non-space '" << text[pos] << "' found at index: " << pos << std::endl; // 输出 'T' at 0
}
return 0;
}
修改:
insert(pos, str): 在索引pos处插入字符串str。erase(pos, count): 从索引pos开始删除count个字符。replace(pos, count, str): 将从pos开始的count个字符替换为str。append(str): 在末尾追加str(等价于+=)。assign(str): 替换整个字符串内容为str(等价于=)。1
2
3
4
5std::string phrase = "Hello world";
phrase.insert(6, "beautiful "); // "Hello beautiful world"
phrase.erase(0, 6); // "beautiful world"
phrase.replace(0, 9, "Wonderful"); // "Wonderful world"
phrase.append("!"); // "Wonderful world!"
获取 C 风格字符串:
c_str(): 返回一个指向以空字符结尾的const char*数组的指针，内容与string对象相同。返回的指针指向的内存在string对象被修改或销毁后可能失效。data(): 类似c_str()，但在 C++11 之前不保证以空字符结尾（C++11 起保证结尾有\0）。当你需要将
string对象传递给需要const char*的 C 风格函数时，这两个方法非常有用。1
2
3
4
5
6
7
8
int main() {
std::string cpp_str = "C++ String";
printf("Using c_str(): %s\n", cpp_str.c_str());
return 0;
}
16.1.4 string 还提供了哪些功能
std::string 类还有许多其他功能，包括：
- 容量管理:
-
capacity(): 返回当前分配的内存容量（可能大于size()）。 -
reserve(n): 请求至少为n的容量。如果n大于当前容量，可能重新分配内存。 -
shrink_to_fit()(C++11): 请求减少容量以匹配当前大小。 -
clear(): 清空字符串内容（size()变为 0）。 -
empty(): 检查字符串是否为空（size() == 0）。
-
- 迭代器: 提供
begin(),end(),rbegin(),rend()等迭代器，允许像遍历容器一样遍历字符串中的字符，可以配合 STL 算法使用。 - 子字符串:
substr(pos, count): 返回一个新的string对象，包含从pos开始的count个字符的子串。 - 比较:
compare()方法提供比关系运算符更详细的比较选项。 - 数值转换 (C++11):
<string>头文件还包含stoi,stol,stod,to_string等函数，用于字符串和数值类型之间的转换。
要了解 string 类的所有功能，建议查阅 C++ 参考文档（如 cppreference.com）。
16.1.5 字符串种类
std::string 是 std::basic_string<char> 的别名，用于处理基于 char 的窄字符字符串（通常是 ASCII 或 UTF-8 编码）。
C++ 标准库还提供了处理其他字符类型的 basic_string 特化版本：
-
std::wstring:basic_string<wchar_t>的别名，用于处理宽字符 (wchar_t) 字符串，常用于 Windows API 中的 Unicode。 -
std::u16string(C++11):basic_string<char16_t>的别名，用于处理 UTF-16 编码的字符串。 -
std::u32string(C++11):basic_string<char32_t>的别名，用于处理 UTF-32 编码的字符串。
这些宽字符串类具有与 std::string 类似的操作接口，但处理的字符类型不同。
1 |
|
选择哪种字符串类型取决于你的应用场景和需要处理的字符集。在现代 C++ 中，如果需要处理 Unicode，通常推荐使用 UTF-8 编码的 std::string，并配合相应的 Unicode 处理库。
16.2 智能指针模板类
在 C++ 中，使用 new 分配动态内存后，必须使用 delete 来释放它，否则会导致**内存泄漏 (Memory Leak)**。手动管理内存容易出错，尤其是在复杂的代码路径、异常处理或资源共享的情况下。忘记 delete、重复 delete 或使用悬挂指针（指向已释放内存的指针）都是常见的错误来源。
为了解决这个问题，C++ 标准库（在 <memory> 头文件中）提供了一系列智能指针 (Smart Pointers) 模板类。智能指针是行为类似于指针的类对象，但它们能自动管理所指向的动态分配的内存。当智能指针本身离开作用域（例如函数结束、对象销毁）或被重新赋值时，它会自动调用 delete（或自定义的删除器）来释放其管理的内存。这极大地简化了动态内存管理，提高了程序的健壮性，并有助于实现 RAII（资源获取即初始化）。
C++11 引入了三种主要的智能指针类型：
-
std::unique_ptr<T>: 实现独占所有权 (Exclusive Ownership) 或严格所有权模型。在任何时候，只有一个unique_ptr可以指向给定的资源。当unique_ptr被销毁或重置时，资源被释放。它不能被复制，但可以被**移动 (Moved)**。 -
std::shared_ptr<T>: 实现共享所有权 (Shared Ownership) 模型。允许多个shared_ptr指向同一个资源。内部维护一个**引用计数 (Reference Count)**，记录有多少个shared_ptr指向该资源。只有当最后一个指向资源的shared_ptr被销毁或重置时，资源才会被释放。 -
std::weak_ptr<T>: 是一种非拥有 (Non-owning) 的智能指针，它指向由shared_ptr管理的资源，但不增加引用计数。它主要用于解决shared_ptr可能遇到的循环引用 (Cyclic Reference) 问题，并用于观察资源是否存在。
16.2.1 使用智能指针
std::unique_ptr
unique_ptr 是轻量级的智能指针，开销几乎与原始指针相同。它是管理动态分配资源的首选方式，除非你需要共享所有权。
创建:
- 推荐方式 (C++14 及以后): 使用
std::make_unique<T>(args...)。它更安全（避免了某些异常安全问题）且可能更高效。1
2
3
4
5
6
7
8
// 创建指向 int 的 unique_ptr
auto uptr_int = std::make_unique<int>(10); // 指向值为 10 的 int
// 创建指向 string 的 unique_ptr
auto uptr_str = std::make_unique<std::string>("Hello"); // 指向 "Hello" - C++11 方式: 直接使用
new。1
2std::unique_ptr<int> uptr_int_cpp11(new int(20));
std::unique_ptr<std::string> uptr_str_cpp11(new std::string("World"));
所有权转移 (移动): unique_ptr 不能复制，但可以通过 std::move() 转移所有权。
1 | std::unique_ptr<int> ptr1 = std::make_unique<int>(100); |
函数可以返回 unique_ptr，这会自动触发移动语义，将所有权转移给调用者。
1 | std::unique_ptr<std::string> create_string() { |
使用: 像普通指针一样使用 * 和 ->。
1 | std::unique_ptr<std::string> uptr = std::make_unique<std::string>("Test"); |
其他操作:
-
get(): 返回指向被管理对象的原始指针（但不转移所有权）。小心使用，避免手动delete这个指针。 -
reset(p): 销毁当前管理的对象（如果有），并接管指针p指向的新对象。 -
reset(): 销毁当前管理的对象，并将unique_ptr置为空。 -
release(): 放弃对指针的所有权，返回原始指针，并将unique_ptr置为空。调用者负责手动delete返回的指针。
用于数组: unique_ptr 可以管理动态分配的数组。
1 | // 创建指向包含 5 个 int 的数组的 unique_ptr |
自定义删除器: 可以为 unique_ptr 指定自定义的删除器，用于执行非标准的资源释放操作（如关闭文件句柄）。
1 |
|
std::shared_ptr
shared_ptr 用于资源可能被多个指针共享所有权的场景。
创建:
- 推荐方式: 使用
std::make_shared<T>(args...)。它通常更高效，因为它可以在一次内存分配中同时为对象和引用计数控制块分配内存。1
2auto sptr_int = std::make_shared<int>(50);
auto sptr_str = std::make_shared<std::string>("Shared"); - 使用
new:1
2
3
4
5std::shared_ptr<int> sptr_int_new(new int(60));
// 注意：不要将同一个原始指针用于初始化多个 shared_ptr，应通过复制已有的 shared_ptr 来共享
// int* raw_ptr = new int(70);
// std::shared_ptr<int> sp1(raw_ptr);
// std::shared_ptr<int> sp2(raw_ptr); // 错误！会导致重复 delete
共享所有权和引用计数: 复制 shared_ptr 会增加引用计数，销毁或重置 shared_ptr 会减少引用计数。
1 | std::shared_ptr<int> sp1 = std::make_shared<int>(100); |
使用: 与 unique_ptr 类似，使用 * 和 ->。
其他操作:
-
get(): 返回原始指针。 -
reset()/reset(p): 减少当前对象的引用计数（如果为 0 则删除），并可选地接管新指针p。 -
use_count(): 返回当前的引用计数值（主要用于调试）。
循环引用问题: 如果两个对象通过 shared_ptr 相互引用，它们的引用计数永远不会变为 0，即使没有外部指针指向它们，也会导致内存泄漏。
1 | struct NodeB; // 前向声明 |
解决方案: 使用 std::weak_ptr 打破循环。
std::weak_ptr
weak_ptr 用于“观察”由 shared_ptr 管理的对象，但它本身不拥有对象，也不影响对象的生命周期（不改变引用计数）。
创建: 只能从 shared_ptr 或另一个 weak_ptr 创建。
1 | std::shared_ptr<int> sp = std::make_shared<int>(10); |
使用:
-
expired(): 检查所观察的对象是否已被销毁（对应的shared_ptr引用计数是否为 0）。 lock(): 关键方法。尝试获取一个指向所观察对象的shared_ptr。- 如果对象仍然存在，返回一个有效的
shared_ptr（并增加引用计数）。 - 如果对象已被销毁，返回一个空的
shared_ptr。
这是访问weak_ptr指向对象的安全方式。
- 如果对象仍然存在，返回一个有效的
1 | if (wp.expired()) { |
解决循环引用: 在循环引用的场景中，让其中一个指针（或两个）成为 weak_ptr。
1 | struct NodeB_weak; |
16.2.2 有关智能指针的注意事项
- 不要混用智能指针和原始指针: 避免将
get()返回的原始指针传递给另一个智能指针或手动delete。 - 优先使用
make_unique和make_shared: 更安全、可能更高效。 -
shared_ptr的性能开销: 引用计数是原子操作，在多线程环境下有一定开销。shared_ptr对象本身也比unique_ptr或原始指针大（需要存储指向控制块的指针）。 -
this指针问题: 不要在类的构造函数中将this指针直接传递给shared_ptr的构造函数。如果需要让类自身能够创建指向自己的shared_ptr，应继承自std::enable_shared_from_this<YourClass>并使用shared_from_this()方法。
16.2.3 unique_ptr 为何优于 auto_ptr
C++98 引入了 std::auto_ptr，它是 unique_ptr 的前身，也试图实现独占所有权。但 auto_ptr 有一个严重的设计缺陷：它的复制构造函数和赋值运算符会转移所有权。
1 | std::auto_ptr<int> ap1(new int(10)); |
这种隐式的、破坏性的复制行为非常危险，尤其是在将 auto_ptr 放入容器或作为函数参数按值传递时，会导致意外的所有权丢失。
C++11 引入了移动语义，使得 unique_ptr 可以通过显式的 std::move 来安全地转移所有权，同时禁止了复制操作，从而避免了 auto_ptr 的问题。
auto_ptr 已在 C++11 中被废弃，并在 C++17 中被移除。应始终使用 unique_ptr 替代它。
16.2.4 选择智能指针
- 默认选择
std::unique_ptr: 当你需要管理一个动态分配的资源，并且不需要共享其所有权时，unique_ptr是最简单、最高效的选择。 - 使用
std::shared_ptr: 当资源需要被多个所有者共享生命周期时（例如，在数据结构中多个部分可能引用同一个节点，或者回调函数需要确保某个对象在其执行期间存活）。 - 使用
std::weak_ptr: 当你需要观察一个由shared_ptr管理的对象，但不想影响其生命周期时，特别是为了打破shared_ptr之间的循环引用。
智能指针是现代 C++ 中管理动态资源的核心工具，极大地提高了代码的安全性和简洁性。
16.3 标准模板库（STL）
标准模板库 (Standard Template Library, STL) 是 C++ 标准库的一个重要组成部分，它提供了一套通用的模板类和函数，用于实现常用的数据结构和算法。STL 的核心思想是**泛型编程 (Generic Programming)**，即代码独立于特定的数据类型，可以应用于多种类型。
STL 主要由三个核心组件构成：
- 容器 (Containers): 用于存储数据的模板类。例如
vector,list,deque,set,map等。它们封装了数据结构，并提供了管理元素的方法。 - 算法 (Algorithms): 用于处理容器中数据的模板函数。例如
sort,find,copy,for_each等。这些算法通常通过迭代器作用于容器中的元素范围。 - 迭代器 (Iterators): 行为类似于指针的对象，用于遍历容器中的元素，并作为连接容器和算法的桥梁。
本节将重点介绍 STL 中最常用的容器之一：vector，以及适用于多种容器的通用操作。
16.3.1 模板类 vector
std::vector 是一个模板类，定义在 <vector> 头文件中。它实现了一个**动态数组 (Dynamic Array)**，可以根据需要自动增长或收缩大小。
特点:
- 动态大小: 可以在运行时添加或删除元素，
vector会自动管理内存。 - 随机访问: 支持通过索引 (
[]或at()) 快速访问任何位置的元素，时间复杂度为 O(1)。 - 连续存储: 元素在内存中是连续存储的，这使得通过指针或迭代器进行遍历非常高效，并能与需要连续内存的 C 风格 API 兼容。
- 尾部插入/删除高效: 在末尾添加 (
push_back) 或删除 (pop_back) 元素通常很高效（摊销时间复杂度为 O(1)）。 - 中间插入/删除低效: 在中间或开头插入或删除元素可能需要移动后续所有元素，时间复杂度为 O(N)。
基本用法:
1 |
|
16.3.2 可对容器执行的操作
许多 STL 容器（包括 vector）都支持一组常见的操作：
-
size(): 返回容器中元素的数量。类型通常是size_type(一种无符号整型)。 -
empty(): 检查容器是否为空。如果size() == 0，返回true，否则返回false。 -
operator[]: 通过索引访问元素（仅适用于vector,deque,string,array）。不进行边界检查。 -
at(): 通过索引访问元素（仅适用于vector,deque,string,array）。进行边界检查，越界时抛出std::out_of_range异常。 -
front(): 返回对第一个元素的引用。容器不能为空。 -
back(): 返回对最后一个元素的引用。容器不能为空。 -
push_back(value): (仅适用于vector,deque,list,string) 在容器末尾添加一个值为value的元素。 -
pop_back(): (仅适用于vector,deque,list,string) 删除容器末尾的元素。容器不能为空。
示例:
1 |
|
16.3.3 对容器可执行的其他操作
除了基本操作，STL 容器还提供了其他一些有用的方法，其中许多涉及到**迭代器 (Iterators)**。迭代器是泛化的指针，用于指定容器中的位置或范围。
迭代器获取:
-
begin(): 返回指向容器第一个元素的迭代器。 -
end(): 返回指向容器末尾之后 (past-the-end) 位置的迭代器。它不指向任何有效元素，常用于标记范围的结束。 -
rbegin(),rend(): 返回反向迭代器，用于从后向前遍历。 -
cbegin(),cend(),crbegin(),crend()(C++11): 返回const迭代器，用于只读访问。
-
插入 (
insert()): 在指定位置插入元素。需要一个指向插入位置的迭代器。-
insert(iterator pos, const value_type& val): 在pos之前插入val。返回指向新插入元素的迭代器。 -
insert(iterator pos, size_type n, const value_type& val): 在pos之前插入n个val。 -
insert(iterator pos, InputIt first, InputIt last): 在pos之前插入来自迭代器范围[first, last)的元素。
-
删除 (
erase()): 删除指定位置或范围的元素。需要迭代器。-
erase(iterator pos): 删除pos指向的元素。返回指向被删除元素之后元素的迭代器。 -
erase(iterator first, iterator last): 删除范围[first, last)内的元素。返回指向最后一个被删除元素之后元素的迭代器。
-
清空 (
clear()): 删除容器中的所有元素。size()变为 0。交换 (
swap()):c1.swap(c2)或std::swap(c1, c2)。高效地交换两个容器的内容。对于vector等容器，通常只交换内部指针和大小信息，速度很快。赋值 (
assign()): 替换容器的全部内容。-
assign(size_type n, const value_type& val): 赋值为n个val。 -
assign(InputIt first, InputIt last): 赋值为来自迭代器范围[first, last)的元素。 -
assign(initializer_list<value_type> il)(C++11): 从初始化列表赋值。
-
容量管理 (主要用于
vector,string,deque):-
capacity(): 返回当前已分配内存能够容纳的元素数量。 -
reserve(n): 请求将容量增加到至少n。如果n大于当前容量，可能发生内存重新分配（这会导致所有迭代器、指针和引用失效）。 -
shrink_to_fit()(C++11): 请求减少容量以匹配size()。不保证一定减少。
-
示例 (使用迭代器):
1 |
|
16.3.4 基于范围的 for 循环（C++11）
C++11 引入了一种更简洁、更不易出错的遍历容器（以及其他支持 begin() 和 end() 的序列）的方式：**基于范围的 for 循环 (Range-based for loop)**。
语法:
1 | for ( declaration : range_expression ) { |
-
range_expression: 一个可以提供begin()和end()迭代器的对象（如 STL 容器、数组、初始化列表，或定义了相应成员/非成员函数的自定义类型）。 -
declaration: 声明一个变量，其类型应与range_expression中的元素类型兼容。每次循环迭代，range_expression中的下一个元素会被复制或引用到这个变量中。
常用形式:
- 只读访问 (推荐): 使用
const auto&避免不必要的复制，并确保不会意外修改元素。1
2
3
4
5std::vector<std::string> names = {"Alice", "Bob", "Charlie"};
for (const auto& name : names) {
std::cout << name << " ";
}
// 输出: Alice Bob Charlie - 修改元素: 使用
auto&获取元素的引用，允许在循环中修改容器内容。1
2
3
4
5
6
7
8
9std::vector<int> nums = {1, 2, 3, 4};
for (auto& num : nums) {
num *= 2; // 将每个元素乘以 2
}
// nums 现在是 {2, 4, 6, 8}
for (const auto& num : nums) {
std::cout << num << " ";
}
// 输出: 2 4 6 8 - 复制元素: 使用
auto(或具体类型) 会将每个元素复制到循环变量中。对循环变量的修改不会影响容器中的原始元素。1
2
3
4
5
6
7
8
9
10std::vector<int> data = {5, 10, 15};
for (auto val : data) {
val += 1; // 只修改了副本 val，data 不变
std::cout << val << " "; // 输出 6 11 16
}
std::cout << std::endl;
for (const auto& d : data) {
std::cout << d << " "; // 输出 5 10 15 (原始数据未变)
}
std::cout << std::endl;
基于范围的 for 循环极大地简化了遍历容器的代码，使其更易读、更安全（避免了迭代器失效或索引越界等常见错误）。
16.4 泛型编程
泛型编程 (Generic Programming) 是一种编程范式，旨在编写独立于特定数据类型的代码。其目标是创建可重用的组件（如函数或类），这些组件可以处理多种不同的数据类型，而无需为每种类型重写代码。C++ 中的模板 (Templates) 是实现泛型编程的主要机制。
标准模板库 (STL) 就是泛型编程思想的集中体现。它通过模板定义了通用的容器、算法和迭代器，使得我们可以用同样的方式操作 vector<int>, list<string> 或其他自定义类型的数据。
16.4.1 为何使用迭代器
STL 的设计核心是将数据存储（容器）和数据操作（算法）分离开来。但是，算法如何才能访问不同容器（如 vector, list, deque）中的数据呢？不同的容器内部结构可能完全不同。
迭代器 (Iterators) 就是解决这个问题的关键。迭代器是一种泛化的指针，它提供了一种统一的方式来遍历容器中的元素，并访问元素的值，而无需暴露容器的内部实现细节。
- 抽象访问: 算法不直接操作容器，而是通过迭代器来访问容器中的元素范围。
- 统一接口: 所有容器都提供符合特定标准的迭代器接口（如
begin(),end(),++前进,*解引用）。 - 灵活性: 算法只需要知道如何使用迭代器，就可以应用于任何提供兼容迭代器的容器。例如，
std::sort算法可以对vector,deque甚至普通数组（通过指针，指针也是一种迭代器）进行排序，只要它们提供所需的迭代器类型。
1 |
|
在这个例子中，同一个 std::find 算法可以作用于 vector, list 和 C 风格数组，因为它操作的是迭代器（或指针）定义的范围，而不是容器本身。
16.4.2 迭代器类型
STL 定义了五种主要的迭代器类别，它们根据提供的操作能力进行区分：
输入迭代器 (Input Iterator):
- 最基本的迭代器，只能向前移动 (
++)。 - 只能读取 (
*) 所指向的元素一次（读取后再次读取同一位置的结果未定义）。 - 支持比较相等 (
==,!=)。 - 用于单遍扫描算法，例如
std::find,std::accumulate。istream_iterator是一个例子。
- 最基本的迭代器，只能向前移动 (
输出迭代器 (Output Iterator):
- 只能向前移动 (
++)。 - 只能写入 (
*it = value) 所指向的位置一次。 - 不支持比较。
- 用于将结果写入目标，例如
std::copy的第三个参数。ostream_iterator是一个例子。
- 只能向前移动 (
前向迭代器 (Forward Iterator):
- 结合了输入和输出迭代器的部分能力（但更强）。
- 可以向前移动 (
++)。 - 可以多次读取 (
*) 同一个元素。 - 可以多次写入 (
*it = value) 同一个元素（如果指向的是非const元素）。 - 支持比较相等 (
==,!=)。 - 用于需要多次遍历同一范围的算法。
std::forward_list提供前向迭代器。unordered容器也提供至少前向迭代器。
双向迭代器 (Bidirectional Iterator):
- 继承了前向迭代器的所有能力。
- 增加了向后移动 (
--) 的能力。 -
std::list,std::set,std::map提供双向迭代器。
随机访问迭代器 (Random Access Iterator):
- 最强大的迭代器，继承了双向迭代器的所有能力。
- 支持算术运算：
it + n,it - n,it += n,it -= n(快速移动到任意位置)。 - 支持下标运算：
it[n](等价于*(it + n))。 - 支持比较大小 (
<,>,<=,>=)。 - 支持计算两个迭代器之间的距离 (
it2 - it1)。 -
std::vector,std::deque,std::array,std::string提供随机访问迭代器。普通指针也是随机访问迭代器。
算法会根据其需要指定它所要求的最低迭代器类别。例如，std::reverse 需要双向迭代器，而 std::sort 需要随机访问迭代器（因为它需要高效地交换任意位置的元素）。
16.4.3 迭代器层次结构
这五种迭代器类型形成了一个层次结构，后面的类别拥有前面类别所有（或等价）的功能：
1 | Input Iterator Output Iterator |
这意味着，如果一个算法需要前向迭代器，你可以传递给它前向、双向或随机访问迭代器。但如果算法需要随机访问迭代器，你就不能传递给它双向或前向迭代器。
16.4.4 概念、改进和模型 (Concepts, Refinements, and Models)
STL 的设计基于概念 (Concepts) 的思想。一个概念是一组对类型的要求（包括类型必须提供的操作、类型别名、语义保证等）。
- 概念 (Concept): 例如，“迭代器”是一个概念，“可排序 (Sortable)”是一个概念，“容器”是一个概念。
- 改进 (Refinement): 一个概念可以是另一个概念的改进。例如，“前向迭代器”是“输入迭代器”的改进，因为它增加了可以多次读取的要求。“双向迭代器”是“前向迭代器”的改进，增加了向后移动的要求。
- 模型 (Model): 一个具体的类型如果满足了某个概念的所有要求，就称为该概念的一个**模型 (Model)**。例如，
std::vector<int>::iterator是“随机访问迭代器”概念的一个模型。int类型是“可相加 (Additive)”概念的一个模型。
虽然 C++ 标准本身直到 C++20 才正式引入语言级别的 Concepts 支持，但 STL 从一开始就是基于这种思想设计的。算法的文档通常会说明它对模板参数（特别是迭代器类型）的概念要求。例如，std::sort 要求其迭代器参数是“随机访问迭代器 (RandomAccessIterator)”的模型，并且元素类型是“可小于比较 (LessThanComparable)”和“可移动构造/赋值 (MoveConstructible/MoveAssignable)”的模型。
理解概念有助于我们知道哪些算法可以用于哪些容器或数据类型。
16.4.5 容器种类
STL 提供了多种容器类型，可以大致分为几类：
顺序容器 (Sequence Containers): 元素按照线性顺序排列。
-
std::vector: 动态数组，连续内存，随机访问快，尾部插入/删除快，中间插入/删除慢。 -
std::deque(Double-Ended Queue): 双端队列，非连续内存（分块），支持随机访问，头部和尾部插入/删除都快，中间插入/删除慢。 -
std::list: 双向链表，非连续内存，不支持随机访问（访问元素需遍历），任何位置插入/删除都快 (O(1))。 -
std::forward_list(C++11): 单向链表，比list开销更小，只支持向前遍历，任何位置插入/删除快。 -
std::array(C++11): 固定大小数组，是对 C 风格数组的封装，连续内存，支持随机访问，大小在编译时确定，不能动态改变。
-
关联容器 (Associative Containers): 元素根据键 (Key) 进行排序和存储，查找速度通常较快 (对数时间复杂度 O(log N))。
-
std::set: 存储唯一元素的集合，自动排序。 -
std::map: 存储**键-值对 (Key-Value Pair)**，键是唯一的，根据键自动排序。 -
std::multiset: 类似于set，但允许存储重复元素。 -
std::multimap: 类似于map，但允许存储具有相同键的多个键-值对。
-
无序关联容器 (Unordered Associative Containers) (C++11): 元素根据键的哈希值 (Hash Value) 存储在桶 (Bucket) 中，不保证元素顺序。插入、删除和查找的平均时间复杂度通常为常数时间 O(1)，但最坏情况下可能退化为线性时间 O(N)。
-
std::unordered_set: 存储唯一元素的哈希集合。 -
std::unordered_map: 存储键-值对的哈希映射，键唯一。 -
std::unordered_multiset: 允许重复元素的哈希集合。 -
std::unordered_multimap: 允许重复键的哈希映射。
-
容器适配器 (Container Adapters): 基于其他容器类型实现特定接口（通常限制了底层容器的功能）。
-
std::stack: 后进先出 (LIFO) 栈，默认基于deque实现。 -
std::queue: 先进先出 (FIFO) 队列，默认基于deque实现。 -
std::priority_queue: 优先级队列，最大（或最小）元素总是在顶部，默认基于vector实现。
-
选择哪种容器取决于具体需求，如是否需要排序、是否需要快速随机访问、插入/删除的频率和位置、是否允许重复元素等。
16.4.6 关联容器
关联容器的核心特点是元素根据键自动排序。它们通常使用某种形式的平衡二叉搜索树（如红黑树）来实现，保证了插入、删除和查找操作的时间复杂度为 O(log N)。
std::set<Key>:存储类型为
Key的唯一元素。元素自动按升序排序（默认使用
operator<）。主要用于快速检查元素是否存在。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main() {
std::set<std::string> unique_words;
unique_words.insert("apple");
unique_words.insert("banana");
unique_words.insert("apple"); // 重复插入会被忽略
std::cout << "Set contains: ";
for (const auto& word : unique_words) {
std::cout << word << " "; // 输出: apple banana (已排序)
}
std::cout << std::endl;
if (unique_words.count("banana")) { // count() 返回 0 或 1
std::cout << "banana is in the set.\n";
}
auto it = unique_words.find("cherry"); // find() 返回迭代器
if (it == unique_words.end()) {
std::cout << "cherry is not in the set.\n";
}
}
std::map<Key, Value>:存储
std::pair<const Key, Value>类型的键-值对。键
Key必须是唯一的。元素根据键自动排序。
可以通过键快速查找对应的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int main() {
std::map<std::string, int> word_counts;
// 插入方式
word_counts.insert({"apple", 3});
word_counts.insert(std::make_pair("banana", 5));
word_counts["cherry"] = 2; // 使用 operator[] 插入或更新
word_counts["apple"] = 4; // 更新 apple 的值
std::cout << "Map contains:\n";
for (const auto& pair : word_counts) {
// pair.first 是 const Key, pair.second 是 Value
std::cout << pair.first << ": " << pair.second << std::endl;
// 输出按键排序: apple: 4, banana: 5, cherry: 2
}
std::cout << "Count for banana: " << word_counts["banana"] << std::endl; // 使用 [] 访问
auto it = word_counts.find("grape");
if (it == word_counts.end()) {
std::cout << "grape not found.\n";
}
// 注意：如果使用 operator[] 访问不存在的键，会自动插入一个具有默认值的元素！
std::cout << "Count for grape (after []): " << word_counts["grape"] << std::endl; // 输出 0，并插入了 {"grape", 0}
}
std::multiset<Key>: 允许存储重复的键，元素自动排序。std::multimap<Key, Value>: 允许存储重复的键，键值对根据键自动排序。查找会返回一个范围（所有具有该键的元素）。
16.4.7 无序关联容器（C++11）
无序关联容器使用哈希表 (Hash Table) 实现，元素不保证任何特定顺序。它们通过计算键的哈希值来确定元素存储的位置（桶）。
优点: 插入、删除和查找的平均时间复杂度为 O(1)，通常比关联容器更快。
缺点:
- 最坏情况下的时间复杂度为 O(N)（当发生大量哈希冲突时）。
- 元素是无序的。
- 需要为键类型提供哈希函数和相等比较操作（标准库为基本类型和
string等提供了默认实现）。 - 哈希表操作可能会导致迭代器失效。
std::unordered_set<Key>: 存储唯一键的哈希集合。std::unordered_map<Key, Value>: 存储唯一键值对的哈希映射。std::unordered_multiset<Key>: 允许重复键的哈希集合。std::unordered_multimap<Key, Value>: 允许重复键的哈希映射。
示例 (unordered_map):
1 |
|
无序容器在不需要元素排序且注重平均查找性能的场景下非常有用，例如实现缓存、快速查找表等。
16.5 函数对象
在 STL 中，许多算法（如 sort, find_if, for_each）不仅可以通过迭代器指定操作的范围，还可以接受一个额外的参数来定制其行为。这个参数通常是一个可调用 (Callable) 的实体，用于指定比较规则、判断条件或要执行的操作。
除了普通的函数指针，C++ 还提供了一种强大的可调用实体：**函数对象 (Function Object)**，也称为 **函数符 (Functor)**。
16.5.1 函数符概念
函数对象（或函数符）是一个重载了函数调用运算符 operator() 的类的对象。这意味着你可以像调用函数一样使用这个对象。
基本结构:
1 |
|
为什么使用函数对象？
携带状态: 与普通函数不同，函数对象是对象，它可以拥有自己的成员变量（状态）。这些状态可以在多次调用之间保持，或者在创建时进行配置。这对于需要累加、计数或根据特定上下文操作的算法非常有用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 函数对象，用于计算总和并记录调用次数
class SumAndCount {
private:
int sum;
int count;
public:
SumAndCount() : sum(0), count(0) {} // 初始化状态
void operator()(int x) {
sum += x;
count++;
}
int getSum() const { return sum; }
int getCount() const { return count; }
};
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5};
SumAndCount sac; // 创建带有状态的函数对象
// 将函数对象传递给 for_each 算法
// for_each 会对 nums 中的每个元素调用 sac.operator()
// 注意：for_each 返回其函数对象参数的副本。
// 如果需要获取最终状态，需要接收返回值（或使用引用包装器）
sac = std::for_each(nums.begin(), nums.end(), sac);
std::cout << "Sum: " << sac.getSum() << std::endl; // 输出 15
std::cout << "Count: " << sac.getCount() << std::endl; // 输出 5
return 0;
}内联可能性: 编译器通常更容易对函数对象的
operator()进行内联 (inline) 优化，因为它在编译时是已知的。相比之下，通过函数指针调用函数通常会阻止内联，可能带来轻微的性能开销。类型多样性: 每个函数对象类都是一个独立的类型。这允许我们通过模板特化或重载来为不同的函数对象提供不同的行为。
16.5.2 预定义的函数符
标准库在 <functional> 头文件中提供了一系列常用的预定义函数符，可以直接使用，省去了自己编写简单操作类的麻烦。
常见的预定义函数符包括：
- 算术类:
-
plus<T>: 执行arg1 + arg2。 -
minus<T>: 执行arg1 - arg2。 -
multiplies<T>: 执行arg1 * arg2。 -
divides<T>: 执行arg1 / arg2。 -
modulus<T>: 执行arg1 % arg2。 -
negate<T>: 执行-arg。
-
- 比较类:
-
equal_to<T>: 执行arg1 == arg2。 -
not_equal_to<T>: 执行arg1 != arg2。 -
less<T>: 执行arg1 < arg2(默认排序规则)。 -
greater<T>: 执行arg1 > arg2。 -
less_equal<T>: 执行arg1 <= arg2。 -
greater_equal<T>: 执行arg1 >= arg2。
-
- 逻辑类:
-
logical_and<T>: 执行arg1 && arg2。 -
logical_or<T>: 执行arg1 || arg2。 -
logical_not<T>: 执行!arg。
-
使用示例:
这些预定义函数符常用于需要自定义比较或操作的 STL 算法。
1 |
|
16.5.3 自适应函数符和函数适配器 (旧概念)
在 C++11 引入 lambda 表达式之前，为了更灵活地组合和使用函数符，STL 提供了一些更复杂的机制，如自适应函数符 (Adaptable Functors) 和**函数适配器 (Function Adapters)**。
- 自适应函数符: 除了
operator()，还提供了一些嵌套的typedef（如result_type,first_argument_type,second_argument_type），使得适配器能够了解函数符的参数和返回类型。预定义的函数符大多是自适应的。 - 函数适配器: 用于修改或绑定函数符的参数。
- 绑定器 (Binders): 如
bind1st和bind2nd(在 C++11 中废弃，C++17 中移除)，用于将二元函数符的一个参数绑定到特定值，生成一个一元函数符。例如，bind1st(less<int>(), 5)会创建一个判断参数是否小于 5 的一元函数符。 - 求反器 (Negators): 如
not1和not2(在 C++17 中废弃)，用于对一元或二元谓词函数符的结果取反。例如，not1(is_even)会创建一个判断是否为奇数的一元函数符。 - 成员函数适配器: 如
mem_fun和mem_fun_ref(在 C++11 中废弃，C++17 中移除)，用于将成员函数包装成可以被 STL 算法使用的函数对象。
- 绑定器 (Binders): 如
现代 C++ 的替代方案:
这些旧的适配器机制比较复杂且用法受限。在现代 C++ (C++11 及以后) 中，它们的功能很大程度上被以下特性取代：
-
std::bind(来自<functional>): 一个更通用、更强大的绑定器，可以绑定普通函数、成员函数、函数对象，并灵活地指定参数占位符 (std::placeholders::_1,_2等)。 - Lambda 表达式: 提供了非常简洁和灵活的方式来就地定义匿名函数对象，可以捕获上下文变量，极大地简化了需要传递自定义逻辑给算法的场景。
1 |
|
虽然旧的适配器已被废弃，但理解函数对象的基本概念仍然很重要，因为它们是 STL 设计的基础，并且 lambda 表达式本质上就是编译器为我们自动生成的匿名函数对象。
16.6 算法
STL 的第三个主要组件是**算法 (Algorithms)**。STL 提供了大量用于处理容器（或其他序列）中数据的模板函数，这些函数统称为算法。它们定义在 <algorithm> 头文件中（还有一些数值算法在 <numeric> 中）。
STL 算法是泛型的，它们通过迭代器作用于元素范围，而不依赖于特定容器的实现。这使得同一个算法可以应用于 vector, list, deque, C 风格数组等多种数据结构。
16.6.1 算法组
STL 算法可以根据其功能大致分为几类：
- 非修改序列操作 (Non-modifying sequence operations): 这些算法检查序列中的元素，但不修改元素的值。它们通常返回一个迭代器、一个布尔值或一个计数值。
- 例如:
find,find_if,count,count_if,equal,search,for_each。
- 例如:
- 修改序列操作 (Modifying sequence operations): 这些算法会修改序列中的元素值或元素顺序。
- 例如:
copy,copy_if,move,transform,replace,replace_if,fill,generate,remove,remove_if,unique,reverse,rotate,random_shuffle(C++17 废弃),shuffle(C++11)。
- 例如:
- 排序和相关操作 (Sorting and related operations): 用于对序列进行排序或执行基于排序的操作。
- 例如:
sort,stable_sort,partial_sort,nth_element,binary_search,lower_bound,upper_bound,equal_range,merge,inplace_merge。
- 例如:
- 数值操作 (Numeric operations): 定义在
<numeric>头文件中，用于执行数值计算。- 例如:
accumulate,inner_product,partial_sum,adjacent_difference,iota(C++11)。
- 例如:
- 堆操作 (Heap operations): 用于将范围维护成堆结构。
- 例如:
make_heap,push_heap,pop_heap,sort_heap。
- 例如:
- 最小/最大操作 (Min/max operations):
- 例如:
min,max,minmax(C++11),min_element,max_element,minmax_element(C++11)。
- 例如:
- 排列操作 (Permutation operations):
- 例如:
next_permutation,prev_permutation。
- 例如:
16.6.2 算法的通用特征
- 基于迭代器: 算法通常接受一对迭代器
first和last作为参数，指定要操作的左闭右开区间[first, last)**。last指向的是要处理的最后一个元素的下一个**位置。 - 不检查边界: 大多数算法假定传入的迭代器范围是有效的。传递无效范围（如
end()在begin()之前，或迭代器指向不同容器）会导致未定义行为。 - 不改变容器大小 (通常): 修改序列的算法（如
replace,remove）通常只覆盖或移动元素，而不改变容器的大小。例如，remove只是将不被移除的元素移动到序列的前部，并返回一个指向新的逻辑末尾的迭代器，它不会真正删除容器中的元素。通常需要配合容器的erase方法来实际删除元素。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int main() {
std::vector<int> v = {1, 2, 3, 2, 4, 2, 5};
int val_to_remove = 2;
// 使用 remove 将所有不等于 2 的元素移到前面
auto new_end = std::remove(v.begin(), v.end(), val_to_remove);
// v 现在可能是 {1, 3, 4, 5, ?, ?, ?} (问号代表未定义的值)
// new_end 指向第一个问号的位置 (逻辑上的新末尾)
std::cout << "Vector after remove (before erase): ";
for(int x : v) std::cout << x << " "; // 输出可能包含未定义值
std::cout << "\nSize before erase: " << v.size() << std::endl; // size 仍然是 7
// 使用 erase 删除从 new_end 到原始末尾的元素
v.erase(new_end, v.end());
std::cout << "Vector after erase: ";
for(int x : v) std::cout << x << " "; // 输出: 1 3 4 5
std::cout << "\nSize after erase: " << v.size() << std::endl; // size 变为 4
return 0;
} - 接受函数对象/Lambda: 许多算法接受一个额外的参数（通常是最后一个参数），用于指定自定义的比较逻辑（如
sort的比较函数）、判断条件（如find_if,count_if的谓词）或要执行的操作（如for_each,transform的函数）。这可以是函数指针、函数对象或 lambda 表达式。 - 谓词 (Predicate): 接受一个或两个参数并返回
bool值的可调用实体。- 一元谓词:
bool pred(const Type& a)，用于find_if,count_if,remove_if等。 - 二元谓词:
bool pred(const Type& a, const Type& b)，用于sort,unique等，通常表示某种顺序关系（如“小于”）。
- 一元谓词:
示例 (使用算法和 Lambda):
1 |
|
16.6.3 STL 和 string 类
std::string 类虽然不是 STL 容器（它没有 value_type 等嵌套类型定义），但它提供了与 STL 兼容的接口，特别是迭代器 (begin(), end() 等）。因此，许多 STL 算法可以直接应用于 std::string 对象。
1 |
|
虽然 string 类本身也提供了许多成员函数（如 find, replace），但使用 STL 算法有时可以提供更通用或更强大的功能（例如配合 lambda 使用复杂条件）。
16.6.4 函数和容器方法
有时，容器本身提供了与某个 STL 算法功能相似的成员函数。例如：
-
list有自己的sort()成员函数。 -
list有自己的remove()和remove_if()成员函数。 -
list有自己的unique()成员函数。 -
set,map等关联容器有find()成员函数。
何时使用成员函数 vs. STL 算法？
- 优先使用成员函数 (如果可用且满足需求): 容器的成员函数通常能更好地利用容器的内部结构进行优化。
- 例如，
list::sort()比std::sort(list.begin(), list.end())(如果list迭代器支持的话，但它不支持随机访问，所以不能用std::sort) 更高效，因为它只需要重新链接节点，而不需要移动元素。 -
list::remove()可以真正地从链表中删除节点并调整大小，而std::remove不能。 - 关联容器的
find()成员函数利用其内部树或哈希结构，复杂度为 O(log N) 或 O(1)，而std::find是线性扫描 O(N)。
- 例如，
- 使用 STL 算法:
- 当容器没有提供相应的成员函数时。
- 当需要跨不同容器类型使用统一的算法时。
- 当需要更复杂的、成员函数不支持的操作逻辑时（例如，使用
std::remove_copy_if将不满足条件的元素复制到另一个容器）。
16.6.5 使用 STL
掌握 STL 的关键在于理解其三个核心组件如何协同工作：
- 选择合适的容器: 根据数据存储和访问的需求选择
vector,list,map,set等。 - 使用迭代器指定范围: 通过
begin(),end()或其他方式获取迭代器来定义算法操作的元素区间[first, last)。 - 选择合适的算法: 从
<algorithm>或<numeric>中选择能完成所需任务的算法。 - 提供自定义逻辑 (如果需要): 通过函数对象、lambda 表达式或函数指针向算法传递自定义的比较、判断或操作规则。
STL 是一个强大而灵活的库，熟练使用它可以大大提高 C++ 编程的效率和代码质量。建议多查阅文档（如 cppreference.com）了解各种容器、算法和迭代器的详细用法和要求。
16.7 其他库
除了 string 类、智能指针和 STL 的核心组件（容器、算法、迭代器）之外，C++ 标准库还提供了许多其他有用的工具和类。本节将简要介绍 valarray 类和 C++11 引入的 initializer_list。
16.7.1 vector、valarray 和 array
我们在前面章节已经接触过 vector 和 array，它们都提供了类似数组的功能，但各有特点。标准库还在 <valarray> 头文件中提供了另一个模板类 std::valarray，它主要设计用于数值计算，特别是对整个数组进行高效的元素级算术运算。
std::vector<T>:- 头文件:
<vector> - 大小: 动态大小，可运行时增长和收缩。
- 内存: 保证元素连续存储。
- 主要特点: 通用的动态数组，支持丰富的 STL 算法，尾部插入/删除高效。
- 数值运算: 不直接支持元素级的算术运算符（例如，两个
vector不能直接相加）。需要手动循环或使用std::transform等算法。
- 头文件:
std::array<T, N>(C++11):- 头文件:
<array> - 大小: 固定大小
N，在编译时确定。 - 内存: 保证元素连续存储，通常在栈上分配（如果是局部变量且大小适中）。
- 主要特点: 对 C 风格数组的类型安全封装，支持 STL 算法，性能与 C 风格数组相当。
- 数值运算: 与
vector类似，不直接支持元素级运算。
- 头文件:
std::valarray<T>:- 头文件:
<valarray> - 大小: 动态大小（但通常在创建后大小变化不频繁）。
- 内存: 不保证连续存储（实现可能进行优化，如分块）。
- 主要特点: 专为数值计算设计。重载了算术运算符 (
+,-,*,/等）以支持元素级 (element-wise) 操作。还提供了许多数学函数（如abs,sqrt,sin,cos等）的应用版本。 - STL 兼容性: 与标准 STL 算法的兼容性不如
vector和array好（例如，其迭代器可能不是标准类别）。
- 头文件:
比较总结:
| 特性 | std::vector<T> |
std::array<T, N> (C++11) |
std::valarray<T> |
|---|---|---|---|
| 头文件 | <vector> |
<array> |
<valarray> |
| 大小 | 动态 | 固定 (编译时) | 动态 |
| 内存 | 连续 | 连续 | 不保证连续 |
| 主要用途 | 通用动态数组 | C 数组的安全替代品 | 数值计算 |
| 元素级运算 | 否 | 否 | 是 |
| STL 算法 | 完全兼容 | 完全兼容 | 有限兼容 |
valarray 示例:
1 |
|
如果你的主要任务是进行向量化或矩阵式的数值计算，valarray 可能是一个值得考虑的选择，尽管在现代 C++ 中，也有许多第三方库（如 Eigen, Blaze）提供了更强大和灵活的线性代数功能。对于通用的动态序列存储，vector 仍然是首选。
16.7.2 模板 initializer_list（C++11）
C++11 引入了一个新的模板类 std::initializer_list<T>，定义在 <initializer_list> 头文件中。它是一个轻量级的代理对象，代表了一个用花括号 {} 初始化的值列表，其中所有值的类型都是 T 或可以隐式转换为 T。
主要目的: 使得函数（尤其是构造函数）能够接受任意数量的、类型相同的初始化值，就像内置数组或聚合类型那样使用花括号初始化一样。
特点:
- 轻量级:
initializer_list对象本身通常只包含指向底层（临时）数组的指针和数组的大小。复制initializer_list对象是浅拷贝，开销很小。 - 只读访问: 通过
initializer_list访问其元素通常是只读的 (const T&)。你不能通过initializer_list修改列表中的元素。 - 生命周期:
initializer_list引用的底层数组的生命周期与initializer_list对象本身相关联，通常是临时的。不要存储initializer_list对象并在其原始上下文之外使用。 - 迭代器: 提供了
begin()和end()成员函数，返回指向底层数组的const T*指针，可以方便地遍历列表中的元素。 -
size(): 返回列表中的元素数量。
如何工作: 当编译器遇到一个需要 std::initializer_list<T> 参数的地方，并且你提供了一个 {value1, value2, ...} 形式的初始化列表时，编译器会自动：
- 创建一个临时的、类型为
const T的数组，并将列表中的值存储进去。 - 创建一个
std::initializer_list<T>对象，使其内部指针指向这个临时数组的开头，并记录数组的大小。 - 将这个
initializer_list<T>对象传递给函数或构造函数。
16.7.3 使用 initializer_list
initializer_list 最常见的用途是作为函数或构造函数的参数类型。
1. 作为函数参数:
1 |
|
2. 作为构造函数参数:
这是 initializer_list 最重要的用途之一，它使得 STL 容器（如 vector, list, map, set 等）以及用户自定义的类能够支持简洁的花括号列表初始化。
1 |
|
initializer_list 极大地增强了 C++11 及以后版本的初始化语法，使其更加统一和方便，特别是对于容器和需要接受可变数量同类型参数的场景。
16.8 总结
本章深入探讨了 C++ 标准库提供的几个强大的工具，它们极大地增强了 C++ 的功能和易用性，特别是 string 类、智能指针和标准模板库 (STL)。
主要内容回顾：
string类:- 提供了比 C 风格字符数组更安全、更方便的字符串处理方式，具有自动内存管理和丰富的成员函数（构造、输入、拼接、查找、修改、比较等）。
- 支持通过
c_str()获取与 C 风格函数兼容的const char*。 - 标准库还提供了宽字符版本如
wstring。
智能指针 (
<memory>):- 用于自动管理动态分配的内存，防止内存泄漏和悬挂指针。
-
unique_ptr: 实现独占所有权，轻量级，不可复制，可移动。管理动态数组时使用unique_ptr<T[]>。是管理动态资源的首选。 -
shared_ptr: 实现共享所有权，通过引用计数管理资源生命周期。当最后一个shared_ptr销毁时释放资源。需要注意循环引用问题。 -
weak_ptr: 非拥有型指针，用于观察shared_ptr管理的对象，不增加引用计数，可用于打破循环引用。通过lock()安全地获取shared_ptr。 - 应优先使用
make_unique和make_shared创建智能指针。 -
auto_ptr已被废弃，应使用unique_ptr。
标准模板库 (STL):
- 基于泛型编程思想，提供通用的容器、算法和迭代器。
- 容器: 存储数据的模板类。
- 顺序容器:
vector(动态数组),deque(双端队列),list(双向链表),forward_list(单向链表),array(固定大小数组)。 - 关联容器:
set,map,multiset,multimap(基于键排序，对数时间复杂度)。 - 无序关联容器:
unordered_set,unordered_map,unordered_multiset,unordered_multimap(基于哈希，平均常数时间复杂度)。 - 容器适配器:
stack,queue,priority_queue(提供特定接口)。
- 顺序容器:
-
vector: 最常用的动态数组，支持随机访问，尾部操作高效。 - 迭代器: 泛化的指针，连接容器和算法，提供统一的遍历接口。分为输入、输出、前向、双向、随机访问五种类别。
- 算法 (
<algorithm>,<numeric>): 对迭代器指定的范围进行操作的函数模板（如sort,find,copy,transform,accumulate）。算法通常不改变容器大小，需要配合容器方法（如erase）来实际增删元素。 - 基于范围的 for 循环 (C++11): 提供了简洁、安全的遍历容器（或序列）的方式。
函数对象 (Functors):
- 重载了
operator()的类的对象，可以像函数一样调用。 - 可以携带状态，常作为参数传递给 STL 算法以定制行为。
- 标准库在
<functional>中提供了预定义的函数符（如plus,less）。 - 现代 C++ 中，Lambda 表达式和
std::bind提供了比旧式函数适配器更灵活的方式。
- 重载了
其他库特性:
-
valarray(<valarray>): 专为数值计算设计的动态数组，支持元素级算术运算。 -
initializer_list(<initializer_list>, C++11): 使得函数和构造函数能接受花括号初始化列表{...}，简化了容器和自定义类的初始化。
-
本章介绍的库特性是现代 C++ 编程的基础。熟练运用 string、智能指针和 STL 的容器、迭代器、算法，可以编写出更安全、更简洁、更高效、更易于维护的代码。
