捷 C++ 课程学习笔记：STL 应用与复杂度分析

一、STL 六大组件

STL（Standard Template Library）是 C++ 标准库的重要组成部分，提供了通用的模板类和函数，用于实现常用的数据结构和算法。STL 主要包括以下六大组件：

1. 容器（Containers）：

   • 用于存储数据的结构，如 vector、list、map 等。
   • 容器可以分为序列容器（如 vector、list）和关联容器（如 map、set）。

2. 分配器（Allocators）：

   • 用于管理内存分配和释放，如 allocator。
   • 分配器可以与容器配合使用，提供灵活的内存管理。

3. 算法（Algorithms）：

   • 提供各种操作，如排序、搜索、遍历等，如 sort、find、count 等。
   • 算法通常与迭代器和容器配合使用。

4. 迭代器（Iterators）：

   • 用于遍历容器中的元素，如 begin() 和 end()。
   • 迭代器可以分为输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器。

5. 适配器（Adapters）：

   • 用于扩展容器和迭代器的功能，如 vector 的 push_back 和 pop_back。
   • 适配器可以将一种容器或迭代器转换为另一种形式。

6. 仿函式（Functors）：

   • 用于实现函数对象，如 less、greater 等。
   • 仿函式可以与算法配合使用，提供灵活的操作。

二、STL 六大组件关系

STL 的六大组件之间相互配合，形成了一个强大的工具集。以下是一个具体的例子，展示了这些组件的使用：

#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>using namespace std;int main() {int ia[] = {27, 210, 12, 47, 109, 83};vector<int, allocator<int>> vi(ia, ia + 6);cout << count_if(vi.begin(), vi.end(), not1(bind2nd(less<int>(), 40))) << endl;return 0;
}

• 容器（Containers）：vector<int, allocator<int>> vi 用于存储整数数组 ia。
• 分配器（Allocators）：allocator<int> 用于管理内存分配。
• 算法（Algorithms）：count_if 用于统计满足条件的元素数量。
• 迭代器（Iterators）：vi.begin() 和 vi.end() 用于遍历容器中的元素。
• 适配器（Adapters）：not1 和 bind2nd 用于调整函数对象的行为。
• 仿函式（Functors）：less<int> 用于比较两个整数的大小。

三、复杂度分析

在使用 STL 时，了解算法和操作的复杂度是非常重要的。常见的复杂度表示法（Big-oh）包括：

1. O(1) 或 O©：常数时间（constant time）。

   • 示例：访问数组中的元素。

2. O(n)：线性时间（linear time）。

   • 示例：遍历一个数组或链表。

3. O(log₂n)：次线性时间（sub-linear time）。

   • 示例：二分查找。

4. O(n²)：平方时间（quadratic time）。

   • 示例：冒泡排序。

5. O(n³)：立方时间（cubic time）。

   • 示例：三重循环。

6. O(2ⁿ)：指数时间（exponential time）。

   • 示例：递归计算斐波那契数列。

7. O(n log₂n)：介于线性及二次方增长的中间行为模式。

   • 示例：快速排序、归并排序。

四、迭代器的使用

迭代器是 STL 中的重要组件，用于遍历容器中的元素。迭代器的使用需要注意“前闭后开”区间，即 [begin, end)。

Container<T> c;
...
Container<T>::iterator ite = c.begin();
for (; ite != c.end(); ++ite) {...
}

• begin()：返回容器的第一个元素的迭代器。
• end()：返回容器的最后一个元素的下一个位置的迭代器。

五、范围 for 循环

C++11 引入了范围 for 循环（range-based for loop），简化了遍历容器的代码。

for (int i : {2, 3, 5, 7, 9, 13, 17, 19}) {std::cout << i << std::endl;
}std::vector<double> vec;
...
for (auto elem : vec) {std::cout << elem << std::endl;
}for (auto& elem : vec) {elem *= 3;
}

• auto：自动推导类型，简化代码编写。
• auto&：引用类型，用于修改容器中的元素。

六、auto 关键字

C++11 引入了 auto 关键字，用于自动推导类型，简化代码编写。

list<string> c;
...
list<string>::iterator ite;
ite = ::find(c.begin(), c.end(), target);list<string> c;
...
auto ite = ::find(c.begin(), c.end(), target);

• auto：自动推导 find 函数返回的迭代器类型，简化代码编写。

总结

通过学习，我对 STL 的六大组件及其关系有了更深入的理解。老师帮助我掌握 STL 的核心概念和应用技巧。特别是对复杂度分析、迭代器的使用和范围 for 循环的介绍，为后续的面向对象编程和高级开发打下了坚实的基础。

在实际编程中，合理使用 STL 可以显著提高代码的可读性和可维护性。同时，理解算法的复杂度，有助于选择合适的算法和数据结构，提高程序的性能。

在未来的学习和工作中，我将继续深入探索 STL 的高级特性，并将其应用到实际项目中，以提升自己的编程能力。