1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

C++ STL Iterators

Discussion in 'C++' started by BiplabKamal, Jun 27, 2016.

  1. BiplabKamal

    BiplabKamal New Member

    Joined:
    Dec 30, 2015
    Messages:
    36
    Likes Received:
    5
    Trophy Points:
    0
    Occupation:
    Software Engineer
    Location:
    Kolkata
    Iterator is a concept of objects which can be used to traverse through the elements of a collection of objects like STL containers. An iterator object can point to an element within a range of elements and provides a mean to move the pointer through other elements within that range using operators. An iterator must support at leas increment operator (++) and dereference operator (*). There is no single type of iterators. Pointer is the most simple and obvious form of iterators which can point to any element of an array and can iterate through the array of elements using increment (++) and decrement (++) operators.

    STL standard has divided all type of iterators in 5 categories:
    Input and output iterators have the minimum capabilities like reading or writing the elements in one direction. Forward iterator have the capability of both input and output iterators and also can be moved sequentially in forward direction. Bidirectional iterator has all the capabilities of forward iterator plus it can move in backward direction also. The super power iterator called random access iterator has the capability of moving at any direction plus it can move to any element with constant time. Any random access iterator also a bidirectional iterator which is also a forward iterator and in turn input and output iterator. Iterator mainly supports operators and constructors. Following figure depicts the relationship among iterators:

    [​IMG]

    These categories works as a guidelines not a strict rule. You are free to implement an iterator which may not fall in any of the categories completely. For example you can have an iterator which allows only input operation but can move towards both the direction. Following the guidelines, will help in understanding and communication. Iterators returned by any iterator function of STL containers will fall in any of the categories. To get more familiar with different categories of iterators let us implement an iterator starting from input and output iterators to random access iterator. We will have our own container class and define iterator for the container class. We will upgrade the iterator starting from input/output iterator to random access iterator. STL provides an std::iterator class in it’s header <iterator> which can be used as the base class of any iterator. Though you are free to implement any iterator without inheriting the std::iterator class, it is required if you want to use your iterator in any STL algorithms. STL algorithm functions retrieve iterator properties like iterator category from this base iterator. For this purpose the STL algorithms use another class std::iterator_traits. Iterator class does not have any functionality but some typedef members. The two classes declaration are shown below:
    Code:
    std::itertor:
    template <class Category,              // iterator::iterator_category
    class T,                     // iterator::value_type
    class Distance = ptrdiff_t,  // iterator::difference_type
    class Pointer = T*,          // iterator::pointer
    class Reference = T&         // iterator::reference
    > class iterator;
    
    std::itertor_traits
    template <class Iterator> class iterator_traits;
    template <class T> class iterator_traits<T*>;
    template <class T> class iterator_traits<const T*>;
    
    We will derive our iterator from the std::iterator so that we can apply STL algorithms on it. Throughout the examples we will use following class for elements type used by our container and the iterator classes.

    Code:
    #include<iostream>
    
    //Employee data structure
    struct Employee
    {
        unsigned EmpId;
        wchar_t EmpName[100];
        Employee() :EmpId{ 0 }
        {
            wcscpy_s(EmpName, L"");
        }
        Employee(unsigned id, wchar_t name[]) :EmpId{ id }
        {
            wcscpy_s(EmpName, name);
        }
        // Equality comparison operator
        bool operator ==(const Employee e) const
        {
            return (EmpId == e.EmpId && wcscmp(EmpName, e.EmpName) == 0);
    
        }
        // Operator for less than comparison
        bool operator <(const Employee e) const
        {
            return (EmpId < e.EmpId);
    
        }
        // Operator for greater than comparison
        bool operator >(const Employee e) const
        {
            return (EmpId > e.EmpId);
    
        }
    };
    //Overloading oprator << for wostream and Employee to print the Emloyee data on the console
    wostream& operator<<(wostream& o, const Employee& e)
    {
        o << "Employee Id = " << e.EmpId << "," << "Employee Name = " << e.EmpName << endl;
        return o;
    }
    //////////////
    
    Following is the class which is like a container class we will use throughout the examples. This class uses Employee class as its element type.
    Code:
    #include<iostream>
    ////////////////
    // The container class store the element in a sequential storage and provides iterators to access its elements
    class MyContainerClass
    {
        const static unsigned size = 20; // Max capacity of the container
        unsigned Count;
        Employee employees[size];
    public:
        MyContainerClass() :Count{ 0 }
        {
    
        }
        // Display the elements
        void ShowElements()
        {
            for (unsigned int i = 0;i < Count;++i)
                std::wcout << employees[i];
        }
        // Will add a new element at the end
        void Addlast(Employee e)
        {
            if (Count < size)
            {
                employees[Count] = e;
                ++Count;
            }
        }
        //Will remove the last element
        void RemoveLast()
        {
            if (Count>0)
                --Count;
        }
        // Will return the iterator pointing to the firts element
        Myiterator Begin()
        {
            return Myiterator(employees);
        }
        //Will return the iterator pointing to the one past to end element
        Myiterator End()
        {
            return Myiterator(employees + Count);
        }
    };
    //////////////
    
    In the examples followed we will implement the iterator class and the main() function to test the iterator capabilities. To compile and run the application you need to copy Employee class and it’s << operator overload before the iterator class and the MyContainerClass class after the iterator class.

    In the main() function some code is kept commented. You can try to uncomment and compile, it will give compiler error. Once we upgrade the iterator class to most capable iterator i. e. random access iterator all the commented code will be compiled.

    Input and Output Iterator



    Input and output iterators are most basic iterator as per STL guideline. They are single pass iterators, means once they are incremented you are not assured that the previous element is still valid. The example of just input iterator and just output iterator is std:istream_iterator and std:eek:stream_iterator respectively. Once you read/write a byte from/to the underlying stream you cannot read/write the same byte again. In following example we are going to implement an input iterator.

    Example: Input Iterator

    Code:
    #include<iterator>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    //Iterator class for MyContainerClass class
    class Myiterator:public iterator<std::input_iterator_tag,Employee>
    {
        // Pointer to an element of the range of elements
        Employee *pEmp;
        //Constructor is kept private so that instance cannot be created by others except the MyContainerClass which is a friend
        Myiterator(Employee* p) :pEmp{ p }
        {
    
        }
    public:
        ~Myiterator(){}
        friend class MyContainerClass;
        // Copy Constructor is required for all iterators
        Myiterator(const Myiterator& itr)
        {
            pEmp = itr.pEmp;
    
        }
        //Single pass dereference operator only for read operation of input iterator
        const Employee& operator *()
        {
            return *pEmp;
        }
        // Pre-increment operator required for all iterators    
        Myiterator operator ++()
        {
            ++pEmp;
            return *this;
        }
        // Post-increment operator required for all iterators
        Myiterator operator ++(int)
        {
            Myiterator itr = *this;
            ++pEmp;
            return itr;
        }
        // Inequality operation required for input iterator
        bool operator != (const Myiterator& it)
        {
            return (pEmp != it.pEmp);
        }
        // Equality operation required for input iterator
        bool operator == (const Myiterator& it)
        {
            return (pEmp == it.pEmp);
        }
        // Assignment operator required for all iterators
        Myiterator& operator = (const Myiterator& it)
        {
            if (&it !=this)
            {
                (pEmp = it.pEmp);
            }
            return *this;
        }
    };
    
    int main()
    {
        MyContainerClass c;
        c.Addlast(Employee(1,L"Bimal") );
        c.Addlast(Employee(2, L"Amal"));
        c.Addlast(Employee(3, L"Kamal"));
        c.Addlast(Employee(4, L"Matin"));
        c.Addlast(Employee(5, L"Jatin"));
        c.Addlast(Employee(6, L"Nitin"));
        c.Addlast(Employee(7, L"Ela"));
        c.Addlast(Employee(8, L"Bela"));
        c.Addlast(Employee(9, L"Shila"));
        c.Addlast(Employee(10, L"Cris"));
    
        // Acquiring iterators
        auto begin = c.Begin();
        auto end = c.End();
        // Copy construction operation
        auto beginitr = begin;
        auto enditr = end;
    
        // Assignment operation
        beginitr = begin;
        enditr = end;
        
        //Default constructor
        //Myiterator enditr; // default constructor required only for forward operator
    
        // Read operation    
        Employee emp = *begin; // read the element
        wcout<<"The first element: " << emp<<endl;
    
        cout << "The elements are: " << endl;
        while(begin != end) // Inequiality comparison
        {
            wcout << (*begin++); // Increment the iterator.
        }
        //Increament operation
        wcout << "The first element is " << *(beginitr++);
        wcout << "The 3rd element is " << *(++beginitr);
    
        //Decreament operation
        //wcout << "The last element is " << *(--enditr) << endl; // Allowed only for bidirectional iterator
        //wcout << "The end last element is " << *(enditr--) << endl; // Allowed only for bidirectional iterator
    
        
        // Comparison operators
        if (begin == end)
            cout << "End of range reached" << endl;
        /*if (begin < end) //Allowed only for random access iterator
            cout << "More elements to traverse" << endl;
        if (end>begin) //Allowed only for random access iterator
            cout << "More elements to traverse" << endl;
        if (begin <= end) //Allowed only for random access iterator
            cout << "More elements may be there to traverse" << endl;
        if (end>=begin) //Allowed only for random access iterator
            cout << "More elements may be there to traverse" << endl;
            
        // Accessing elements randomly
        //wcout<<endl << "The 5th element is " << *(beginitr + 4) << endl; //Allowed only for random access iterator
        //wcout << "The last 2nd element is " << *(enditr -2) << endl;//Allowed only for random access iterator
        //wcout << "The 6th element is " << beginitr[5] << endl; //Allowed only for random access iterator
        beginitr += 2;//Allowed only for random access iterator
        wcout << "The 3rd element is " << *beginitr << endl;
        
        enditr -= 3;//Allowed only for random access iterator
        wcout << "The last 3rd element is " << *enditr << endl;*/
    
        // Using std algorithm 
        cout <<endl<< "Applying algorithm: " << endl;
        std::for_each(c.Begin(), c.End(), [](Employee e) {wcout << e;});
        if(std::find(c.Begin(), c.End(), Employee(8, L"Bela"))!= c.End())
            cout << "Employee Bela found" << endl;
        
        return 0;
    }
    
    OUTPUT
    Code:
    The first element: Employee Id = 1,Employee Name = Bimal
    
    The elements are:
    Employee Id = 1,Employee Name = Bimal
    Employee Id = 2,Employee Name = Amal
    Employee Id = 3,Employee Name = Kamal
    Employee Id = 4,Employee Name = Matin
    Employee Id = 5,Employee Name = Jatin
    Employee Id = 6,Employee Name = Nitin
    Employee Id = 7,Employee Name = Ela
    Employee Id = 8,Employee Name = Bela
    Employee Id = 9,Employee Name = Shila
    Employee Id = 10,Employee Name = Cris
    The first element is Employee Id = 1,Employee Name = Bimal
    The 3rd element is Employee Id = 3,Employee Name = Kamal
    End of range reached
    Applying algorithm:
    
    Employee Id = 1,Employee Name = Bimal
    Employee Id = 2,Employee Name = Amal
    Employee Id = 3,Employee Name = Kamal
    Employee Id = 4,Employee Name = Matin
    Employee Id = 5,Employee Name = Jatin
    Employee Id = 6,Employee Name = Nitin
    Employee Id = 7,Employee Name = Ela
    Employee Id = 8,Employee Name = Bela
    Employee Id = 9,Employee Name = Shila
    Employee Id = 10,Employee Name = Cris
    Employee Bela found
    
    In the above program the class Myiterator is input iterator class which allows reading the same element multiple times which is not not required for an input/output iterator. This capability is available due to the type of elements storage used in the container class which is not true for input stream. Now let us modify the above program and convert the iterator class to a just output iterator class. To do that two major modification needed: 1. Remove equality/inequality operations, 2. Change operator *() and add overloaded assignment = operator to accept a value whose type is same as the element type of the container. Here is the sample code:

    Example: Output Iterator

    Code:
    #include<iterator>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    //Iterator class for MyContainerClass class
    class Myiterator:public iterator<std::output_iterator_tag,Employee>
    {
        // Pointer to an element of the range of elements
        Employee *pEmp;
        //Constructor is kept private so that instance cannot be created by others except the MyContainerClass which is a friend
        Myiterator(Employee* p) :pEmp{ p }
        {
    
        }
    public:
        ~Myiterator(){}
        friend class MyContainerClass;
        // Copy Constructor is required for all iterators
        Myiterator(const Myiterator& itr)
        {
            pEmp = itr.pEmp;
    
        }
        //    Single pass dereference operator only for read operation of input iterator
        /*const Employee& operator *()
        {
            return *pEmp;
        }*/
        Myiterator& operator *()
        {
        //Moving the pointer to the next element
        return *this;
        }
        // Pre-increment operator required for all iterators    
        Myiterator operator ++()
        {
            ++pEmp;
            return *this;
        }
        // Post-increment operator required for all iterators
        Myiterator operator ++(int)
        {
            Myiterator itr = *this;
            ++pEmp;
            return itr;
        }
        // Inequality operation required for input iterator
        /*bool operator != (const Myiterator& it)
        {
            return (pEmp != it.pEmp);
    
        }
        // Equality operation required for input iterator
        bool operator == (const Myiterator& it)
        {
            return (pEmp == it.pEmp);
    
        }*/
        // Assignment operator required for all itertors
        Myiterator& operator = (const Myiterator& it)
        {
            if (&it !=this)
            {
                (pEmp = it.pEmp);
            }
            return *this;
    
        }
        Myiterator& operator =(const Employee& e)
        {
            *pEmp = e;
            return *this;
        }
    };
    
    int main()
    {
        MyContainerClass c;
        
        c.Addlast(Employee(1,L"Bimal") );
        c.Addlast(Employee(2, L"Amal"));
        c.Addlast(Employee(3, L"Kamal"));
        c.Addlast(Employee(4, L"Matin"));
        c.Addlast(Employee(5, L"Jatin"));
        c.Addlast(Employee(6, L"Nitin"));
        c.Addlast(Employee(7, L"Ela"));
        c.Addlast(Employee(8, L"Bela"));
        c.Addlast(Employee(9, L"Shila"));
        c.Addlast(Employee(10, L"Cris"));
    
        // Acquiring iterators
        auto begin = c.Begin();
        auto end = c.End();
        // Copy construction operation
        auto beginitr = begin;
        auto enditr = end;
    
        // Assignment operation
        beginitr = begin;
        enditr = end;
        
        //Default constructor
        //Myiterator enditr; // default constructor required only for forward operator
    
        // Write operation
        *begin = Employee(100, L" Shabbir Bhimani");
        ++begin;
        begin++;
        
    
        // Read operation not supported by just output iterator    
        /*Employee emp = *begin; // read the element
        wcout<<"The first element: " << emp<<endl;
    
        cout << "The elements are: " << endl;
        while(begin != end) // Inequiality comparison only for input operator
        {
            wcout << (*begin++); // Increment the iterator.
        }*/
        //Increament operation and read
        //wcout << "The first element is " << *(beginitr++);
        //wcout << "The 3rd element is " << *(++beginitr);
    
        //Decreament operation
        //wcout << "The last element is " << *(--enditr) << endl; // Allowed only for bidirectional iterator
        //wcout << "The end last element is " << *(enditr--) << endl; // Allowed only for bidirectional iterator
    
        
        // Comparision  operators 
        /*if (begin == end) //require only for input operators 
            cout << "End of range reached" << endl;*/
        /*if (begin < end) //Allowed only for random access iterator
            cout << "More elemets to traverse" << endl;
        if (end>begin) //Allowed only for random access iterator
            cout << "More elemets to traverse" << endl;
        if (begin <= end) //Allowed only for random access iterator
            cout << "More elemets may be there to traverse" << endl;
        if (end>=begin) //Allowed only for random access iterator
            cout << "More elemets may be there to traverse" << endl;
            
        // Accessing elements randomly
        //wcout<<endl << "The 5th element is " << *(beginitr + 4) << endl; //Allowed only for random access iterator
        //wcout << "The last 2nd element is " << *(enditr -2) << endl;//Allowed only for random access iterator
        //wcout << "The 6th element is " << beginitr[5] << endl; //Allowed only for random access iterator
        beginitr += 2;//Allowed only for random access iterator
        wcout << "The 3rd element is " << *beginitr << endl;
        
        enditr -= 3;//Allowed only for random access iterator
        wcout << "The last 3rd element is " << *enditr << endl;*/
    
        // Using std algorithm 
        cout <<endl<< "Applying algorithm: " << endl;
        //std::for_each(c.Begin(), c.End(), [](Employee e) {wcout << e;});
        //if(std::find(c.Begin(), c.End(), Employee(8, L"Bela"))!= c.End())
        //    cout << "Employee Bela found" << endl;
        std::fill_n(begin, 2, Employee(200, L"Jesmin"));
        c.ShowElements();
        
        return 0;
    }
    
    Code:
    Applying algorithm:
    Employee Id = 100,Employee Name =  Shabbir Bhimani
    Employee Id = 2,Employee Name = Amal
    Employee Id = 200,Employee Name = Jesmin
    Employee Id = 200,Employee Name = Jesmin
    Employee Id = 5,Employee Name = Jatin
    Employee Id = 6,Employee Name = Nitin
    Employee Id = 7,Employee Name = Ela
    Employee Id = 8,Employee Name = Bela
    Employee Id = 9,Employee Name = Shila
    Employee Id = 10,Employee Name = Cris
    

    Forward Iterator



    Forward iterator has the capability of both input and output iterators. We have to just modify dereference operator * to enable both read and write operation. Also added a default constructor in the public section. Standards says it is a requirement for forward iterator. Here is the modified code for forward iterator:

    Example: Forward Iterator

    Code:
    #include<iterator>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    //Iterator class for MyContainerClass class
    class Myiterator:public iterator<std::forward_iterator_tag,Employee>
    {
        // Pointer to an element of the range of elements
        Employee *pEmp;
        //Constructor is kept private so that instance cannot be created by others except the MyContainerClass which is a friend
        Myiterator(Employee* p) :pEmp{ p }
        {
    
        }
    public:
        Myiterator(){} // Default constructor required for forward iterator. Not sure about the usage
        ~Myiterator(){}
        friend class MyContainerClass;
        // Copy Constructor is required for all iterators
        Myiterator(const Myiterator& itr)
        {
            pEmp = itr.pEmp;
    
        }
        //    dereference operator for read and write operation 
        Employee& operator *()
        {
            return *pEmp;
        }
        // Pre-increment operator required for all iterators    
        Myiterator operator ++()
        {
            ++pEmp;
            return *this;
        }
        // Post-increment operator required for all iterators
        Myiterator operator ++(int)
        {
            Myiterator itr = *this;
            ++pEmp;
            return itr;
        }
        // Inequality operation required for input iterator
        bool operator != (const Myiterator& it)
        {
            return (pEmp != it.pEmp);
    
        }
        // Equality operation required for input iterator
        bool operator == (const Myiterator& it)
        {
            return (pEmp == it.pEmp);
    
        }
        // Assignment operator required for all itertors
        Myiterator& operator = (const Myiterator& it)
        {
            if (&it !=this)
            {
                (pEmp = it.pEmp);
            }
            return *this;
        }
    };
    
    int main()
    {
        MyContainerClass c;
        c.Addlast(Employee(1,L"Bimal") );
        c.Addlast(Employee(2, L"Amal"));
        c.Addlast(Employee(3, L"Kamal"));
        c.Addlast(Employee(4, L"Matin"));
        c.Addlast(Employee(5, L"Jatin"));
        c.Addlast(Employee(6, L"Nitin"));
        c.Addlast(Employee(7, L"Ela"));
        c.Addlast(Employee(8, L"Bela"));
        c.Addlast(Employee(9, L"Shila"));
        c.Addlast(Employee(10, L"Cris"));
    
        // Acquiring iterators
        auto begin = c.Begin();
        auto end = c.End();
        // Copy construction operation
        auto beginitr = begin;
        auto enditr = end;
    
        // Assignment operation
        beginitr = begin;
        enditr = end;
        
        //Default constructor
        Myiterator emtyitr; // default constructor required for forward operator
    
        // Read operation    
        Employee emp = *begin; // read the element
        wcout<<"The first element: " << emp<<endl;
    
        cout << "The elements are: " << endl;
        while(begin != end) // Inequiality comparison
        {
            wcout << (*begin++); // Increment the iterator.
        }
    
        // Write operation
        *begin = Employee(100, L" Shabbir Bhimani");
        ++begin;
        begin++;
        //Increament operation
        wcout << "The first element is " << *(beginitr++);
        wcout << "The 3rd element is " << *(++beginitr);
    
        //Decreament operation
        //wcout << "The last element is " << *(--enditr) << endl; // Allowed only for bidirectional iterator
        //wcout << "The end last element is " << *(enditr--) << endl; // Allowed only for bidirectional iterator
        
        // Comparision  operators
        if (begin == end)
            cout << "End of range reached" << endl;
        /*if (begin < end) //Allowed only for random access iterator
            cout << "More elemets to traverse" << endl;
        if (end>begin) //Allowed only for random access iterator
            cout << "More elemets to traverse" << endl;
        if (begin <= end) //Allowed only for random access iterator
            cout << "More elemets may be there to traverse" << endl;
        if (end>=begin) //Allowed only for random access iterator
            cout << "More elemets may be there to traverse" << endl;
            
        // Accessing elements randomly
        //wcout<<endl << "The 5th element is " << *(beginitr + 4) << endl; // //Allowed only for random access iterator
        //wcout << "The last 2nd element is " << *(enditr -2) << endl;// //Allowed only for random access iterator
        //wcout << "The 6th element is " << beginitr[5] << endl; // //Allowed only for random access iterator
        beginitr += 2;//Allowed only for random access iterator
        wcout << "The 3rd element is " << *beginitr << endl;
        
        enditr -= 3;//Allowed only for random access iterator
        wcout << "The last 3rd element is " << *enditr << endl;*/
    
        // Using std algorithm require input iterator
        cout <<endl<< "Applying algorithm: " << endl;
        std::for_each(c.Begin(), c.End(), [](Employee e) {wcout << e;});
        if(std::find(c.Begin(), c.End(), Employee(8, L"Bela"))!= c.End())
            cout << "Emplyee Bela found" << endl;
        // Algorithm need output iterator
        std::fill_n(c.Begin(), 2, Employee(200, L"Jesmin"));
    
        //Algorithm need forward iterator
        if (std::is_sorted(c.Begin(), c.End(), [](Employee& e1, Employee& e2) {return e1.EmpId < e2.EmpId;}))
            cout << "Elements are sorted" << endl;
        else
            cout << "Element are not sorted" << endl;
        c.ShowElements();
        
        return 0;
    }
    
    Code:
    The first element: Employee Id = 1,Employee Name = Bimal
    
    The elements are:
    Employee Id = 1,Employee Name = Bimal
    Employee Id = 2,Employee Name = Amal
    Employee Id = 3,Employee Name = Kamal
    Employee Id = 4,Employee Name = Matin
    Employee Id = 5,Employee Name = Jatin
    Employee Id = 6,Employee Name = Nitin
    Employee Id = 7,Employee Name = Ela
    Employee Id = 8,Employee Name = Bela
    Employee Id = 9,Employee Name = Shila
    Employee Id = 10,Employee Name = Cris
    The first element is Employee Id = 1,Employee Name = Bimal
    The 3rd element is Employee Id = 3,Employee Name = Kamal
    
    Applying algorithm:
    Employee Id = 1,Employee Name = Bimal
    Employee Id = 2,Employee Name = Amal
    Employee Id = 3,Employee Name = Kamal
    Employee Id = 4,Employee Name = Matin
    Employee Id = 5,Employee Name = Jatin
    Employee Id = 6,Employee Name = Nitin
    Employee Id = 7,Employee Name = Ela
    Employee Id = 8,Employee Name = Bela
    Employee Id = 9,Employee Name = Shila
    Employee Id = 10,Employee Name = Cris
    Emplyee Bela found
    Element are not sorted
    Employee Id = 200,Employee Name = Jesmin
    Employee Id = 200,Employee Name = Jesmin
    Employee Id = 3,Employee Name = Kamal
    Employee Id = 4,Employee Name = Matin
    Employee Id = 5,Employee Name = Jatin
    Employee Id = 6,Employee Name = Nitin
    Employee Id = 7,Employee Name = Ela
    Employee Id = 8,Employee Name = Bela
    Employee Id = 9,Employee Name = Shila
    Employee Id = 10,Employee Name = Cris
    
    Following STL method returns a forward iterator- std::forward_list::begin

    Bidirectional iterator



    Bidirectional iterator has all the capability and also it can be decremented. Adding the prefix and postfix decrement (–) operators to the forward iterator will make it bidirectional iterator:

    Example: Bidirectional Iterator

    Code:
    #include<iterator>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    //Iterator class for MyContainerClass class
    class Myiterator:public iterator<std::bidirectional_iterator_tag,Employee>
    {
        // Pointer to an element of the range of elements
        Employee *pEmp;
        //Constructor is kept private so that instance cannot be created by others except the MyContainerClass which is a friend
        Myiterator(Employee* p) :pEmp{ p }
        {
    
        }
    public:
        Myiterator(){} // Default constructor required for forward iterator. Not sure about the usage
        ~Myiterator(){}
        friend class MyContainerClass;
        // Copy Constructor is required for all iterators
        Myiterator(const Myiterator& itr)
        {
            pEmp = itr.pEmp;
        }
        //    dereference operator for read and write operation 
        Employee& operator *()
        {
            return *pEmp;
        }
        // Pre-increment operator required for all iterators    
        Myiterator operator ++()
        {
            ++pEmp;
            return *this;
        }
        // Post-increment operator required for all iterators
        Myiterator operator ++(int)
        {
            Myiterator itr = *this;
            ++pEmp;
            return itr;
        }
        // Pre-increment operator required for all iterators    
        Myiterator operator --()
        {
            --pEmp;
            return *this;
        }
        // Post-increment operator required for all iterators
        Myiterator operator --(int)
        {
            Myiterator itr = *this;
            pEmp;
            return itr;
        }
        // Inequality operation required for input iterator
        bool operator != (const Myiterator& it)
        {
            return (pEmp != it.pEmp);
    
        }
        // Equality operation required for input iterator
        bool operator == (const Myiterator& it)
        {
            return (pEmp == it.pEmp);
    
        }
        // Assignment operator required for all itertors
        Myiterator& operator = (const Myiterator& it)
        {
            if (&it !=this)
            {
                (pEmp = it.pEmp);
            }
            return *this;
        }
    };
    
    int main()
    {
        MyContainerClass c;
        c.Addlast(Employee(1,L"Bimal") );
        c.Addlast(Employee(2, L"Amal"));
        c.Addlast(Employee(3, L"Kamal"));
        c.Addlast(Employee(4, L"Matin"));
        c.Addlast(Employee(5, L"Jatin"));
        c.Addlast(Employee(6, L"Nitin"));
        c.Addlast(Employee(7, L"Ela"));
        c.Addlast(Employee(8, L"Bela"));
        c.Addlast(Employee(9, L"Shila"));
        c.Addlast(Employee(10, L"Cris"));
    
        // Acquiring iterators
        auto begin = c.Begin();
        auto end = c.End();
        // Copy construction operation
        auto beginitr = begin;
        auto enditr = end;
    
        // Assignment operation
        beginitr = begin;
        enditr = end;
        
        //Default constructor
        Myiterator emtyitr; // default constructor required for forward operator
    
        // Read operation    
        Employee emp = *begin; // read the element
        wcout<<"The first element: " << emp<<endl;
    
        cout << "The elements are: " << endl;
        while(begin != end) // Inequiality comparison
        {
            wcout << (*begin++); // Increment the iterator.
        }
    
        // Write operation
        *begin = Employee(100, L" Shabbir Bhimani");
        ++begin;
        begin++;
        //Increament operation
        wcout << "The first element is " << *(beginitr++);
        wcout << "The 3rd element is " << *(++beginitr);
    
        //Decreament operation
        wcout << "The last element is " << *(--enditr) << endl; // Allowed only for bidirectional iterator
        wcout << "The last element is " << *(enditr--) << endl; // Allowed only for bidirectional iterator
    
        
        // Comparision  operators
        if (begin == end)
            cout << "End of range reached" << endl;
        /*if (begin < end) //Allowed only for random access iterator
            cout << "More elemets to traverse" << endl;
        if (end>begin) //Allowed only for random access iterator
            cout << "More elemets to traverse" << endl;
        if (begin <= end) //Allowed only for random access iterator
            cout << "More elemets may be there to traverse" << endl;
        if (end>=begin) //Allowed only for random access iterator
            cout << "More elemets may be there to traverse" << endl;
            
        // Accessing elements randomly
        //wcout<<endl << "The 5th element is " << *(beginitr + 4) << endl; // //Allowed only for random access iterator
        //wcout << "The last 2nd element is " << *(enditr -2) << endl;////Allowed only for random access iterator
        //wcout << "The 6th element is " << beginitr[5] << endl; // //Allowed only for random access iterator
        beginitr += 2; //Allowed only for random access iterator
        wcout << "The 3rd element is " << *beginitr << endl;
        
        enditr -= 3;//Allowed only for random access iterator
        wcout << "The last 3rd element is " << *enditr << endl;*/
    
        // Using std algorithm require input iterator
        cout <<endl<< "Applying algorithm: " << endl;
        std::for_each(c.Begin(), c.End(), [](Employee e) {wcout << e;});
        if(std::find(c.Begin(), c.End(), Employee(8, L"Bela"))!= c.End())
            cout << "Emplyee Bela found" << endl;
        // Algorithm need output iterator
        std::fill_n(c.Begin(), 2, Employee(200, L"Jesmin"));
        //Algorithm need bidirectional iterator
        std::reverse(c.Begin(), c.End());
    
        //Algorithm need forward iterator
        if (std::is_sorted(c.Begin(), c.End(), [](Employee& e1, Employee& e2) {return e1.EmpId < e2.EmpId;}))
            cout << "Elements are sorted" << endl;
        else
            cout << "Element are not sorted" << endl;
        c.ShowElements();
        
        return 0;
    }
    
    Code:
    The first element: Employee Id = 1,Employee Name = Bimal
    
    The elements are:
    Employee Id = 1,Employee Name = Bimal
    Employee Id = 2,Employee Name = Amal
    Employee Id = 3,Employee Name = Kamal
    Employee Id = 4,Employee Name = Matin
    Employee Id = 5,Employee Name = Jatin
    Employee Id = 6,Employee Name = Nitin
    Employee Id = 7,Employee Name = Ela
    Employee Id = 8,Employee Name = Bela
    Employee Id = 9,Employee Name = Shila
    Employee Id = 10,Employee Name = Cris
    The first element is Employee Id = 1,Employee Name = Bimal
    The 3rd element is Employee Id = 3,Employee Name = Kamal
    The last element is Employee Id = 10,Employee Name = Cris
    
    The last element is Employee Id = 10,Employee Name = Cris
    
    
    Applying algorithm:
    Employee Id = 1,Employee Name = Bimal
    Employee Id = 2,Employee Name = Amal
    Employee Id = 3,Employee Name = Kamal
    Employee Id = 4,Employee Name = Matin
    Employee Id = 5,Employee Name = Jatin
    Employee Id = 6,Employee Name = Nitin
    Employee Id = 7,Employee Name = Ela
    Employee Id = 8,Employee Name = Bela
    Employee Id = 9,Employee Name = Shila
    Employee Id = 10,Employee Name = Cris
    Emplyee Bela found
    Element are not sorted
    Employee Id = 10,Employee Name = Cris
    Employee Id = 9,Employee Name = Shila
    Employee Id = 8,Employee Name = Bela
    Employee Id = 7,Employee Name = Ela
    Employee Id = 6,Employee Name = Nitin
    Employee Id = 5,Employee Name = Jatin
    Employee Id = 4,Employee Name = Matin
    Employee Id = 3,Employee Name = Kamal
    Employee Id = 200,Employee Name = Jesmin
    Employee Id = 200,Employee Name = Jesmin
    
    Following STL method returns a bidirectional iterator-std::list::begin

    Random Access Iterator



    Random access iterator has all the capabilities of other iterators and also support the comparison operators: <, >, <=, >= and arithmetic operators: +, -, +=, -= whose right hand operand is an integre and the subtraction operator (-) which right hand operators is the same iterator type. The subtracting two iterator of the same range gives the distance between the elements pointed by the iterators.

    Example: Random Access Iterator

    Code:
    #include<iterator>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    //Iterator class for MyContainerClass class
    class Myiterator :public iterator<std::random_access_iterator_tag, Employee>
    {
        // Pointer to an element of the range of elements
        Employee *pEmp;
        //Constructor is kept private so that instance cannot be created by others except the MyContainerClass which is a friend
        Myiterator(Employee* p) :pEmp{ p }
        {
    
        }
    public:
        Myiterator() {} // Default constructor required for forward iterator. Not sure about the usage
        ~Myiterator() {}
        friend class MyContainerClass;
        // Copy Constructor is required for all iterators
        Myiterator(const Myiterator& itr)
        {
            pEmp = itr.pEmp;
    
        }
        //    dereference operator for read and write operation 
        Employee& operator *()
        {
            return *pEmp;
        }
        // Pre-increment operator required for all iterators    
        Myiterator operator ++()
        {
            ++pEmp;
            return *this;
        }
        // Post-increment operator required for all iterators
        Myiterator operator ++(int)
        {
            Myiterator itr = *this;
            ++pEmp;
            return itr;
        }
        // Pre-increment operator required for all iterators    
        Myiterator operator --()
        {
            --pEmp;
            return *this;
        }
        // Post-increment operator required for all iterators
        Myiterator operator --(int)
        {
            Myiterator itr = *this;
            pEmp;
            return itr;
        }
        // Inequality operation required for input iterator
        bool operator != (const Myiterator& it)
        {
            return (pEmp != it.pEmp);
        }
        // Equality operation required for input iterator
        bool operator == (const Myiterator& it)
        {
            return (pEmp == it.pEmp);
        }
        // Required for random access iterator
        bool operator < (const Myiterator& it)
        {
            return (pEmp < it.pEmp);
        }
        // Required for random access iterator
        bool operator <= (const Myiterator& it)
        {
            return (pEmp <= it.pEmp);
        }
        // Required for random access iterator
        bool operator > (const Myiterator& it)
        {
            return (pEmp > it.pEmp);
        }
        // Required for random access iterator
        bool operator >= (const Myiterator& it)
        {
            return (pEmp >= it.pEmp);
        }
    
        // Assignment operator required for all itertors
        Myiterator& operator = (const Myiterator& it)
        {
            if (&it != this)
            {
                (pEmp = it.pEmp);
            }
            return *this;
        }
        // Only required for random access operator
        void operator +=(int n)
        {
            pEmp += n;
        }
        // Only required for random access operator
        void operator -=(int n)
        {
            pEmp -= n;
        }
        // Only required for random access operator
        Myiterator operator +(int i)
        {
            Myiterator theItr = *this;
            theItr.pEmp += i;
            return theItr;
        }
        // Only required for random access operator
        Myiterator operator -(int i)
        {
            Myiterator theItr = *this;
            theItr.pEmp -= i;
            return theItr;
        }
        //Difference operator only needed by random access operator
        Myiterator::difference_type operator -(Myiterator itr)
        {
            return pEmp - itr.pEmp;
        }
        // Only required for random access operator
        Employee operator[](int n)
        {
            return pEmp[n];
        }
    };
    
    int main()
    {
        MyContainerClass c;
        c.Addlast(Employee(1, L"Bimal"));
        c.Addlast(Employee(2, L"Amal"));
        c.Addlast(Employee(3, L"Kamal"));
        c.Addlast(Employee(4, L"Matin"));
        c.Addlast(Employee(5, L"Jatin"));
        c.Addlast(Employee(6, L"Nitin"));
        c.Addlast(Employee(7, L"Ela"));
        c.Addlast(Employee(8, L"Bela"));
        c.Addlast(Employee(9, L"Shila"));
        c.Addlast(Employee(10, L"Cris"));
    
        // Acquiring iterators
        auto begin = c.Begin();
        auto end = c.End();
        // Copy construction operation
        auto beginitr = begin;
        auto enditr = end;
    
        // Assignment operation
        beginitr = begin;
        enditr = end;
    
        //Default constructor
        Myiterator emtyitr; // default constructor required for forward operator
    
                            // Read operation    
        Employee emp = *begin; // read the element
        wcout << "The first element: " << emp << endl;
    
        cout << "The elements are: " << endl;
        while (begin != end) // Inequiality comparison
        {
            wcout << (*begin++); // Increment the iterator.
        }
    
        // Write operation
        *begin = Employee(100, L" Shabbir Bhimani");
    
        //Increament operation
        wcout << "The first element is " << *(beginitr++);
        wcout << "The 3rd element is " << *(++beginitr);
    
        //Decreament operation
        wcout << "The last element is " << *(--enditr) << endl; // Allowed only for bidirectional iterator
        wcout << "The last element is " << *(enditr--) << endl; // Allowed only for bidirectional iterator
    
    
                                                                // Comparision  operators
        if (begin == end)
            cout << "End of range reached" << endl;
        if (begin < end) //Allowed only for random access iterator
            cout << "More elemets to traverse" << endl;
        if (end>begin) //Allowed only for random access iterator
            cout << "More elemets to traverse" << endl;
        if (begin <= end) //Allowed only for random access iterator
            cout << "More elemets may be there to traverse" << endl;
        if (end >= begin) //Allowed only for random access iterator
            cout << "More elemets may be there to traverse" << endl;
    
        // Accessing elements randomly
        wcout << endl << "The 5th element is " << *(c.Begin() + 4) << endl; // //Allowed only for random access iterator
        wcout << "The last 2nd element is " << *(c.End() - 2) << endl;////Allowed only for random access iterator
        wcout << "The 6th element is " << c.Begin()[5] << endl; // //Allowed only for random access iterator
        beginitr = c.Begin();
        enditr = c.End();
        beginitr += 2; //Allowed only for random access iterator
        wcout << "The 3rd element is " << *beginitr << endl;
    
        enditr -= 3;//Allowed only for random access iterator
        wcout << "The last 3rd element is " << *enditr << endl;
    
        // Using std algorithm require input iterator
        cout << endl << "Applying algorithm: " << endl;
        std::for_each(c.Begin(), c.End(), [](Employee e) {wcout << e;});
        if (std::find(c.Begin(), c.End(), Employee(8, L"Bela")) != c.End())
            cout << "Emplyee Bela found" << endl;
        // Algorithm need output iterator
        std::fill_n(c.Begin(), 2, Employee(200, L"Jesmin"));
        //Algorithm need bidirectional iterator
        std::reverse(c.Begin(), c.End());
        begin = c.Begin();
        end = c.End();
        std::sort(begin, end);
        //Algorithm need forward iterator
        if (std::is_sorted(c.Begin(), c.End(), [](Employee& e1, Employee& e2) {return e1.EmpId < e2.EmpId;}))
            cout << "Elements are sorted" << endl;
        else
            cout << "Element are not sorted" << endl;
        c.ShowElements();
    
        return 0;
    }
    
    Code:
    The first element: Employee Id = 1,Employee Name = Bimal
    
    The elements are:
    Employee Id = 1,Employee Name = Bimal
    Employee Id = 2,Employee Name = Amal
    Employee Id = 3,Employee Name = Kamal
    Employee Id = 4,Employee Name = Matin
    Employee Id = 5,Employee Name = Jatin
    Employee Id = 6,Employee Name = Nitin
    Employee Id = 7,Employee Name = Ela
    Employee Id = 8,Employee Name = Bela
    Employee Id = 9,Employee Name = Shila
    Employee Id = 10,Employee Name = Cris
    The first element is Employee Id = 1,Employee Name = Bimal
    The 3rd element is Employee Id = 3,Employee Name = Kamal
    The last element is Employee Id = 10,Employee Name = Cris
    
    The last element is Employee Id = 10,Employee Name = Cris
    
    End of range reached
    More elemets may be there to traverse
    More elemets may be there to traverse
    
    The 5th element is Employee Id = 5,Employee Name = Jatin
    
    The last 2nd element is Employee Id = 9,Employee Name = Shila
    
    The 6th element is Employee Id = 6,Employee Name = Nitin
    
    The 3rd element is Employee Id = 3,Employee Name = Kamal
    
    The last 3rd element is Employee Id = 8,Employee Name = Bela
    
    Applying algorithm:
    Employee Id = 1,Employee Name = Bimal
    Employee Id = 2,Employee Name = Amal
    Employee Id = 3,Employee Name = Kamal
    Employee Id = 4,Employee Name = Matin
    Employee Id = 5,Employee Name = Jatin
    Employee Id = 6,Employee Name = Nitin
    Employee Id = 7,Employee Name = Ela
    Employee Id = 8,Employee Name = Bela
    Employee Id = 9,Employee Name = Shila
    Employee Id = 10,Employee Name = Cris
    Emplyee Bela found
    Elements are sorted
    Employee Id = 3,Employee Name = Kamal
    Employee Id = 4,Employee Name = Matin
    Employee Id = 5,Employee Name = Jatin
    Employee Id = 6,Employee Name = Nitin
    Employee Id = 7,Employee Name = Ela
    Employee Id = 8,Employee Name = Bela
    Employee Id = 9,Employee Name = Shila
    Employee Id = 10,Employee Name = Cris
    Employee Id = 200,Employee Name = Jesmin
    Employee Id = 200,Employee Name = Jesmin
    
    Following STL method returns a random access iterator - std::array::begin()

    Iterators are mainly used by algorithms which makes the algorithms independent of the type of elements and arrangement of elements. STL algorithms work on iterators and independent of the containers which manage collections. So if you want your container class to be used by STL algorithms you should implement the iterators for them following the iterator concept in STL. If you want your algorithms to work with STL containers your algorithms should work on iterators supported by STL iterator concept.
     
    Last edited by a moderator: Jan 21, 2017

Share This Page