Lab 10-2: 串列 (List) 的 Iterator 與 operator[]

 
實習目標 operator overloading: operator->, operator*, operator[]
friend and Iterator
static member variable
 
步驟一
上一個實習中我們製作了 Student 類別, StudentList 類別, StudentList::Node 類別, 這三個類別主要提供的功能包括將 Student 物件記錄在 StudentList 中, 將具有某一 id 的 Student 物件找到或是刪除。

還缺的功能包括

  1. 順序將記錄在 StudentList 中的 Student 物件取出來 (這個功能我們將嘗試以兩種方式來達到: a. iterator b. operator[])

  2. insert(): 在串列中某一個 Student 物件之後加入新的一個 Student 物件
步驟二
我們先來看看測試程式, 了解希望加入的功能到底需要配合什麼應用程式:
    void main()
    {
        StudentList sList;
        sList.appendEntry(new Student("Mary Chen", "111111111", 
                                      "0933111111", 
                                      "Business"));
        sList.appendEntry(new Student("John Wang", "222222222", 
                                      "0928222222", 
                                      "Computer Science"));
        sList.appendEntry(new Student("Mel Lee", "333333333", 
                                      "0968333333", 
                                      "Mechanical Engineering"));
        sList.appendEntry(new Student("Bob Tsai", "444444444", 
                                      "0930444444", 
                                      "Electrical Engineering"));
        sList.appendEntry(new Student("Ron Yang", "555555555", 
                                      "0918555555", 
                                      "Computer Science"));

        // 列印串列中所有的 Student 物件
        int i;
        Iterator iter(sList);
        for (i=0, iter.reset(); iter.hasMoreData(); iter.next(), i++)
        {
            cout << i << ":";
            iter->display(cout);
            cout << endl;
        }
        cout << endl;

        // 檢查是否串列中有兩個學生是在同一個系所的           
        Iterator iter1(sList), iter2(sList);
        for (iter1.reset(); iter1.hasMoreData(); iter1.next())
        {
            for (iter2=iter1, iter2.next(); 
                 iter2.hasMoreData(); iter2.next())
            {
                if (iter1->ofTheSameDepartment(*iter2))
                {
                    cout << "The following two students are "
                             "of the same department:\n";
                    iter1->display(cout);
                    cout << endl;
                    iter2->display(cout);
                    cout << endl;
                }
            }
        }

        // 在 id="333333333" 的學生之後再加入一個學生
        for (iter1.reset(); iter1.hasMoreData(); iter1.next())
            if (iter1->IDEquals("333333333"))
                sList.insertEntry(iter1, 
                                  new Student("Carol Chen", "333331111", 
                                              "0933333111", "Business"));
        for (i=0; i<sList.size(); i++)
            sList[i]->display(cout);
    }
步驟三
我們需要定義 Iterator 類別

這個類別依照上述的用法來看至少應該要有下列功能

    class Iterator
    {
    public:
        Iterator(StudentList &list);
        void reset();
        void next();
        Student &operator*() const;
        Student *operator->() const;
        bool hasMoreData() const;
    private:
        StudentList::Node *m_iterator;
        StudentList *m_list;
    };
這個類別和 StudentList 有很密切的關連, 所以值得用 friend 功能來實作, 它需要存取 StudentList 內的資料成員, 所以需要在 StudentList 內將 Iterator 設為其 friend

建構元 Iterator(StudentList &list) 最主要需要建構出這個 Iterator 物件和 StudentList 之間的關係, 同時將 m_iterator 清為 0

reset() 及 next() 為移動目前的指標 m_iterator 位置的基本函式

hasMoreData() 測試是不是已經移到串列最尾端

operator->() 是一個 Smart pointer, 它應該要傳回目前指標 m_iterator 所指到的 Student 物件的指標, 例如:


    Student *Iterator::operator->() const
    {
        if (m_iterator)
            return m_iterator->m_data;
        else
            return 0;
    }

operator*() 是 dereferencing operator, 它應該要傳回目前指標 m_iterator 所指到的 Student 物件的參考, 例如:


    Student &Iterator::operator*() const
    {
        if (m_iterator)
            return *(m_iterator->m_data);
        else
            return m_dummy;
    }
    
    m_dummy 是一個宣告在類別裡的 static Student 變數

    class Iterator
    {
        ...
    private:
        static Student m_dummy;
    };
    
    記得要在 iterator.cpp 中定義

    Student Iterator::m_dummy;
步驟四 定義 int StudentList::size() const; 成員函式

傳回目前 StudentList 內 Student 物件的總個數, 這個函式內可以當場去算一遍到底 List 內有幾個節點, 也可以在 StudentList 內實作一個變數來記錄目前總共有幾筆資料, 在 appendEntry() 或是 insertEntry() 時加一, deleteEntry() 時減一

步驟五 定義 Student *&StudentList::operator[](int slot); 成員函式

將 List 中第 slot 個節點所記錄的 Student 物件的指標變數的參考傳回

步驟六 定義 void StudentList::insertEntry(Iterator iter, Student *student); 成員函式

請評估是否需要定義 Iterator 類別的拷貝建構元

