清华大学田永鸿教授的程序设计实习教程

“程序设计实习（田永鸿)清华大学 ACM入门 C语言入门 北京大学《程序设计实习》课程” 在“程序设计实习”这门课程中，主要涉及的是ACM竞赛的基础知识，以及C语言的编程技巧。课程由田永鸿教授，并提供了丰富的实例和算法分析，帮助学生深入理解和应用编程概念。 课程内容涵盖了几种关键的程序设计概念和STL（Standard Template Library，标准模板库）的使用。其中，第二十讲特别关注了标准模板库的第三个部分，包括： 1. **list容器**：list是一种双向链表，支持双向迭代器。它提供了如`push_front`和`pop_front`用于在列表开头添加或移除元素，以及`sort`、`remove`/`unique`、`merge`/`splice`和`reverse`等操作。 2. **deque容器**：deque（双端队列）允许在两端进行快速插入和删除，同时提供随机访问的能力，类似于数组。 3. **函数对象（Functors）**：函数对象是重载了函数调用操作符`operator()`的类的实例，它可以像函数一样被调用。函数对象可以是内联的，从而提高执行效率，且可以拥有数据域来存储状态，提升运行质量。例如，`accumulate`函数可以接受函数对象作为参数，`greater`则是一个比较函数对象。 4. **multiset容器**：multiset类似于集合，但允许存储多个相同值的元素。元素类需要重载`<`运算符，以便进行排序。multiset提供了`Find`、`lower_bound`/`upper_bound`、`count`和`insert`等方法来操作其内部元素。 课堂问题1探讨了函数对象的特点，强调了函数对象可以拥有数据域并能够作为泛型算法的参数，而函数指针在某些情况下可能无法达到同样的效率。 课堂问题2中，给出了一个关于自定义类`A`和`multiset`的例子。错误在于类`A`没有正确实现`operator<`，这是因为在`multiset`中，元素需要可比较性以便进行排序。因此，为了将`A`对象插入到`multiset`，需要定义`bool operator<(const A& other)`以满足容器的要求。 通过这个课程，学生不仅可以学习到C语言的基本语法，还能深入了解STL容器的使用，以及如何利用函数对象和自定义类来解决更复杂的问题，这些都是ACM竞赛和实际编程中不可或缺的技能。