數據結構是一個容器，用于將一些數據組織到單個對象中。我們已經見過了幾個數據結構，比如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函數，使它以城市對象為第二個參數。