CS计算机代考程序代写 compiler Java c++ Systematic Traversal of Sets

Systematic Traversal of Sets
147
© Dr Markus Lumpe, 2021

Iterators
• We can use a loop statement and a loop counter to travers all elements of an array in sequence.
• However, not all data types are arrays and simple indexing may not suffice.
•Iterators offer programmers a suitable alternative to define traversal in a data type agnostic way.
• Conceptually, iterators are objects that implement the necessary infrastructure to iterate over elements of a sequence. They do this via a common interface.
• The C++ ecosystem has popularized and uses five types of iterators. Iterator objects have the look-and-feel of pointers, and advancing an iterator means to increment/decrement a pointer-like object.
148
© Dr Markus Lumpe, 2021

C++ Iterators
Input Iterator Output Iterator Forward Iterator
Bidirectional Iterator Random Access Iterator
149
© Dr Markus Lumpe, 2021

Abilities of Iterators
Iterator Category
Ability
Provider
Input Iterator
Read forward
istream
Output Iterator
Write forward
ostream, inserter
Forward Iterator
Read and write forward
Bidirectional Iterator
Read and write forward and backward
list, set, multiset, map, multimap, vector, deque, string, array
Random Access Iterator
Read and write with random access
150
© Dr Markus Lumpe, 2021

Input Iterator
Expression
Effect
*iter
Provides read access to the actual element
iter->member
Provides read access to a member of the actual element
++iter
Steps forward (returns new position)
iter++
Steps forward (returns old position)
iter1 == iter2
Returns whether iter1 and iter2 are equal
iter1 != iter2
Returns whether iter1 and iter2 are not equal
151
© Dr Markus Lumpe, 2021

Output Iterator
Expression
Effect
*iter = value
Provides write access to the actual element
++iter
Steps forward (returns new position)
iter++
Steps forward (returns old position)
An output iterator is like a “black hole.”
152
© Dr Markus Lumpe, 2021

Forward Iterator
Expression
Effect
*iter
Provides read access to the actual element
iter->member
Provides read access to a member of the actual element
++iter
Steps forward (returns new position)
iter++
Steps forward (returns old position)
iter1 == iter2
Returns whether iter1 and iter2 are equal
iter1 != iter2
Returns whether iter1 and iter2 are not equal
iter1 = iter2
Assigns an iterator
153
© Dr Markus Lumpe, 2021

Bidirectional Iterator
Expression
Effect
*iter
Provides read access to the actual element
iter->member
Provides read access to a member of the actual element
++iter
Steps forward (returns new position)
iter++
Steps forward (returns old position)
–iter
Steps backward (returns new position)
iter–
Steps backward (returns old position)
iter1 == iter2
Returns whether iter1 and iter2 are equal
iter1 != iter2
Returns whether iter1 and iter2 are not equal
iter1 = iter2
Assigns an iterator
154
© Dr Markus Lumpe, 2021

Random Access Iterator
Expression
Effect
iter[n]
Provides read access to the element at index n
iter += n
Steps n elements forward or backward
iter -= n
Steps n elements forward or backward
n+iter
Returns the iterator of the nth next element
n-iter
Returns the iterator of the nth previous element
iter – iter2
Returns disjoint distance between iter1 and iter2
iter1 < iter2 Returns whether iter1 is before iter2 iter1 > iter2
Returns whether iter1 is after iter2
iter1 <= iter2 Returns whether iter1 is not after iter2 iter1 >= iter2
Returns whether iter1 is not before iter2
155
© Dr Markus Lumpe, 2021

A Read-Only Forward Iterator
156
© Dr Markus Lumpe, 2021

Forward Iterator Constructor
Arrays are passed as pointers to the first element to functions in C++.
We must not repeat the default value.
We must use member initializer to initialize const instance variables!
157
© Dr Markus Lumpe, 2021

