数据结构是一个容器，用于将一些数据组织到单个对象中。我们已经见过了几个数据结构，比如apstring是一些字符组成，而apvector是一组相同类型（可以是任意数据类型）的元素组成。 有序集是由一些项组成的集合，它有两个决定性的属性： **有序性**：集合中的元素都有一个相应的索引。我们可以通过这些索引确定集合中的元素。 **唯一性**：集合中每个元素只能出现一次。向集合中添加一个已经存在的元素是没有效果的。 此外，我们实现的有序集还有下面一个属性： **大小任意**：随着我们向集合中添加元素，它会扩充以容纳新元素。apstring和apvector都是有序的；每个元素都有一个索引，我们可以通过索引来确定元素。但是我们见到的数据结构都不具有唯一性和大小任意这两个属性。 要满足唯一性，我们编写的add函数必须先查找以确定集合中是否存在要添加的元素。集合随着添加元素扩张这一特点可以利用apvector的resize函数实现。 下面是Set类定义的开始部分： ~~~ class Set { private: apvector<apstring> elements; int numElements; public: Set (int n); int getNumElements () const; apstring getElement (int i) const; int find (const apstring& s) const; int add (const apstring& s); }; Set::Set (int n) { apvector<apstring> temp (n); elements = temp; numElements = 0; } ~~~ 实例变量包括字符串的向量和记录集合中有多少元素的整型数。一定要记住集合中的元素数numElement与apvector的大小不是一个东西。通常前者会小一些。 Set的构造函数接受一个参数，该参数是apvector的初始大小。元素个数初始值总是0。 getNumElements和getElement是私有实例变量的访问函数。 numElements是只读变量，所以我们只提供了get函数而没有提供set函数。 ~~~ int Set::getNumElements () const { return numElements; } ~~~ 为什么我们必须阻止客户程序修改getNumElements呢？ 因为这是该类型的不变式，客户程序怎么能破坏不变式呢。我们看下Set其余的成员函数，看你能否说服自己它们都维护了不变式。 当我们使用[]操作符访问apvector时，它会检查并确认索引值大于等于0且小于向量的长度。不过要访问集合的元素，我们需要更强的条件验证。index必须小于元素数，元素数可能是个比向量长度小的值。 ~~~ apstring Set::getElement (int i) const { if (i < numElements) { return elements[i]; } else { cout << "Set index out of range." << endl; exit (1); } } ~~~ 如果getElement得到的索引值超出了范围，它会打印错误信息（我承认，并不是最有用的信息）后退出。 find和add是比较有趣的函数。到目前为止，遍历和查找的模式还是老样子： ~~~ int Set::find (const apstring& s) const { for (int i=0; i<numElements; i++) { if (elements[i] == s) return i; } return -1; } ~~~ 现在就剩下add了。像add这样的函数的返回类型一般是void，不过在这个例子中，更有意义的可能是返回元素的索引。 ~~~ int Set::add (const apstring& s) { // 如果元素已经在集合中，返回其索引 int index = find (s); if (index != -1) return index; // 如果apvector满了，将它的大小调整为原来的2倍 if (numElements == elements.length()) { elements.resize (elements.length() * 2); } // 添加新元素并返回其索引 index = numElements; elements[index] = s; numElements++; return index; } ~~~ 这里有个技巧，numElements会以两种方式使用：其一就是表示集合中的元素数目，其二是用作下一个要添加的元素的索引。 可能要花点时间才能相信这行得通，但是考虑一下：当元素数目为0时，下一个要加入元素的索引也是0。当元素数目等于向量的长度时，这就说明向量已经满了，要加入新元素必须先通过resize分配更多的空间。 下面是一个Set对象的状态图，该对象初始包含2个元素的空间：  现在我们可以使用Set类来记录在文件中找到的城市。在main函数中我们以2为初始大小创建Set对象： ~~~ Set cities (2); ~~~ 然后在processLine函数中我们把两个城市添加到Set中，并保存返回的索引值。 ~~~ int index1 = cities.add (city1); int index2 = cities.add (city2); ~~~ 我修改了processLine函数，使它以城市对象为第二个参数。