C++程序设计：原理与实践（基础篇）（原书第2版）

12.1　简介

C++标准库中最有用的容器就是vector。一个vector提供一个指定类型元素的序列。可以通过索引（下标）引用元素，使用push_back（）扩展vector，使用size（）获得vector元素的数量，以及对vector元素访问进行越界检查。标准库vector是一种方便、灵活、（时空）高效、静态类型安全的元素容器。标准string具有相似的特性，其他有用的标准容器类型，如list和map，也是如此，我们将在第15章中介绍它们。但是，计算机内存并不能直接支持这些有用的类型。硬件能直接支持的只有字节序列。例如，对于一个vector<double>，操作v.push_back（2.3）将2.3添加到double类型序列中，并将元素数量v（v.size（））增加1。在最底层，计算机并不知道push_back（）这样的复杂操作的任何信息，它所知道的只是如何一次读或写若干字节。

在本章和接下来的两章中，我们将展示如何通过每个程序员都能使用的基本语言特性来构建vector。通过这些内容，我们可以阐明有用的概念和编程技术，以及如何用C++语言特性表达这些概念和技术。我们在vector的实现中遇到的语言特性和编程技术，都是有广泛用途且的确被广泛使用的。

在学习如何设计、实现和使用vector之后，我们可以继续学习其他的标准库容器（例如map），并研究C++标准库所提供的优雅、高效的特性及其使用方法（见第15和16章）。这些特性被称为算法，能将我们从涉及数据的常见编程任务中解放出来。作为替代，所有C++实现都提供了许多算法给我们使用，可大大简化我们编写和测试库的工作。我们已经见到并使用过标准库中的一个最有用的算法：sort（）。

我们通过设计一系列越来越复杂的vector实现来逐渐逼近标准库vector。首先，构建一个非常简单的vector。然后，考察vector中哪些部分不合需求并进行相应修改。这样经过几次处理之后，我们就得到了一个与你的C++编译器所提供的标准库vector（也就是在前面章节中你曾使用过的版本）大致等价的vector实现。这种逐渐完善的过程与我们完成一个新的编程任务的方式非常相似。在这个过程中，我们会遇到很多涉及内存和数据结构使用的经典问题，并对它们进行探究。我们的基本计划是： ...