The Dereference Operator
• The deference operator returns the element the iterator is currently positioned on.
• The dereference operator is a const operation, that is, it does not change any instance variables of the iterator.
• We use a const reference to avoid copying the original value stored in the underlying collection.
• No range check is required. The operator*() should only be called if the iterator has not yet reached the end of the underlying collection.
158
© Dr Markus Lumpe, 2021

Prefix Increment
• The prefix increment operator advances the iterator and returns a reference of this iterator.
Return a reference to the current iterator (set forward).
159
© Dr Markus Lumpe, 2021

Postfix Increment
•The postfix increment operator advances the iterator and returns a copy of the old iterator.
Return a copy of the old iterator (position unchanged).
160
© Dr Markus Lumpe, 2021

Iterator Equivalence
Two iterators are equal if and only if they refer to the same element (this may require considering the context of ==):
• fIndex is the current index into the array
• Arrays are passed as a pointer to the first element (arrays decay to pointers) that is constant throughout runtime.
161
© Dr Markus Lumpe, 2021

Iterator Inequality
We implement != in terms of ==.
162
© Dr Markus Lumpe, 2021

Auxiliary Methods
• The methods begin() and end() return fresh iterators set to the first element and past-the-end element, respectively.
• The names and implementation of these auxiliary methods follow standard practices. The compiler may look for them when you
use a for-each loop.
163
© Dr Markus Lumpe, 2021
We use the default value 0 for aStart here.

Auxiliary Methods: Copy This Object
“clone” this object
• The methods “clone” this iterator object and set the
position accordingly.
164
© Dr Markus Lumpe, 2021

Putting Everything Together
165
© Dr Markus Lumpe, 2021

Can we do better?
166
© Dr Markus Lumpe, 2021

C++11: For-Each-Loop
• The traditional for statement in C++ reads:
for ( init-statement; condition; expression ) statement
This form uses explicit loop variables, conditions, and increments over loop variables.
• C++11 introduces a simpler form, called range for statement, to iterate through the elements of a container or other sequence:
for ( declaration : expression ) statement
This form is called for-each, and expression must denote a sequence and declaration defines a variable, set in each step of the iteration.
167
© Dr Markus Lumpe, 2021

Understanding C++11’s range loop
for ( declaration : expression ) statement
• According to the standard, this is equivalent to the following plain for loop:
auto&& __range = expression;
for ( auto __begin = begin-expression, __end = end-expression;
// C++11 forwarding (move)
// begin() // end()
__begin != __end; ++__begin )
{
}
declaration = *__begin; statement;
Compare with page 165
168
© Dr Markus Lumpe, 2021

Using C++11’s For-Each-Loop
• Case 1: read-write variable
• Case 2: constant reference
• Case 3: auto variable
• Case 4: constant auto reference
© Dr Markus Lumpe, 2021

Which declaration to use?
•In a for-each loop always use a reference variable. This avoids unnecessary copies.
• Prefer auto to explicit type declarations. Iterator types can be quite complex and hard to express. Using auto – automatic type deduction – simplifies things dramatically.
• You still need to understand what type deduction means and what the results are. Code becomes less readable, as fewer explicit detail is available.
171
© Dr Markus Lumpe, 2021

A Note on auto
• Using auto save typing and prevents correctness and
performance issues when dealing with complex types.
• Automatic type deduction via auto is no free lunch. The programmer has to guide the compiler to produce the right answer. Failing to do so, can result in a wrong type altogether.
• Using auto can produce undefined behavior. The code still compiles fine, but there is a chance the result will be unpredictable. In this case an explicit type specification is required.
173
© Dr Markus Lumpe, 2021

Iterator Interface – java.util.Iterator
• boolean hasNext():
• Returns true if the iteration has more elements. In other words, returns true if next() would return an element rather than throwing an exception.
• E next():
• Returns the next element in the iteration. Calling this method repeatedly until the hasNext() method returns false will return each element in the underlying collection exactly once.
• void remove():
• Removes the last element returned from the underlying collection.
This is an optional operation.
175
© Dr Markus Lumpe, 2021

Related Posts