COMS W4995 C++ Deep Dive for C Programmers

Iterators

Lecture outline

iterator1.cpp

1. For_Each() using pointers to array or vector elements

   • Explain using diagram

2. For_Each() using begin() & end()

   • For vectors, they return the appropriate pointers

   • But the same code works if we replace vector with list

     • so list::begin() can’t just return a pointer – For_Each() does ++b, which is not the right thing to do for linked list
     • it needs to be a class object for which we define operator++()
     • let’s write some pseudo-code for it

3. Iterators

   • for (list<int>::iterator i = v.begin(); i != v.end(); ++i) {

     • begin() returns an iterator pointing at the first element
     • end() returns an iterator pointing at one PAST the last element
     • many STL functions work on the half-open element range: [ b, e )

   • for (list<int>::const_iterator i = v.begin(); i != v.end(); ++i) {

     • dereferencing iterator gives you T&
     • dereferecning const_iterator gives you const T&

   • iterator and range-for loop

     • use auto to deduce iterator type
     • range-for loop simply uses begin() & end()

4. Subtleties in For_Each() implementation

   • why not (b < e) instead of (b != e)?
     • we will discuss iterator categories later
   • why not b++ instead of ++b?

     • consider how one would implement prefix and postfix increments:

       iterator& operator();     // prefix increment
       iterator  operator(int);  // postfix increment
       

iterator2.cpp

1. std::copy()

   • See possible implementation from cppreference.com
   • It simply assumes that the target container has enough space

2. ()-initializer vs. {}-initializer

   • Try the following two differnt initializers:

     vector<int> v2(5);
     vector<int> v2{5};
     

   • For STL containers, the ()-initializer syntax is for sizes and the {}-initializer syntax is for a list of elements

3. vector( std::initializer_list<T> init )

   • When an object is initialized with a brace-enclosed initializer list, and a constructor takes a std::initializer_list parameter, a std::initializer_list object is automatically constructed

   • std::initializer_list<T> is a lightweight viewer object that provides access to an array of the initializers, which may have been placed in read-only memory by the compiler

   • std::initializer_list can be implemented with a pointer and the length of the underlying array; copying a std::initializer_list does not copy the underlying array

   • std::initializer_list provides begin() and end()

4. Iterator that calls push_back()

   • IteratorThatPushes class code walk-thru

     vector<int> v2;
     copy(v1.begin(), v1.end(), IteratorThatPushes<vector<int>>{v2});
     copy(v1.begin(), v1.end(), IteratorThatPushes{v2});
     

   • STL version:

     copy(v1.begin(), v1.end(), back_inserter(v2));
     

5. ostream_iterator

   • Iterator that writes to any ostream object

     ostream_iterator<int> oi {cout, "\n"};
     copy(v2.begin(), v2.end(), oi);
     

6. istream_iterator

   • Iterator that reads from any istream object

     vector<int> v2;
     istream_iterator<int> iib {cin};
     istream_iterator<int> iie {};
     
     copy(iib, iie, back_inserter(v2));
           
     reverse(v2.begin(), v2.end());
     

7. Iterator Categories

   • Iterator categories are not concrete types. They are defined conceptually by their capabilities – i.e., by the set of operations that they support.

   • LegacyOutputIterator: supports writing and single-pass increment

   • LegacyInputIterator: supports reading and single-pass increment

   • LegacyForwardIterator: InputIter + multi-pass increment
   • LegacyBidirectionalIterator: ForwardIter + decrement
   • LegacyRandomAccessIterator: BidirIter + O(1) element access
   • LegacyContiguousIterator (since C++17): RandomIter + contiguous memory

8. Iterator Concepts (since C++20)

   • C++20 turned the idea of these capabilities into a laguage feature called “Concepts”

   • Iterator Categories were reworked into a similar but slightly different taxonomy called Iterator Concepts.

   • The old iterator category names were prepended with “Legacy”.