# Lecture 3 Strings, Vectors and Arrays

String
---
C++ 標準函式庫提供 string，可以使用這個類別來建立字串，便於進行高階的字串操作，像是字串指定、串接等。string 可以將字串指定給另一個字串，使用 size() 或 length() 來取得字串長度，使用 empty() 測試字串是否為空，使用 == 比較兩個字串的內容是否相同若要表現字串。C++ 建議使用 string，但要先 include string 標頭檔，並以下方式來建立實例，例如：

string str1;                 // 內容為空字串
string str2("caterpillar");  // 內容為指定的字串常量
string str3(str2);           // 以 str1 實例建立字串
string str4 = "Justin";      // 內容為指定的字串常量

另外在 string 的 input/output 中，需要注意若以 cin>>string 的寫法由終端機輸入的文字遇到空白格會忽略後續的文字，若要輸入一段文字則以 getline() 的寫法達成目的。

string s;
cin >> s; //input Hello World!
cout << s << endl; //output Hello

string line;
getline(cin, line); //input Hello World!
cout << line << endl; //output Hello World!

string s;
while (cin >> s) // CTRL+D to end loop
cout << s << endl;

loop over strings，並使用 [ ] 指定索引來存取相對應位置的 char

for(auto index = 0; index != s.size(); index++)
    cout << s[index] << endl;
for(auto ch : s): // for each element in s
    cout << ch << endl;
    

Vector
---
如果需要長度可變的資料容器，可以使用 vector，使用時需要包含< vector >標頭檔。vector 可以裝載指定型態的資料，如建立一個可裝載 int 的 vector < int >：

vector<int> ivec1 = {10, 20, 30}; // equal to vector<int> ivec{10, 20, 30}
vector<int> ivec2{3, 'oop'}; // equal to vector<int> ivec{'oop', 'oop', 'oop'}
vector<Sales_item> salesVec;
vector<vector<int> > matInt;
vector<int> ivec3(ivec1); // has a copy of each elements in ivec1

若要使用陣列的元素來建構 vector，可以透過以下的方式

int number[] = {10, 20, 30, 40, 50};
vector<int> v(begin(number) + 2, end(number)); // 包含 30, 40, 50

如果打算對 vector 進行排序、尋找、反轉等操作，可以使用包含< algorithm >標頭檔：
* 排序

vector<int> ivec = {30, 12, 55, 31, 98, 11, 41, 80, 66, 21};

sort(ivec.begin(), ivec.end());
for(auto i : ivec)
    cout << i << " ";
// 11 12 21 30 31 41 55 66 80 98

* 搜尋

// find() returns An iterator to the first element in the range that compares equal to val.
// If no elements match, the function returns last.
cout << "輸入搜尋值：";
int search = 0;
cin >> search;

auto it = find(ivec.begin(), ivec.end(), search);
cout << (it != ivec.end() ? "找到" : "沒有")
     << "搜尋值" 
     << endl;
/*輸入搜尋值：22
沒有搜尋值*/

* 反轉

reverse(ivec.begin(), ivec.end());
for(auto i : ivec) 
    cout << i << " ";

// 98 80 66 55 41 31 30 21 12 11

#### some operation of vector
vector 的 size 方法得知元素的個數，empty 方法可以得知是否為空，front 方法可以取得第一個元素，back 方法可以取得最後一個元素，想要新增元素，可以使用 push_back、insert 方法，想取出最後一個元素可以用 pop_back，clear 可以清空 vector 等。

ivec1.empty(); // returns true if ivec1 is empty; otherwise returns false
ivec1.size(); // returns the number of elements in ivec1

ivec1[0]; // get the n element in ivec1, equal to ivec.at(n)
ivec1.front(); // get the first element in ivec1
ivec1.back(); // get the last element in ivec1

ivec1.pop_back(); // removes last element
ivec1.push_back(40); // ivec{10,20,40}
ivec1.insert(ivec1.begin(), 5); // inserts 5 at the beginning
ivec2 = ivec1; // replace the elements in ivec2 with a copy of those in ivec1
if(ivec1 == ivec2)
    cout << "ivec has the same elements in ivec2" << endl;
ivec1.clear(); // erases the vector

#### loop over a vector
1. use for range method

vector<int> v{ 1, 2, 3 };
for (auto &i : v) // note: i is a reference{
    i *= i; // square the element value
    cout << i << " "; // print the element
}
cout << endl;

2. use index to access elenments with v.size()

vector<int> v{ 1, 2, 3 };
for (decltype(v.size()) idx = 0; idx != v.size(); ++idx){
v[idx] = v[idx] * v[idx];
cout << v[idx] << " ";
}
cout << endl;

