055-C++之STL容器算法迭代器的设计理念及常用算法
本帖最后由 moc 于 2018-9-22 23:05 编辑1、STL容器算法迭代器的设计理念
STL实现了数据类型与容器的分离：采用模板技术；
算法和容器的分离：迭代器（指针）， 回调函数（函数指针）。
迭代器：保存了与容器相关的指针并重载了*等操作的封装好的接口。
迭代器的作用就是提供一个遍历容器内部所有元素的接口，因此迭代器的内部必须保存一个与容器相关联的指针，然后重载各种运算操作来方便遍历，其中最重要的就是 * 运算符和 -> 运算符，以及++，--等可能需要的运算符重载。这和C++标准库中的智能指针(smart pointer)很像，智能指针也是将一个指针封装。
① STL的容器通过类模板技术，实现数据类型和容器模型的分离。
② STL的迭代器技术实现了遍历容器的统一方法；也为STL的算法提供了统一性。
③ STL的函数对象实现了自定义数据类型的算法运算
核心思想：其实函数对象本质就是回调函数，回调函数的思想，就是任务的编写者和任务的调用者有效解耦合，函数指针做函数参数。
④ 具体例子：transform算法的输入，通过迭代器first和last指向的元算作为输入；通过result作为输出；通过函数对象来做自定义数据类型的运算。
2、STL常用算法
STL中算法大致分为四类：
① 非可变序列算法：指不直接修改其所操作的容器内容的算法。
② 可变序列算法：指可以修改它们所操作的容器内容的算法。
③ 排序算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
④ 数值算法：对容器内容进行数值计算。
1. 常用查找算法:
adjacent_find(); binary_search(); count(); count_if(); equal_range(); find(); find_if()等。
2. 常用排序算法：
merge(); sort(); random_shuffle(); reverse()等。
3. 常用拷贝和替换算法：
copy(); replace(); replace_if(); swap()等。
4. 常用的算术和生成算法：
accumulate(); fill()等。
5. 常用的集合算法：
set_union(); set_intersection(); set_difference()等。
6. 常用的遍历算法：
for_each(); transform()等。
页:
[1]