Lab 2-2: Using vector, string, sort, and find

課本上 string 類別的基本使用範例如下：

#include <string>               // string
#include <string.h>             // strcpy()
#include <iostream>           // cin, cout
using namespace std;

int main()
{
    string s1, s2;                              // empty strings
    string s3 = "Hello, World.";    // initialized
    string s4("I am");                       // initialized
    char dest[100];
    s2 = "today";                               // string copy
    s1 = s3 + "  " + s4;                     // concatenation of strings
    s1 += " 8 ";                                  // appending to a sting
    cout << s1 + s2 + "!" << endl; // extended ostream
    strcpy(dest, s1.c_str());                // convert to char array
    cin >> s1;
    cout << s1.length();                     // or s1.size();
    if (s3 + s4 == "Hello, World.I am")
    {
        // do something
    }
    return 0;
}

vector 類別的使用範例如下面這個課本上運用 string 與 vector 列印資料及列號的程式

// Thinking in C++ page 105
#include <iostream>               // cout
#include <fstream>                 // ifstream 
#include <vector>                 // vector
#include <string>                    // string, getline()
#include <iomanip>                // endl
using namespace std;

int main()
{
    ifstream inf("AddLineNumber.cpp");
    string line;
    vector<string> lines;
    
    while (getline(inf, line))
        lines.push_back(line);
        
    for (int i=0; i<lines.size(); i++)
        cout << i << ":" << lines[i] << endl;
        
    // 下面是一段運用 vector 容器物件的 iterator 來依序列印所有
    // 元素的程式碼

    vector<string>::iterator iter;
    for (iter=lines.begin(); iter!=lines.end(); iter++)
        cout << iter - lines.begin() << ':' << *iter << endl;

    return 0;
}

迭代器 ( iterator) 是大部分STL 的容器類別裡面都有定義的一個內部類別 (internal class), iterator 型態的變數的 概念和使用方法 和 C 裡面的 "指標變數" 幾乎是一樣的, 以 vector 容器的 iterator 為例, 可以用 *, ->, ++, --, ==, <, -, + 等運算符號, 不過請特別注意這只是概念上相同, 實際上不見得 和 C 裡面的指標一樣是記憶體位址, 你要取得容器物件裡某一個元素的 iterator 時, 不是像 C 裡面直接在變數前面加上 & 來取得, 通常是透過 begin(), end(), find() 等等函式來取得, 但是當你有一個 iterator 時, 你可以運用取值的運算子 * 來取得所指向的資料, 或是箭號運算子 -> 來取得所指向結構的某一欄位, 比較特別的容器像是 priority_queue 並不提供 iterator, 以免客戶程式任意破壞它的封裝設計。

STL 裡還有一個 for_each, 可以用它以及容器的iterator, 巡訪容器裡所有的元素, 使用範例如下：

#include <algorithm>  // for_each()
using namespace std;

void printElement(string element)
{
    static int i=0;
    cout << ++i << ':' << element << endl;
}

int main()
{
    ....
    for_each(lines.begin(), lines.end(), printElement);
    ....
}

注意:
1. printElement 是一個函式的名稱, 也是函式的位址 (或者稱為函式指標)
2. string 本身也是一個提供 begin(), end() 以及 iterator 和 operator[] 的容器

void printChar(char element)
{
    cout << element;
}

int main()
{
    ....
    line = "Hello world\n";
    for_each(line.begin(), line.end(), printChar);
    ....
}

3. 你也可以用 vector<vector<int>> matrix(10, vector<int>(5,0)); 定義一個 10x5 的二維陣列, 每一個元素都初始化為 0, 來取代 C 裡面的 int matrix[10][5] = {{0}}; , 如此在程式執行時萬一使用到 matrix[10][0], matrix[8][-1] 時都會得到錯誤的訊息, 這樣子的設計也可以擴充為每一列元素個數不等的二維陣列。

    struct DataRecord
    {
        int lineNumber;
        int value;
    };

vector<struct DataRecord> recordArray; 或是
vector<DataRecord> recordArray;   (C++ 語法中 struct 關鍵字可省略)

然後運用 iostream 的功能將 raw1.dat 檔案內的資料讀取到 recordArray 陣列中, 將每一筆資料在該檔案內的列號記錄在 lineNumber 那個欄位中, 將每一筆資料的內容記錄在 value 那個欄位中。

DataRecord tmp;
int lineNumber = 0;
...
inf >> tmp.value;
tmp.lineNumber = ++lineNumber;
recordArray.push_back(tmp);

