JZTXT

算法

发布时间 2023-08-24 20:43:28作者: stu--wy
  • STL中算法 是 function template。
  • 算法看不见容器，对其一无所知，所以它所需要的一切信息都必须从itertor取得，而iterators（由容器提供）必须能够回答算法的所有提问，才能搭配该算法的所有操作。
  • 迭代器的分类：
  1. struct input_iterator_tag {};
  2. struct output_iterator_tag {};
  3. struct forward_iterator_tag {} : public input_iterator_tag {};
  4. struct bidirectional_iterator_tag {} : public forward_iterator_tag {};
  5. sturct random_access_iterator_tag {} : public bidirectional_iterator_tag {};

  • 迭代器分类对算法的影响，示例：求两个迭代器之间的距离的distance算法，如果迭代器是 random_access_iterator，实现用last - first。如果迭代器是input_iterator 实现用while(first != last) ++first; ++cnt;。标准库算法的设计，算法是主函数，通过迭代器的分类调用不同的次函数，以适应不同的容器或做特化的设计提高算法效率。标准库算法源码中有对iterator_category的暗示。
  • 仿函数 (class template)，重载了（），为算法提供服务。