Hide Notes 

Slide 1: Iterators http://ecomputernotes.com
Slide 2: Iterators • Iterators are types defined by STL • Iterators are for containers like pointers are for ordinary data structures • STL iterators provide pointer operations such as * and ++ http://ecomputernotes.com
Slide 3: Iterator Categories • Input Iterators • Output Iterators • Forward Iterators • Bidirectional Iterators • Random-access Iterators http://ecomputernotes.com
Slide 4: Input Iterators • Can only read an element • Can only move in forward direction one element at a time • Support only one-pass algorithms http://ecomputernotes.com
Slide 5: Output Iterators • Can only write an element • Can only move in forward direction one element at a time • Support only one-pass algorithms http://ecomputernotes.com
Slide 6: Forward Iterators • Combine the capabilities of both input and output iterators • In addition they can bookmark a position in the container http://ecomputernotes.com
Slide 7: Bidirectional Iterators • Provide all the capabilities of forward iterators • In addition, they can move in backward direction • As a result they support multi-pass algorithms http://ecomputernotes.com
Slide 8: Random Access Iterators • Provide all the capabilities of bidirectional iterators • In addition they can directly access any element of a container http://ecomputernotes.com
Slide 9: Iterator Summary Random Access Bidirectional Forward Input Output http://ecomputernotes.com
Slide 10: Container and Iterator Types • Sequence Containers -- vector -- deque -- list -- random access -- random access -- bidirectional -- bidirectional -- bidirectional -- bidirectional -- bidirectional • Associative Containers -- set -- multiset -- map -- multimap http://ecomputernotes.com
Slide 11: …Container and Iterator Types • Container Adapters -- stack -- queue -- priority_queue --(none) --(none) --(none) http://ecomputernotes.com
Slide 12: Iterator Operations http://ecomputernotes.com
Slide 13: All Iterators • ++p - pre-increment an iterator • p++ - post-increment an iterator http://ecomputernotes.com
Slide 14: Input Iterators • *p - Dereference operator (used as rvalue) • p1 = p2 - Assignment • p1 == p2 - Equality operator • p1 != p2 - Inequality operator • p-> - Access Operator http://ecomputernotes.com
Slide 15: Output Iterators • *p - Dereference operator (can be used as lvalue) • p1 = p2 - Assignment http://ecomputernotes.com
Slide 16: Forward Iterators • Combine the operations of both input and output iterators http://ecomputernotes.com
Slide 17: Bidirectional Iterators • Besides the operations of forward iterators they also support • --p - Pre-increment operator • p-- post-decrement operator http://ecomputernotes.com
Slide 18: Random-access Iterators • Besides the operations of bidirectional iterators, they also support •p + i - Result is an iterator pointing at p +i -i •p - i - Result is an iterator pointing at p http://ecomputernotes.com
Slide 19: …Random-access Iterators • p += i - Increment iterator p by i positions • p -= i - Decrement iterator p by i positions • p[ i ] - Returns a reference of element at p + i • p1 < p2 - Returns true if p1 is before p2 in the container http://ecomputernotes.com
Slide 20: …Random-access Iterators • p1 <= p2 - Returns true if p1 is before p2 in the container or p1 is equal to p2 • p1 > p2 - Returns true if p1 is after p2 in the container • p1 >= p2 - Returns true if p1 is after p2 in the container or p1 is equal to p2 http://ecomputernotes.com
Slide 21: Example - Random Access Iterator typedef std::vector< int > IntVector; int main() { const int SIZE = 3; int iArray[ SIZE ] = { 1, 2, 3 }; IntVector iv(iArray, iArray + SIZE); IntVector::iterator it = iv.begin(); cout << “Vector contents: ”; for ( int i = 0; i < SIZE; ++i ) cout << it[i] << ", "; return 0; http://ecomputernotes.com }
Slide 22: …Sample Output Vector contents: 1, 2, 3, http://ecomputernotes.com
Slide 23: Example - Bidirectional Iterator typedef std::set< int > IntSet; int main() { const int SIZE = 3; int iArray[ SIZE ] = { 1, 2, 3 }; IntSet is( iArray, iArray + SIZE ); IntSet::iterator it = is.begin(); cout << “Set contents: ”; for (int i = 0; i < SIZE; ++i) cout << it[i] << ", "; // Error return 0; }
Slide 24: …Example - Bidirectional Iterator typedef std::set< int > IntSet; int main() { const int SIZE = 3; int iArray[ SIZE ] = { 1, 2, 3 }; IntSet is( iArray, iArray + SIZE ); IntSet::iterator it = is.begin(); cout << “Set contents: ”; for ( int i = 0; i < SIZE; ++i ) cout << *it++ << ", "; // OK return 0; http://ecomputernotes.com }
Slide 25: …Sample Output Set contents: 1, 2, 3, http://ecomputernotes.com
Slide 26: …Example - Bidirectional Iterator typedef std::set< int > IntSet; int main() { const int SIZE = 3; int iArray[ SIZE ] = { 1, 2, 3 }; IntSet is( iArray, iArray + SIZE ); IntSet::iterator it = is.end(); cout << “Set contents: ”; for (int i = 0; i < SIZE; ++i) cout << *--it << ", "; return 0; }
Slide 27: …Sample Output Set contents: 3, 2, 1, http://ecomputernotes.com
Slide 28: Example - Input Iterator #include <iostream> using std::cin; using std::cout; using std::endl; #include <iterator> int main() { int x, y, z; cout << "Enter three integers:\n"; http://ecomputernotes.com
Slide 29: …Example - Input Iterator std::istream_iterator< int > inputIt( cin ); x = *inputIt++; y = *inputIt++; z = *inputIt; cout << "x = " << x << endl; cout << "y = " << y << endl; cout << "z = " << z << endl; return 0; }
Slide 30: …Example - Input Iterator int main() { int x = 5; std::istream_iterator< int > inputIt( cin ); *inputIt = x; // Error return 0; }
Slide 31: Example - Output Iterator int main() { int x = 1, y = 2, z = 3; std::ostream_iterator< int > outputIt( cout, ", " ); *outputIt++ = x; *outputIt++ = y; *outputIt++ = z; return 0; }
Slide 32: …Example - Output Iterator int main() { int x = 1, y = 2, z = 3; std::ostream_iterator< int > outputIt( cout, ", " ); x = *outputIt++; // Error return 0; }
Slide 33: Algorithms • STL includes 70 standard algorithms • These algorithms may use iterators to manipulate containers • STL algorithms also work for ordinary pointers and data structures
Slide 34: …Algorithms • An algorithm works with a particular container only if that container supports a particular iterator category • A multi-pass algorithm for example, requires bidirectional iterator(s) at least
Slide 35: Examples
Slide 36: Mutating-Sequence Algorithms copy copy_backward fill fill_n generate generate_n iter_swap partition …
Slide 37: Non-Mutating-Sequence Algorithms adjacent_find count count_if equal find find_each find_end find_first_of …
Slide 38: Numeric Algorithms accumulate inner_product partial_sum adjacent_difference
Slide 39: Example - copy Algorithm #include <iostream> using std::cout; #include <vector> #include <algorithm> typedef std::vector< int > IntVector; int main() { int iArray[] = {1, 2, 3, 4, 5, 6}; IntVector iv( iArray, iArray + 6 );
Slide 40: …Example - copy Algorithm std::ostream_iterator< int > output( cout, ", " ); std::copy( begin, end, output ); return 0; }
Slide 41: Output 1, 2, 3, 4, 5, 6,
Slide 42: Example - fill Algorithm #include <iostream> using std::cout; using std::endl; #include <vector> #include <algorithm> typedef std::vector< int > IntVector; int main() { int iArray[] = { 1, 2, 3, 4, 5 }; IntVector iv( iArray, iArray + 5 );
Slide 43: …Example - fill Algorithm std::ostream_iterator< int > output( cout, ", " ); std::copy( iv.begin(), iv.end(), output ); std::fill(iv.begin(), iv.end(), 0); cout << endl; std::copy( iv.begin(), iv.end(), output ); return 0; }