Arrays, Vectors & Strings Lecture 3

Built-in arrays 数组 int a[5] = {1, 2, 4, 8, 16}; a 1 2 4 8 16 An array is a container of unnamed objects of a single type that we access by position. Container Unnamed objects Single type Access by position int b = a[2]; a[3]=7;

Built-in arrays Definition / initialization int a[5] = {1, 2, 4, 8, 16}; int b[5] = {1, 2, 4}; // ok. equivalent to int b[5] = {1, 2, 4, 0, 0}; int c[ ] = {1, 2, 4, 8, 16}; // ok. equivalent to int c[5] = {1, 2, 4, 8, 16}; const size_t N = 5; int d[N] = {1, 2, 4, 8, 16};

Built-in arrays You CAN NOT do the following. int a[4] = {1, 2, 4, 8, 16}; // error: excess elements in array initializer int b[5] = {1, 2, 4, 8, 16}; int c[5] = b; // error: array initializer must be an initializer list

Built-in arrays Array names are converted to (constant) pointers. a 1 int a[5] = {1, 2, 4, 8, 16}; 1 2 4 8 16 a int *p = a; // ok. 1 2 4 8 16 const int *q = a; // ok. int b = 3; a = &b; // error: array type ‘int [5]’ is not assignable.

Built-in arrays Array names are converted to (constant) pointers. a 1 2 4 8 16 a int a[5] = {1, 2, 4, 8, 16}; 1 2 4 8 16 int b = *a; // ok. equivalent to int b = a[0]; int c = *(a + 3); // ok. equivalent to int c = a[3]; pointer arithmetic

Built-in arrays Array names are converted to (constant) pointers. a 1 2 4 8 16 a int a[5] = {1, 2, 4, 8, 16}; 1 2 4 8 16 int **p = &a; int (*q)[5] = &a; cout << **q << endl; cout << *(*q + 4) << endl; // error: 不能用int (*)[5]初始化int ** // ok. // ok. the result is 1. // ok. the result is 16.

Array index out of bounds int a[5] = {1, 2, 4, 8, 16}; cout << a[5]; // warning: array index 5 is past the end of the array cout << *(a + 5); // problematic, but will be accepted by the compiler All warnings should be treated as errors.

Bounds checking const size_t N = 5; int a[N] = {1, 2, 4, 8, 16}; size_t j = 0; // … some other code if (j >= 0 && j < N) { // do something with element a[j] } else { // report an index-out-of-bound error size_t j = 0; // … some other code assert (j >= 0 && j < N); // do something with element a[j]

Bounds checking Think: What is the benefit of bounds checking? What is the cost of bounds checking? Should we enforce bounds checking when designing a programming language?

vector // an empty vector vector<int> a; // a vector with ten 0s vector<int> b(10); // a vector with ten 0s vector<int> c(10, 1); // a vector with ten 1s vector<int> d{1, 2, 4, 8, 16}; // supported by C++11 g++ -c some_file.cpp -o some_file.o -std=c++11 int arr[5] = {1, 2, 4, 8, 16}; vector<int> v(begin(arr), end(arr));

push_back 1 2 3 4 5 size = 5, capacity = 8 vector<int> v; 1 / 1 2 / 2 3 / 4 4 / 4 5 / 8 6 / 8 7 / 8 8 / 8 9 / 16 10 / 16 11 / 16 12 / 16 13 / 16 14 / 16 15 / 16 16 / 16 17 / 32 18 / 32 vector<int> v; for (int i = 0; i != 18; ++i) { v.push_back(i); cout << v.size( ) << “ / “ << v.capacity( ) << endl; } 1 2 3 4 5 size = 5, capacity = 8 Tested on macOS High Sierra ver. 10.13.6 with 3.1 GHz Intel Core i7 [Oct 12, 2018]

at vs. operator [ ] vector<int> v{1, 2, 4, 8, 16}; v[7] = 9; cout << v[7] << endl; v.at(7) = 9; cout << v.at(7) << endl; No bounds checking. Undefined behavior. Bounds checking. Throw a runtime out_of_range exception.

Iterators vector<int> v{1, 2, 4, 8, 16}; 迭代器 vector<int> v{1, 2, 4, 8, 16}; 指向v的第一个元素 相等判断，而非大小判断 vector<int>::iterator it = v.begin( ); for ( ; it != v.end( ); ++it) cout << *it << ” ”; 指向v的最后一个元素的下一个位置 Dereference，取指向位置的值 迭代器向后移动一个位置

Iterators 1 2 3 4 5 Think: Why left-closed, right-open? begin( ) end( ) 1 2 3 4 5 Think: Why left-closed, right-open? Why do we use != instead of < or <=?

