泛型算法

1. 算法如何工作

每个泛型算法的实现都独立于单独的容器。这些算法还是大而不全的，并且不依赖于容器存储的元素类型。为了知道算法如何工作，让我们深入了解find 操作。该操作的任务是在一个未排序的元素集合中查找特定的元素。从概念上看，find必须包含以下步骤：

1. 顺序检查每个元素。

2. 如果当前元素等于要查找的值，那么返回指向该元素的迭代器。

3. 否则，检查下一个元素，重复步骤2，直到找到这个值，或者检查完所有的元素为止。

4. 如果已经到达集合末尾，而且还未找到该值，则返回某个值，指明要查找的值在这个集合中不存在。

2. 排序算法

标准库定义了四种不同的排序算法，上面只使用了最简单的sort 算法，

使words 按字典次序排列。除了sort 之外，标准库还定义了stable_sort 算法，stable_sort保留相等元素的原始相对位置。通常，对于已排序的序列，我

们并不关心其相等元素的相对位置，毕竟，这些元素是相等的。但是，在这个应用中，我们将“相等”定义为“相同的长度”，有着相同长度的元素还能以字典

次序的不同而区分。调用stable_sort 后，对于长度相同的元素，将保留其字典顺序。

3. 类定义

最简单地说，类就是定义了一个新的类型和一个新作用域。每个类可以没有成员，也可以定义多个成员，成员可以是数据、函数或类型别名。

在类内部，声明成员函数是必需的，而定义成员函数则是可选的。在类内部定义的函数默认为 inline

在类外部定义的成员函数必须指明它们是在类的作用域中。

Sales_item::avg_price 的定义使用作用域操作符来指明这是 Sales_item类中avg_price 函数的定义。

4. 将关键字const 加在形参表之后，就可以将成员函数声明为常量：

double avg_price() const; 

const 成员不能改变其所操作的对象的数据成员。const必须同时出现在声明和定义中，若只出现在其中一处，就会出现一个编译时错误。

5. 数据抽象

数据抽象是一种依赖于接口和实现分离的编程（和设计）技术。类设计者必须关心类是如何实现的，但使用该类的程序员不必了解这些细节。

相反，使用一个类型的程序员仅需了解类型的接口，他们可以抽象地考虑该类型做什么，而不必具体地考虑该类型如何工作。

6. 封装

封装是一项低层次的元素组合起来的形成新的、高层次实体珠技术.函数是封装的一种形式,。同样地，类也是一个封装的实体.被封装的元素隐藏了它们的实现细节——可以调用一个函数但不能访问它所执行的语句。

6. 访问标号

可以在任意的访问标号出现之前定义类成员。在类的左花括号之后、第一个访问标号之前定义成员的访问级别，其值依赖于类是如何定义的。

如果类是用struct 关键字定义的，则在第一个访问标号之前的成员是公有的；如果类是用class 关键字是定义的，则这些成员是私有的。

一个访问标号可以出现的次数通常是没有限制的。每个访问标号指定了随后的成员定义的访问级别。这个指定的访问级别持续有效，直到遇到下一个访问标号或看到类定义体的右花括号为止。

7. 数据抽象和封装提供了两个重要优点：

? 避免类内部出现无意的、可能破坏对象状态的用户级错误。

? 随时间推移可以根据需求改变或缺陷（bug）报告来完美类实现，而无须改变用户级代码。

8. 类声明与类定义

一旦遇到右花括号，类的定义就结束了。并且一旦定义了类，那以我们就知道了所有的类成员，以及存储该类的对象所需的存储空间。

在一个给定的源文件中，一个类只能被定义一次。如果在多个文件中定义一个类，那么每个文件中的定义必须是完全相同的。

9. 可以声明一个类而不定义它：

 class Screen;   //declaration of the Screen class

这个声明，有时称为前向声明（forwarddeclaraton），在程序中引入了类类型的Screen。在声明之后、定义之前，类Screen 是一个不完全类型（incompetetype），即已知Screen 是一个类型，但不知道包含哪些成员。

不完全类型（incompletetype）只能以有限方式使用。不能定义该类型的对象。不完全类型只能用于定义指向该类型的指针及引用，或者用于声明（而不是定义）使用该类型作为形参类型或返回类型的函数。

在创建类的对象之前，必须完整地定义该类。必须定义类，而不只是声明类，这样，编译器就会给类的对象预定相应的存储空间。同样地，在使用引用或指针访问类的成员之前，必须已经定义类。

10. 为类的成员使用类声明

只有当类定义已经在前面出现过，数据成员才能被指定为该类类型。如果该类型是不完全类型，那么数据成员只能是指向该类类型的指针或引用。

class LinkScreen {
 Screen window;
 LinkScreen *next;
 LinkScreen *prev;
 };

因为只有当类定义体完成后才能定义类，因此类不能具有自身类型的数据成员。然而，只要类名一出现就可以认为该类已声明。因此，类的数据成员可以是指向自身类型的指针或引用：

11. 类对象

定义一个类时，也就是定义了一个类型。一旦定义了类，就可以定义该类型的对象。

定义对象时，将为其分配存储空间，但（一般而言）定义类型时不进行存储分配：

 class Sales_item {
 public:
 // operations onSales_item objects
 private:
 std::string isbn;
 unsigned units_sold;
 double revenue;
 };

定义了一个新的类型，但没有进行存储分配。

12． 定义类类型的对象

定义了一个类类型之后，可以按以下两种方式使用。

? 将类的名字直接用作类型名。

? 指定关键字class 或struct，后面跟着类的名字：

 Sales_item item1;       //default initialized object of type Sales_item
 class Sales_itemitem1;  // equivalent definition of item1

两种引用类类型方法是等价的。第二种方法是从C 继承而来的，在C++ 中仍然有效。第一种更为简练，由C++ 语言引入，使得类类型更容易使用。