要將一個 Student 物件加入目前 iter 所在的節點之後, Iterator 類別需要定義界面把它所記錄的節點傳出來, 或是 StudentList 可以將這個 insertEntry 的動作交給 Iterator 類別來完成

請注意由於 Iterator 類別定義時需要先定義 StudentList 類別, 因此在 Iterator.h 裡必須先 #include "StudentList.h"。但是此步驟中加入的成員函式使得定義 StudentList 時必須知道 Iterator 類別, 否則 compiler 會發出 "不認得 Iterator" 的錯誤訊息, 此時很直覺地就會希望在 StudentList.h 中加入 #include "Iterator.h" 的敘述, 以便在定義 StudentList 類別之前先定義 Iterator 類別, 可是這樣子做解決不了問題--你發現定義 StudentList 類別時希望先定義 Iterator 類別, 然後在定義 Iterator 類別時先定義 StudentList 類別 這兩個要求是矛盾的。

解決這個問題的方法是用 forward declaration (預先宣告)

----------------- Iterator.h --------------------
#include "StudentList.h"
class Iterator
{
...
};
---------------- Iterator.cpp -------------------
#include "Iterator.h"
...
--------------- StudentList.h ------------------
class Iterator;
class StudentList
{
...
};
-------------- StudentList.cpp -----------------
#include "StudentList.h"
#include "Iterator.h"
...

請注意

  • 上面各個 include 的順序代表的意義不太一樣, 如果先 #include "Iterator.h" 再 #include "StudentList.h" 則第二個 #include 是沒有做任何事情的, 因為 Iterator.h 裡面已經有 #include "StudentList.h" 了
  • 如果你在 class StudentList 中已經有 friend class Iterator; 的敘述, 就可以省掉 前面的 class Iterator; 敘述.

 

理論上另外一種可能的作法如下, 但是由於 class StudentList::Node; 是一個編譯器在 StudentList 為預先宣告類別時無法接受的敘述, 所以下面這個方式是不成功的

----------------- Iterator.h --------------------
class StudentList;
class StudentList::Node;

class Iterator
{
...
};
---------------- Iterator.cpp -------------------
#include "Iterator.h"
#include "StudentList.h"
...
--------------- StudentList.h ------------------
#include "Iterator.h"
class StudentList
{
...
};
-------------- StudentList.cpp -----------------
#include "StudentList.h"
...

請注意一下一般來說 myClass.h 檔案內到底應該放些什麼東西?

  1. 因為 myClass.h 檔案最主要的功能是給 "其它模組" (例如 main.cpp) 引入 class myClass 的定義的, 所以在思考的時候要從其它模組的角度來想
  2. 當然 myClass.h 裡最主要的東西是 class myClass 的定義
  3. 有的時候也會因為 myClass 和某些其他類別密切結合, 所以會引入那個類別的定義, 例如上述 StudentList.h 可能就會引入 Student.h
  4. 很多同學常常會以為 myClass.h 主要是給 myClass.cpp 引入的, 所以把 myClass.cpp 裡面所有需要引入的宣告檔案都引入進來, 例如 myClass.cpp 裡需要 iostream, string, vector, string.h, 所以就在 myClass.h 裡面引入上述, 這是不對的
  5. 原則上, myClass.h 檔案裡引入的定義檔案越少越好, 別的模組 xxx.cpp 在引入 myClass.h 時才不會發生意想不到的狀況, 例如 xxx.cpp 明明需要使用 vector, 但是卻看不到 #include <vector> 的敘述
  6. myClass.h 裡千萬不要放全域變數的定義, 會造成變數的多重定義 (multiple definitions)

最後在編譯你的程式時, 可以先點選個別 .cpp 檔案, 然後使用 建置/編譯 (Ctrl-F7) 來一個一個檔案確定語法以及所引入的檔案是否正確, 如果你使用 建置/建置方案 來編譯你的程式, 常常因為一次編譯多個檔案, 而且錯誤發生在引入的檔案中, 因為你的程式裡可能有很多地方都引入相同的檔案, 所以你弄不清楚到底是在編譯哪一個檔案時發生錯誤, 而誤導你的判斷

步驟七 定義 bool Student::ofTheSameDepartment(Student &student2); 成員函式

檢查兩個學生的系所是否相同

步驟八 請評估是否需要定義 Iterator::operator=() ?

請注意 Iterator 類別獨立於 StudentList 之外, 在使用時會有點奇怪, 這個 Iterator 類別只能和 StudentList 類別一起用, 也許叫做 StudentListIterator 比較恰當, 或者根本應該宣告在 StudentList 裡面作為一個 public inner class!!

步驟九

請助教檢查後, 將所完成的 project (去掉 debug/ 資料匣下的所有內容) 壓縮起來, 選擇 Lab10-2 上傳, 後面的實習課程可能需要使用這裡所完成的程式

C++ 物件導向程式設計課程 首頁

製作日期: 05/04/2004 by 丁培毅 (Pei-yih Ting)
E-mail: pyting@mail.ntou.edu.tw TEL: 02 24622192x6615
海洋大學 電機資訊學院 資訊工程系 Lagoon

>I>

>