How iterators are useful
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 11 of 11

Thread: How iterators are useful

  1. #1
    Join Date
    Jun 2015
    Posts
    140

    How iterators are useful

    Hello all,

    I finished chapter 20 of the book "Programming Principle and Practice using C++". There is a postscript at the end of this chapter:

    "If we have N kinds of containers of data and M things wed like to do with them, we can easily end up writing N*M pieces of
    code. If the data is of K different types, we could even end up with N*M*K pieces of code. The STL addresses this
    proliferation by having the element type as a parameter (taking care of the K factor) and by separating access to data from
    algorithms. By using iterators to access data in any kind of container from any algorithm, we can make do with N+M
    algorithms. This is a huge simplification. For example, if we have 12 containers and 60 algorithms, the brute-force approach
    would require 720 functions, whereas the STL strategy requires only 60 functions and 12 definitions of iterators: we just saved
    ourselves 90% of the work. In fact, this underestimates the saved effort because many algorithms take two pairs of iterators and
    the pairs need not be of the same type (e.g., see exercise 6). In addition, the STL provides conventions for defining algorithms
    that simplify writing correct code and composable code, so the saving is greater still.
    "

    Although I've done the exercises of the chapter and worked with iterators much, I don't understand the advantages of above all.
    Would you please offer an example showing the benefits of using iterators as the postscript says?

  2. #2
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,783

    Re: How iterators are useful

    Look at the STL functions described here http://www.cplusplus.com/reference/algorithm/

    These take iterators as parameters. This is what makes them so flexible and powerful. If the underlying data structure provides the required iterators, then these functions can be used. So if you code a new structure and provide the iterators for it, then these STL functions will work and can be used for the new structure without the functions knowing anything about this structure.

    Also, if you want to write a new function that works with data structures then if you write it to use iterators then the function will work with any structure that provides the required iterators - the function doesn't need to know anything else about the structure. As the book states, this is very powerful and very flexible.
    Last edited by 2kaud; October 11th, 2017 at 04:30 AM.
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C++17 Compiler: Microsoft VS2017 (15.4.0)

  3. #3
    Join Date
    Feb 2017
    Posts
    157

    Re: How iterators are useful

    Quote Originally Posted by tomy12 View Post
    the benefits of using iterators as the postscript says?
    The postscript you refer to describes the benefits of a general language feature called polymorphism. Lets say you have a bunch of containers that are all sequentially iterable. In the object oriented (OO) approach one would express this by letting them inherit and implement an Iterable interface. Then if a piece of code uses the Iterable type it will work when supplied with any container that implements the Iterable interface. That's polymorphism in action.

    The STL library is not OO for historical reasons so the STL containers are not related by shared interfaces. Still relationships can be formed by letting the containers share function names. Instead of an Iterable interface containers may express the fact that they are sequentially iterable by sharing the two functions begin() and end(). These return a start iterator and a stop iterator respectively which can be used to facilitate iteration through a range. Then if a piece of code is written that uses begin() and end() it will work when supplied with any container sporting a begin() function and an end() function (returning iterators capable of sequential iteration).

    So one use of iterators in STL is to provide the benefits of polymorphism for containers but without OO. Rather than expressing a type relationship by sharing a common interface like in OO, the STL containers express a functional relationship by sharing common functions. This kind of polymorphism is called ad-hoc polymorphism and is central to all of STL really.
    Last edited by wolle; October 12th, 2017 at 06:36 AM.

  4. #4
    Join Date
    Jun 2015
    Posts
    140

    Re: How iterators are useful

    Quote Originally Posted by 2kaud View Post
    Look at the STL functions described here http://www.cplusplus.com/reference/algorithm/

    These take iterators as parameters. This is what makes them so flexible and powerful. If the underlying data structure provides the required iterators, then these functions can be used. So if you code a new structure and provide the iterators for it, then these STL functions will work and can be used for the new structure without the functions knowing anything about this structure.
    Well I think iterators work well because they also gain the advantages of templates. Do you by "if you code a new structure" mean another container, because iterators should iterate over some container?

    And "provide the iterators for it": Does it mean simply creating a class that comprises that new container and provide functions: begin, end, arithmetic and so on, constructors that send pointers and we can use those pointers as iterators?
    I need the subject in its most basic level to figure it out completely.


    Also, if you want to write a new function that works with data structures then if you write it to use iterators then the function will work with any structure that provides the required iterators - the function doesn't need to know anything else about the structure. As the book states, this is very powerful and very flexible.
    It sounds that iterators work as template parameters that needn't know about the (pointer) type that will be sent to them.
    For example:

    Code:
    template <class T> 
    T largest(std::iterator s, std::iterator e)
    {
       T temp = T();
     for(auto it = s; it != e; ++it)
        if( *it > temp)
         temp = *t
     return temp;
    }
    Did you mean something like that for the latter part of our discussion?

  5. #5
    Join Date
    Jun 2015
    Posts
    140

    Re: How iterators are useful

    Quote Originally Posted by wolle View Post
    The STL library is not OO for historical reasons so the STL containers are not related by shared interfaces.
    So that's why we can't assign an iterator of, E.g., std::vector to that of std::list. It's on the contrary to what I though I'd gotten from the subject and to the snip code I offered.
    Still relationships can be formed by letting the containers share function names. Instead of an Iterable interface containers may express the fact that they are sequentially iterable by sharing the two functions begin() and end(). These return a start iterator and a stop iterator respectively which can be used to facilitate iteration through a range. Then if a piece of code is written that uses begin() and end() it will work when supplied with any container sporting a begin() function and an end() function (returning iterators capable of sequential iteration).
    So the snip code might not be that wrong.

    So one use of iterators in STL is to provide the benefits of polymorphism for containers but without OO. Rather than expressing a type relationship by sharing a common interface like in OO, the STL containers express a functional relationship by sharing common functions. This kind of polymorphism is called ad-hoc polymorphism and is central to all of STL really.
    I've read about polymorphism in books IIRC. It talks about functions having different type/order/number of arguments I think.
    Last edited by tomy12; October 13th, 2017 at 02:14 PM.

  6. #6
    Join Date
    Jun 2015
    Posts
    140

    Re: How iterators are useful

    If there is an example that demonstrates what the postscript explained, it will be easily understood.

  7. #7
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,783

    Re: How iterators are useful

    Quote Originally Posted by tomy12 View Post
    Well I think iterators work well because they also gain the advantages of templates. Do you by "if you code a new structure" mean another container, because iterators should iterate over some container?

    And "provide the iterators for it": Does it mean simply creating a class that comprises that new container and provide functions: begin, end, arithmetic and so on, constructors that send pointers and we can use those pointers as iterators?
    I need the subject in its most basic level to figure it out completely.




    It sounds that iterators work as template parameters that needn't know about the (pointer) type that will be sent to them.
    For example:

    Code:
    template <class T> 
    T largest(std::iterator s, std::iterator e)
    {
       T temp = T();
     for(auto it = s; it != e; ++it)
        if( *it > temp)
         temp = *t
     return temp;
    }
    Did you mean something like that for the latter part of our discussion?
    More like

    Code:
    template <typename I>
    I max_element (I s, I e )
    {
        I temp = s;
    
        for (; s != e; ++s)
            if (*s > *temp)
                temp = s;
    
        return temp;
    }
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C++17 Compiler: Microsoft VS2017 (15.4.0)

  8. #8
    Join Date
    Jun 2015
    Posts
    140

    Re: How iterators are useful

    Thank you. I used this:

    Code:
    #include <std_lib_facilities_4.h>
    using namespace std;
    
    template <typename T>
    T max_elem(T first, T end)
    {
    	T temp = first;
    	for (; first != end; ++first)
    		if (*first > *temp)
    			temp = first;
    			return temp;
    }
    
    int main()
    {
    	vector<int> vi{ 3, 5, 7, 4 };
    	vector<double> vd{ 5.8, 4.5, 9.9, 9.8 };
    	list<string> ls{ "AB", "CD", "EF", "AD" };
    
    	cout << *max_elem(vi.begin(), vi.end()) << endl;
    	cout << *max_elem(vd.begin(), vd.end()) << endl;
    	cout << *max_elem(ls.begin(), ls.end()) << endl;
    
    	system("pause");
    	return 0;
    }
    and it correctly showed the max element for each one. So using iterators we needn't write a given function for each container again, but we can this way take advantages of iterators and use the given function for any container. I got this case.
    But apart from that, have iterators any other advantage (especially if it's stated in the postscript)?

    If so, I would be thankful if your explain that and then use a example for it.

  9. #9
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,783

    Re: How iterators are useful

    In addition, the STL provides conventions for defining algorithms
    that simplify writing correct code and composable code, so the saving is greater still
    I think you are referring to this?

    This is just a more generalisation of the first. So if you want to sort or search or merge or find or... then the c++ code more closely reflects the algorithm being used.
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C++17 Compiler: Microsoft VS2017 (15.4.0)

  10. #10
    Join Date
    Jun 2015
    Posts
    140

    Re: How iterators are useful

    Thank you for your answer.

    So to summarise, we can say that the whole power of iterators can be practically summarised to that simple code. I,e. it shows the whole case. Yes?

    If so and you agree, so the power of iterators belongs completely to the pointers containers have declared as iterators to be used, "and" use of generic programming (template). Yes, again?

  11. #11
    Join Date
    Oct 2008
    Posts
    1,452

    Re: How iterators are useful

    Quote Originally Posted by tomy12 View Post
    so the power of iterators belongs completely to the pointers containers have declared as iterators to be used, "and" use of generic programming (template). Yes, again?
    iterators need not to be pointers, nor to belong to some container. An iterator is just something that can be traversed and dereferenced ( how and when depending on its iterator category ).
    For example, you could write an iterator representing pis digits, or a source of pseudo random numbers, or , clearly no such container could exist.

    Moreover, generic algorithms working on iterators are useful not just because they are polymorphic, but also because such polymorphism is resolved at compile time. This increases both type safety and optimization opportunities. It also allows iterators to be efficiently composed, in order to create new iterators from existing one or to use them as building blocks of higher abstractions ( eg. ranges ).

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This a Codeguru.com survey!


On-Demand Webinars (sponsored)