Chapter 11. Generic Algorithms

第十一章 泛型算法

CONTENTS

The library containers define a surprisingly small set of operations. Rather than adding lots of functionality to the containers, the library instead provides a set of algorithms, most of which are independent of any particular container type. These algorithms are "generic:" They operate on different types of containers and on elements of various types.

标准库容器定义的操作非常少。标准库没有给容器添加大量的功能函数，而是选择提供一组算法，这些算法大都不依赖特定的容器类型，是“泛型”的，可作用在不同类型的容器和不同类型的元素上。

The generic algorithms, and a more detailed look at iterators, form the subject matter of this chapter.

泛型算法以及对迭代器更详尽的描述，组成了本章的主题。

The standard containers define few operations. For the most part they allow us to add and remove elements; to access the first or last element; to obtain and in some cases reset the size of the container; and to obtain iterators to the first and one past the last element.

标准容器（the standard container）定义了很少的操作。大部分容器都支持添加和删除元素；访问第一个和最后一个元素；获取容器的大小，并在某些情况下重设容器的大小；以及获取指向第一个元素和最后一个元素的下一位位置的迭代器。

We can imagine many other useful operations one might want to do on the elements of a container. We might want to sort a sequential container, or find a particular element, or find the largest or smallest element, and so on. Rather than define each of these operations as members of each container type, the standard library defines a set of generic algorithms: "algorithms" because they implement common operations; and "generic" because they operate across multiple container typesnot only library types such as vector or list, but also the built-in array type, and, as we shall see, over other kinds of sequences as well. The algorithms also can be used on container types we might define ourselves, as long as our types conform to the standard library conventions.

可以想像，用户可能还希望对容器元素进行更多其他有用的操作：也许需要给顺序容器排序，或者查找某个特定的元素，或者查找最大或最小的元素，等等。标准库并没有为每种容器类型都定义实现这些操作的成员函数，而是定义了一组泛型算法：因为它们实现共同的操作，所以称之为“算法”；而“泛型”指的是它们可以操作在多种容器类型上——不但可作用于 vector 或 list 这些标准库类型，还可用在内置数组类型、甚至其他类型的序列上，这些我们将在本章的后续内容中了解。自定义的容器类型只要与标准库兼容，同样可以使用这些泛型算法。

Most of the algorithms operate by traversing a range of elements bounded by two iterators. Typically, as the algorithm traverses the elements in the range, it operates on each element. The algorithms obtain access to the elements through the iterators that denote the range of elements to traverse.

大多数算法是通过遍历由两个迭代器标记的一段元素来实现其功能。典型情况下，算法在遍历一段元素范围时，操纵其中的每一个元素。算法通过迭代器访问元素，这些迭代器标记了要遍历的元素范围。