ENGR 101 – LECTURE 25
COMMON ALGORITHMS AND IMPLICIT BIAS
string substr – str.substr(start, length)
– string str = “hello world!”;
cout << str.substr(0, 5) << endl; // “hello”
cout << str.substr(7, 2) << endl; // “or”
cout << str.substr(1) << endl; “ello world!”
string find – str.find(query) – str.find(query, offset)
– get the index at which substring first occurs in an original string
string str = “red fish blue fish one fish two fish”;
int x = str.find(“fish”); // 4
int y = str.find(“fish”, 5); // 14
int z = str.find(“fish”, y+1); // 23
if (str.find(“banana”) == string::npos) {
cout << “substring not found!” << endl;
}
If the substring is not found, find returns the special value string::npos.
string erase – str.erase(start, length)
– string str = “this is a string”;
str.erase(10, 2); // “this is a ring”
str.erase(7, string::npos); // “this is“ // If the second parameter is string::npos, it will erase all until
the end of the string.
str.erase(4); // “this”
vector erase
– remove elements from a vector
vector<int> vec;
// Put 8, 6, 7, 5, 3, 0, 9 into the vector
// this would remove the first element (e.g. the 8)
// vec.erase(vec.begin());
// this would remove the element at index 2 (e.g. the 7)
// vec.erase(vec.begin() + 2);
// this version would remove a range of indices (e.g. 7, 5, 3)
// vec.erase(vec.begin() + 2, vec.begin() + 5);
// this version erases all the way to the end
// vec.erase(vec.begin() + 2, vec.end());
COMMON PATTERN: FIND THE “BEST ELEMENT” (ex:min/max/desirable/closest)
// Returns the value of the maximum element in the vector
int max_element(const vector<int> &vec) {
int max_so_far = vec[0]// assume first is largest
// iterate through vector, looking for any larger
for(int i = 0; i < vec.size(); ++i) {
if(vec[i] > max_so_far) {
max_so_far = vec[i];
}
}
return max_so_far;
}
//cannot use this approach to find the largest element & change it
//cannot change vec itself (pass by const reference)
//cannot use the result return to change it from the outside
//only have the value and not index of max element
The vector size() function returns an “unsigned” int.
i < int(vec.size())
COMMON PATTERN: FIND THE INDEXT OF THE “BEST ELEMENT”
//Find the index of the minimum element rather than it’s value.
// Returns the value of the minimum element in the vector
