Programming in C++
Iterators, STL algorithms
12/11/2019
CE221 Part 6
Copyright By PowCoder代写 加微信 powcoder
Iterators 1
An iterator can be regarded as a smart pointer that points to each element in a collection in turn; programs that use iterators should contain the line #include
An iterator is not actually a pointer but the unary * operator has been overloaded so it can be used to refer to the element of the collection that the iterator “points” to. In addition the ++ operator has been overloaded to allow the pointer to be advanced to the next element in the collection. Some iterators also have overloaded version of operators such as — and +=.
An iterator is declared using syntax such as vector
12/11/2019 CE221 Part 6
Iterators 2
There are three different types of iterator: unidirectional (with just ++), bidirectional (with ++ and –) and random-access (with full “pointer” arithmetic); which iterators are available depends on the container class. There are also constant versions which can be used to traverse a collection but not modify its contents.
To obtain an iterator that starts at the beginning of a collection the begin function from the container class should be used, e.g.
vector
The function returns an object of type T::iterator where T is the type of the object to which it is applied; an implicit type conversion is invoked when a constant iterator is required.
12/11/2019 CE221 Part 6
Iterators 3
The end function from the container class returns an iterator whose pointer position is just after the last element of the collection so we can compare the current state of our iterator with myvec.end() to determine whether all items have been traversed. We should use == or != to perform the comparison
since not all iterators have < or <= operators.
The end function also returns a non-constant iterator, but the == and != operators regard a constant iterator and a non-constant iterator that point to the same element in a collection as being equal.
12/11/2019 CE221 Part 6
Iterators 4
We can use the following loop to print the contents of a vector v with element type int one item per line.
vector
for (it = v.begin(); it != v.end(); it++)
cout << *it << endl;
The following loop will replace all values greater than 100 in the vector with the value 0. (This time we cannot use a constant iterator.)
vector
for (it = v.begin(); it != v.end(); it++) if (*it > 100)
12/11/2019 CE221 Part 6
Iterators 5
If we wish to traverse a collection in reverse order and the container supports only unidirectional iterators we need to use a reverse iterator. The following loop will print the contents of v in reverse order.
vector
for (rit = v.rbegin(); rit != v.rend(); rit++) cout << *rit << endl;
Observe that we need to use the functions rbegin and rend to obtain reverse iterators, and ++ (not --) is used to move to the previous element.
12/11/2019 CE221 Part 6
Iterators 6
The vector and string classes support random-access iterators so it is not in fact necessary to use a reverse iterator to access the contents in reverse order; we could use -- to step through the elements from v.end() to v.begin(). (Since we need to access the element referred to by v.begin() but not the one referred to by v.end() we cannot use a for loop with a similar structure to the previous slides.
vector
while (it != v.begin()) { it–;
cout << *it << endl;
12/11/2019 CE221 Part 6
The erase Function 1
The erase function of a container class may be used to remove one or more elements from a collection. The function takes one or two arguments which must be non-constant iterators for the appropriate container class. The single-argument version simply removes the element currently pointed to by the iterator; an exception will be thrown if the iterator does not point to an element of the collection.
We can remove the first element from a vector v (or any other container) using v.erase(v.begin()). To remove the element at location n we could use v.erase(v.begin()+n); this technique can be used only with containers that have random- access iterators.
12/11/2019 CE221 Part 6
The erase Function 2
We could use the following code to locate and remove the first
occurrence of 0 in the vector v.
vector
while (it != v.end() && *it != 0)
if (it != v.end()) v.erase(it);
Note that after using the erase function the iterator will point to an element that has been removed from the collection so it is unsafe to try to continue using it. However the function returns a new iterator object that points to the next element after the removed element(s) so we can use it = v.erase(it) if we need to continue iterating.
12/11/2019 CE221 Part 6
The erase Function 3
The two-argument version of erase will remove a sequence of elements starting with the element pointed to by the first argument and ending immediately before the element pointed to by the second argument so to remove the elements at locations 3, 4 and 5 from the vector v we could use v.erase(v.begin()+3, v.begin()+6). and to remove all but the first six elements we could use v.erase(v.begin()+6, v.end()).
The two arguments must have the same type so we cannot use a combination of a normal iterator and a reverse iterator. An exception will be thrown if the iterator does not point to an element in the container, e.g. if we try to use something like v1.erase(v2.begin()).
12/11/2019 CE221 Part 6
Inserting into Vectors 1
The vector class has three insert member functions allowing new elements to be inserted at a position specified by an iterator. (Note that unlike erase these functions are not provided by all of the container classes.) In all of these the element(s) will be inserted in front of the position pointed to be the first argument; an exception will be thrown if the iterator does not “point” either to an element of the collection or to the position immediately after the last element.
12/11/2019 CE221 Part 6
Inserting into Vectors 2
The simplest insert function has just two arguments, the second being the item to be inserted.
v.insert(v.begin()+2, 4);
// inserts 4 in front of v[2]
The second insert function allows multiple copies of the same element to be inserted. This takes the number of copies as its second argument and the element as its third argument.
v.insert(v.begin()+3, 2, 5);
// inserts 2 copies of 5 in front of v[3]
12/11/2019 CE221 Part 6
Inserting into Vectors 3
The third insert function allows a sequence of elements from another collection (which does not have to be a vector) or from an array to be inserted at a position specified by an iterator. The second argument specifies the location of the beginning of the sequence and the third the location immediately after the end of the sequence. If the sequence comes from an array these arguments should be addresses; otherwise they should be two iterators of the same type each of which points to an element in the same collection object.
int a[] = ……… v.insert(v.begin(), a, a+5);
// inserts copies of first 5 elements of a
12/11/2019 CE221 Part 6
If several functions in a program used constant reverse iterators for vector
After defining the type CRI using
typedef vector
we could declare constant reverse iterators by simply using declarations of the form CRI it;.
12/11/2019 CE221 Part 6
The position of the name of a type in a typedef statement is always the same position as that of a variable of that type in a declaration.
Hence, for example, since int *p[40]; would define p to be an array of 40 pointers to integers,
typedef int *PA[40];
would define the type PA to be “array of 40 pointers to integers”.
[ We can tell that the variable declaration gives an array of pointers rather than a pointer to an array since the precedence rules state that the expression *p[39] means *(p[39]) so p must be an array and p[39] must be a pointer. ]
12/11/2019 CE221 Part 6
It is possible to include typedef statements inside class
declarations. Consider for example
{ typedef …X…
Inside the class declaration we can use the name X to refer to the type specified by the typedef statement; outside the class we would have to use C::X.
This is in fact how the writers of the standard template library were able to define types like vector
12/11/2019 CE221 Part 6
Using auto in C++11 1
C++ 11 introduced a facility for the compiler to infer types of variables from their initialisation, avoiding the need to explicitly use lengthy type names in declarations.
In a declaration of the form
auto x = e;
the type of x will be the type of the expression e.
Note that if e is a call to a function that returns a reference the type of x will not be a reference; if we want a reference we must explicitly use the & symbol:
auto &x = myfun(y);
12/11/2019 CE221 Part 6
Using auto in C++11 2 Using C++ 11 we could have written on slide 7
auto it = v.end();
instead of
vector
However, since the return type of the end function is an iterator rather than a constant iterator, the code on slide 6 invokes an implicit type conversion. The inferred type of it would be vector
12/11/2019 CE221 Part 6
Using auto in C++11 3
Note that auto can be used only when the variable is given an
initial value in its declaration. We could not replace
vector
from slide 6 with
However, we could have used
auto rit = v.begin();
for (; rit != v.rend(); rit++) cout << *rit << endl;
12/11/2019 CE221 Part 6
STL Algorithms 1
The standard template library has a large collection of functions known as algorithms that can be used to search and manipulate the contents of containers or strings. To allow these algorithms to be implemented without reference to specific container types they access the containers through iterators and when a reference to an item in the collection needs to be returned this is also done via an iterator.
The STL has about 70 algorithms, including find, replace, search, sort, copy, and remove. Not all algorithms work with all container classes; for example a set is an unordered collection of items ({1, 2, 3} is the same set as {3, 1 ,2}) so there is no concept of being sorted for a set.
12/11/2019 CE221 Part 7
STL Algorithms 2
All algorithms take two iterator objects as arguments, specifying the start and end of the portion of the collection to which the algorithm is applied. (If this is the whole collection the results returned by begin and end or rbegin and rend should be used.) There will often be additional arguments. As usual the end argument should be an iterator that references the element after the last item in the portion.
To use most algorithms a program must contain the line #include
12/11/2019 CE221 Part 7
The find algorithm will return an iterator that references some occurrence of a specific value, supplied as a third argument. In the case of a sequence container or string this will be the first occurrence (or last occurrence if a reverse iterator is being used). If the value does not occur in the collection the end iterator for the collection or portion of the collection (i.e. that supplied as the second argument) will be returned.
The code fragment on the next slide will print the contents of the vector v (of items of type int) from the first occurrence of 0 to the end of the vector and also the substring of the string s extending from the character following the first occurrence of ‘*’ to the end of the string.
12/11/2019 CE221 Part 7
typedef vector
typedef string::const_iterator StrIter;
VecIter zero = find(v.begin(), v.end(), 0)
for (VecIter it1 = zero; it1!=v.end(); it1++) cout << *it1 << ' ';
cout << endl;
StrIter star = find(s.begin(), s.end(), '*')
if (star != s.end())
for (StrIter it2 = star+1; it2!=s.end(); it2++)
cout << *it2; cout << endl;
12/11/2019 CE221 Part 7
The following function will return the number of occurrences of the character c in the string s
int count(char c, const string& s) { int occs = 0;
string::const_iterator it =
find(s.begin(), s.end(), c);
while (it!=s.end()) { occs++;
it = find(it+1, s.end(), c);
return occs; }
12/11/2019 CE221 Part 7
We could also write a template version that will count the number of occurrences of an item in any collection with the correct item type.
template
typename C::const_iterator it =
find(s.begin(), s.end(), val);
while (it!=s.end())
it = find(it+1, s.end(), val)
return occs; }
12/11/2019 CE221 Part 7
There is nothing in the code on the previous slide to indicate that C should denote a container class and the objects in C should have type T. However if an attempt were made to call the function with classes that do not satisfy this a type error would be raised when trying to generate a call to find.
Since the compiler does not know that C should denote a container class it would not know that C::const_iterator is a type rather than a class member and would try to treat it as the latter unless it is informed that it is the name of a type; hence we have to use the keyword typename.
12/11/2019 CE221 Part 7
The two-argument sort algorithm will sort the contents of a collection (or part of a collection) into ascending order (i.e. smallest first). It can be used only with containers that support random-access iterators. Comparison of items within the function is performed using the < operator so if the items in the collection are objects they must belong to a class that has an operator< function. The function changes the order of the contents within the container so it does not make a copy and does not return a result.
If the arguments are reverse iterators the contents of the collection will be sorted into descending order.
12/11/2019 CE221 Part 7
while (it!=v.end())
{ cout << *it;
if (++it != v.end())
cout << ',';
cout << '>‘ << endl;
// continued on next slide
vector
// sortdemo.cpp – demonstration of sort
using namespace std;
#include
template
{ cout << '<';
12/11/2019
CE221 Part 7
sort 3 // sortdemo.cpp continued
int main()
{ vector
v.push_back(7);
v.push_back(17);
v.push_back(3); // v now holds [7,17,3]
vector
printvec(v); // outputs <3,7,17> sort(v2.rbegin(), v2.rend())
printvec(v2); // outputs <17,7,3>
12/11/2019 CE221 Part 7
There is a three-argument sort algorithm that will sort the contents using a programmer-supplied comparison function instead of <. This is useful when we wish to sort a sequence of objects and the value to be used for sorting is one of the members of the class but either the operator< function of the class compares a different member or the class has no operator< function.
The third argument to sort should be a pointer to a boolean function that takes two arguments (constant references to the items to be compared) and returns true if the value of the first argument is less than the value of the second argument using the ordering that we wish to use.
12/11/2019 CE221 Part 7
The code below will sort a vector v of type Vector
[ Recall that to pass a pointer to a function as an argument to another function we simply supply the function’s name. ]
bool compareMark(const Student& s1, const Student& s2)
{ return s1.aveMark < s2.aveMark;
// need a reverse iterator for descending order sort(v.rbegin(), v.rend(), compareMark);
12/11/2019 CE221 Part 7
for_each 1
The for_each algorithm provides in C++ some of the functionality of Java's for int i:myList or Python's for i in myList. Its use is not required since the introduction of range-based for loops in C++11. However a programmer may have to adapt code that was written before C++11 so should know how to use it. As for_each is a function rather than a loop construct we have to provide the "loop body" as an argument. This must be a pointer to a function that will be called with each of the elements of the collection in turn as its argument; hence it must have a single parameter whose type should be the type of the items in the collection. Any result returned by the function will be ignored.
12/11/2019 CE221 Part 7
for_each 2
We can print the contents of a vector of integers one item per line by supplying a function that will print a single integer and a newline as an argument to for_each:
void print(int i)
{ cout << i << endl;
vector
for_each(v.begin(), v.end(), print);
12/11/2019 CE221 Part 7
for_each 3 In Java we might write code such as:
int sum = 0;
for (int i:myList) sum += i;
Since the “loop body” in C++ has to be written as a function it cannot access any local variables from the function that makes the call to for_each so if we wished to write similar code in C++ we would have to use a global variable:
void addtoSum(int i) { sum += i; }
int main() { ……
for_each(v.begin(), v.end(), addtoSum); }
12/11/2019 CE221 Part 7
accumulate 1
There are ways to overcome the need to use a global variable by
using class objects but these are complicated..
Since the task of obtaining value such as sums, products, minimum and maximum values is often needed and could not be done easily nefore the introduction of range-based for loops an algorithm to perform such tasks is provided in the STL. It is called accumulate (and declared in the
sum = accumulate(v.begin(), v.end(), 0)
The third argument is a starting value. Items from the collection are repeatedly added to this with the final value being returned.
12/11/2019 CE221 Part 7
accumulate 2
Note that the return type of accumulate is determined by the type of the third argument since it is being used to build up the result. If we used
sum = accumulate(v.begin(), v.end(), 0.0)
the sum would be a real number.
To use accumulate to generate anything but the sum we need to supply as a fourth argument a pointer to a two-argument function to be performed instead of addition – its first argument and return type need to have the same type as the third argument to accumulate and the type of its second argument should be the type of the items in the collection.
12/11/2019 CE221 Part 7
accumulate 3
A call to accumulate(it, end, x, f) will effectively perform a loop o
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com