3. use Iterators
iterator 是一個通用指標，不僅用於 vector 這種容器上。其機制便於取得容器中特定位置的元素，且是在 iterate 時非常便利，所寫的程式碼與其他容器具有高度相容性。begin 與 end 方法分別傳回起始位置與結束位置的 vector< int >::iterator，可以把它們看成代表首個元素與最後一個元素的位置，對它們進行 + 或 - 運算，表示元素的位移量，操作上很像指標，至於是不是真的指標，要看底層的實作而定。就 API 的設計來說，不建議將 begin、end 方法的傳回值看成是指標，而建議將之看成迭代器（iterator），這些迭代器重載了相關的運算子，令其看來像是指標操作。如對 iterator 使用 * dereference operator，可以取得該位置實際儲存的物件；並使用 ++ increment operator 來往下一個元素前進。

vector<int> vec{1,2,3}
auto b = vec.beign()
*b = 0; vec{0,2,3}

// C++11 way
for (auto iter = ivec.begin(); iter != ivec.end(); ++iter)
    *iter = 0; // set element to which iter refers to 0

// cbegin() & cend() are const_iterator
// const_iterator for reading but not writing to the elements in the container
for (auto iter = text.cbegin(); iter != text.cend(); ++iter)
    cout << *iter << endl;

Array
---
C++ 提供陣列（array），可以宣告一個以索引（index）作為識別的資料結構，在宣告時包含儲存的資料型態及陣列長度，而長度必須是個編譯時期常數。若要動態宣告陣列長度，可以使用一些資料結構與動態記憶體宣告來解決。與 vector 相比，陣列不可以直接指定給另一陣列，只能依序進行複製；若直接比較兩個陣列是否相同的話，並不是比較其內容而是比較其位址。想比較陣列元素是否相同，也只能逐一比對。但相較下有較好的執行效率。若打算對陣列進行排序、尋找、反轉等操作，同樣使用< algorithm >標頭檔進行。

int intArray[3] = {0}; // {0,0,0}
char ca0[0] = {'\0'}; // 字元陣列會被初始為空字元（'\0'）

int intArray[3] = {0, 1, 2}; // element initialization
int intArray[] = {0, 1, 2}; // element initialization
char ca1[] = {‘C’, ‘+’, ‘+’}; // dim = 3
char ca2[] = {‘C’, ‘+’, ‘+’, ‘\0’}; // dim = 4
char ca3[] = “C++”; // {‘C’,‘+’,‘+’,‘\0’}, dim = 4

如果使用 const 或 constexpr 來修飾陣列，每個索引位置就成為唯讀。

constexpr int ia[] = {1, 2, 3};
ia[1] = 10; // error: assignment of read-only location 'ia[1]'

陣列在使用時，得知陣列長度是必要的。當存取超過陣列長度的記憶體，會發生無法預期的結果，然而陣列本身並不知道自己的長度資訊。可以透過以下方式記錄陣列長度，而當在使用陣列中元素的索引值時，通常會將這個索引值定義為 size_t 的資料型態。這種資料型態確保其記憶體空間夠大以容納陣列中全部元素。

const size_t array_size = 5
int ia[array_size] = {0, 1, 2, 3, 4};
int length = sizeof(ia) / sizeof(ia[0]);
for (size_t i=0; i != array_size ; ++i)
    ia[i] = i;

#### 陣列與指標
陣列名稱本身就儲存了陣列記憶體的首個位置的位址，陣列的索引值表示陣列元素是相對於第一個位址的位移量（offset）。位移的量與資料型態長度有關，如果是 int 整數，每次位移時是一個 int 整數的長度，例如在上例中 ia[0] 索引值為 0 時，表示位移量為 0，自然就是指第一個元素，而 ia[3] 就是指相對於首個元素的位移量為 3。

int ia[] = {0,2,4,6,8};
int *ip = ia; // ip points to ia[0]
int *ip2 = ip+4; // ip2 points to ia[4]
++ip; // ip points to arr[1]

#### loop over an array
1. use for range method

int ia[5] = {0, 1, 2, 3, 4};

for(auto i : ia)
    cout << i << " ";
cout << endl;

2. use index to access elenments

const size_t array_size = 10;
int ia[array_size];
cout << "The contents are: ";
for (size_t ix = 0; ix < array_size; ++ix) {
    ia[ix] = ix;
    cout << ia[ix] << ' ';
}
cout << endl;

3. use Iterators

const size_t array_size = 10;
int ia[array_size];
int *pbeg = begin(ia), *pend = end(ia);
size_t cnt = 0;
cout << "The contents are: ";

// Using begin and end, it is rather easy to write a loop to process the elements in an array.
while (pbeg != pend){
    *pbeg = cnt++;
    cout << *pbeg++ << ' ';
}
cout << endl;