• 要使用 sort() 函式的話, 你需要 #include <algorithm>
• 然後請注意看 MSDN Library 中的 alg_sort.cpp 範例, 節錄如下:

  #include <algorithm>
  using namespace std;
  ...
  bool UDgreater(int elem1, int elem2) 
  {
     return elem1 > elem2;
  }
  ...
  vector<int> v1;
  ...
  sort(v1.begin(), v1.end());
  ...
  sort(v1.begin(), v1.end(), UDgreater);
  ...
  

  由於這個範例程式中 vector 的基本元素是 int, 所以才可以用 sort(v1.begin(), v1.end()) 這樣子兩個參數的型式來排序, 我們現在的應用程式中 vector 的基本元素是 DataRecord, 所以必須用第二種排序的方法,也就是 sort(v1.begin(), v1.end(), UDgreater) 來排序, 其中第三個參數是一個所謂 Binary Predicate 函式之指標 (請參考函式指標實習), 這個函式需要接受兩個參數並且進行比較大小的動作, 如果你希望第一個參數排在第二個參數前面, 這個函式就回傳 true, 否則回傳 false, 它的 prototype 可以如下述:

  bool mygreater(DataRecord elem1, DataRecord elem2);
  或是
  bool mygreater(DataRecord &elem1, DataRecord &elem2);
  或是
  bool mygreater(const DataRecord elem1, const DataRecord elem2);
  或是
  bool mygreater(const DataRecord &elem1, const DataRecord &elem2);
  或是
  int mygreater(const DataRecord &elem1, const DataRecord &elem2);
      

  請完成這個 mygreater 的函式, 完成排序的程式, 並且將結果加上列號與原始的列號一起印出來
  

請注意:

1. 請注意最後這個回傳 int 的函式和 qsort 的 compare() 函式是不一樣的, qsort 的 compare() 函式如果第一個要在第二個之前, compare() 回傳 負數, 如果順序無關緊要 compare() 就回傳 0, 如果第二個要在第一個之前, compare() 回傳 正數, 所以如果要排序的東西是 int, double 的話, 大家習慣會回傳第一個參數減遞二個參數, 但是這樣的 compare() 函式用在這裡會出現執行時的 assert 錯誤

2. mygreater() 這個函式其實叫做 myorder() 也許比較容易瞭解, 基本上 sort 會呼叫這個 myorder() 函式並且傳遞兩個參數進來, myorder() 函式裡需要判斷哪一個在排序時需要放在前面, 如果第一個要在第二個之前, myorder() 回傳 true, 如果第二個要在第一個之前, myorder() 回傳 false。

3. sort() 的第三個參數也可以是一個 functor

4. 在步驟四裡面還有一種方式可以讓 DataRecord 的物件是可以比較大小的, 就是定義一個 DataRecord::operator<() 成員函式

範例執行程式: 請下載 SortVectorDataRecord.exe 並且下載 raw1.dat 後在命令視窗 cmd 內執行

有同學發現做出來的程式和上面這個程式的結果不太一樣 (如下圖差異好像還不小)

其實左邊是 VC98 編譯出來的程式, 右邊是 VC2010 編譯出來的程式, 兩個用的函式庫的實作顯然不太一樣, 當比較的數值都相同時, 本來順序應該是沒有關係的, 你在學演算法的時候應該有學過 stable sort 的特性, 這兩個實作應該都不是 stable 的, 所得到的順序都不是原本資料裡的順序, 你也許還可以想一下如果我們主要運用 value 來比對, 當 value 相同時運用 lineNumber 來比對的話, 應該就可以得到唯一的結果了, 程式該怎麼改呢?

其它 sort 相關事項請參考下列文章

    struct DataRecord
    {
        ....
        bool operator==(const DataRecord& y);
    };
    
    bool DataRecord::operator==(const DataRecord& y)
    {
        請比較欄位 value 和 y.value 是相等的,
        同時 lineNumber 和 y.lineNumber 是相等的
    }

Hint: return ((value == y.value) && ...);

find() 函式可以搜尋一個運用容器物件 v 的 iterator 指定的區間裡面的資料, 例如:

        #include <algorithm>
        using namespace std;
        ...
        vector<DataRecord> v;
        vector<DataRecord>::iterator result;
        ...
        DataRecord goal;
        goal.value = 8;
        goal.lineNumber = 17;
        ...
        result = find(v.begin(), v.end(), goal);
        if (result != v.end())
            cout << result->lineNumber << ":" << result->value << endl;

1. 容器物件裡存放的多筆資料的起始搜尋位置, 如果你希望由第一筆資料開始比對, 你可以傳入 v.begin()
   
   
2. 容器物件裡存放的多筆資料的結束搜尋位置的下一個位置, 如果你希望比對到最後一筆資料, 你可以傳入 v.end()
   
   
3. 想要搜尋的資料

這個範例中 find() 函式會傳回一個 vector<DataRecord>::iterator 型態的資料, 如果這個資料等於 v.end() 就表示沒有找到, 如果找到的話, 你可以運用它傳回的 iterator 來列印結果, iterator 相當於指向那個找到的結構變數的指標, 所以你可以用 iterator->lineNumber 和 iterator->value 來存取那個找到的結構裡的兩個欄位, 你也可以運用 iter - v.begin() 來得到 iter 目前在容器中的位置 (類似指標運算)。

請注意 sort 演算法只能用在 vector 這種具有 random access iterator 類別的物件, 而不能用在 list 類別的物件, find 演算法則都可以運用

其它 C++ 標準函式庫之容器物件, STL Containers (b&w)

在 vector 容器上使用預設的 binary_search 演算法

C++ 標準函式庫之演算法 (b&w)

使用 iterator adaptors: ostream_iterator, istream_iterator, reverse_iterator