Iterators int arr[ ] = {1, 2, 4, 8, 16}; begin(arr) / end(arr) int arr[ ] = {1, 2, 4, 8, 16}; vector<int> v(begin(arr), end(arr)); array arr iterator Overload vector<int>::iterator it; for ( it = begin(v); it != end(v); ++it ) { // do something } vector v iterator begin(v) / end(v) 实际调用v.begin( )和v.end( ) 重载：在同一个可见域中为不同的函数赋予同样的名字。

erase C++ Reference http://www.cplusplus.com/reference/vector/vector/erase/ 函数声明 删除一个迭代器指向的位置上的值 删除两个迭代器之间的所有值（左闭右开） 返回一个新的迭代器，指向最后一个被删除值的下一个位置（可能是end）。 vector上原有的迭代器，在position/first之前的继续有效，在position/first及其后的失效。

erase vector<int> v{1, 2, 4, 8, 16, 32, 64, 128, 256}; vector<int>::const_iterator it = v.begin( ) + 3; v.erase(it); cout << *it; // ok. erase 8. return value ignored. 1, 2, 4, 16, 32, 64, 128, 256 // dangerous: iterator invalidated. (undefined behavior) it = v.erase(v.begin() + 1, v.begin() + 4); cout << *it; // ok. erase 2, 4, 16. it points to 32. // ok. print 32. 1, 32, 64, 128, 256

erase 16 vector<int> v{1, 2, 4, 8, 16, 32, 64, 128, 256}; vector<int>::const_iterator it = v.begin( ) + 3; v.erase(it); cout << *it; // ok. erase 8. return value ignored. // dangerous: iterator invalidated. (undefined behavior) 16 未定义行为：C++标准未明确规定，因此相应情况的具体处理取决于各个编译器的具体实现。 正确的程序不应当依赖未定义行为。 学习过程中应注意区分哪些行为是C++标准、哪些行为是编译器扩展。 Tested on macOS High Sierra ver. 10.13.6 with 3.1 GHz Intel Core i7 [Oct 12, 2018]

erase 如果删除的不是最后一个元素，那么erase需要移动被删除位置后的所有数据来填充因为删除而产生的“空位”。

Strings H e l o , W r d ! \0 Null-terminated string “Hello, World!” null character Null-terminated string “Hello, World!” H e l o , W r d ! \0 char s1[14] = {'H’, 'e’, 'l’, 'l’, 'o’, ',’, ' ‘, 'W’, 'o’, 'r’, 'l’, 'd’, '!’, '\0'}; cout << s1 << endl; Hello, World! char s2[ ] = {'H’, 'e’, 'l’, 'l’, 'o’, ',’, ' ‘, 'W’, 'o’, 'r’, 'l’, 'd’, '!’, '\0'}; cout << s2 << endl; Hello, World! char s3[ ] = “Hello, World!”; cout << s3 << endl; Hello, World! 14 cout << sizeof(s3) / sizeof(char) << endl;

Strings H e l o , W r d ! \0 Null-terminated string “Hello, World!” null character Null-terminated string “Hello, World!” H e l o , W r d ! \0 const char *s4= “Hello, World!”; cout << s4 << endl; Hello, World! char *s5= “Hello, World!”; // warning: ISO C++11 does not allow conversion from string literal to ‘char *’ cout << s5 << endl; Tested on macOS High Sierra ver. 10.13.6 with 3.1 GHz Intel Core i7 [Oct 12, 2018]

string string: a variable-length sequence of characters

string string s1; // empty string string s2(“Hello, World!”); string s3(s2); // Hello, World! string s4(s2.begin( ), s2.begin( ) + 5); // Hello left-closed, right-open

string string s1(“Hello”); cout << s1.length( ) << endl; string s2(“World”); cout << (s1 == s2) << endl; string s3 = s1 + “, “ + s2 + “!”; cout << s3 << endl; string s4 = s3.substr(7, 10); cout << s4 << endl; 5 // equivalent to s1.size( ) // string comparison (matching) // string concatenation Hello, World! // substring. 10 characters starting from s3[7]. World!

string operations push_back( ) 添加字符到串尾，有与vector类似的capacity增长策略 insert( ) & erase( ) empty( ) & clear( ) at( ) & operator [ ] data( ) & c_str( ) begin( ) & end( ) find( ) 添加字符到串尾，有与vector类似的capacity增长策略 插入、删除，有与vector类似的迭代器失效问题 判断是否为空 / 清空（并不实际释放内存） 元素操作，at有自动的bounds checking，而[ ]没有 获取C-style的字符串char *（两个函数等价） 迭代器，分别指向首字符和尾字符的下一个位置 查找（字符或子串）

Next lecture C++ Primer, Chapters 4 & 5