Iterators set as functor
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 10 of 10

Thread: Iterators set as functor

  1. #1
    Join Date
    May 2009
    Location
    Cantý, Italy
    Posts
    13

    Iterators set as functor

    Hello everybody, thanks in advance for your precious help.

    I'm defining a dynamic vector class from scratch (I have to, it's an assignment) and I am requested to define two distinct sets of iterators to walk through the vector (one normal "as inserted", the other sorted): which one to be used is decided once for all as the vector is created.

    I'm wondering how should I declare the iterators and how can I tell my Vector class to use one of them.. there's a little hint which tells that I'm supposed to use a "functor", but didn't really understand how it works.

    I'm only guessing my class should look like this:
    template <class T, class I> class Vector
    where T is the data type of vector's elements and I refers to the Iterator functor..

    Thank you!

  2. #2
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,725

    Re: Iterators set as functor

    Your iterator classes will need to be initialised with the location of the Vector's data array if the sorted iterator is to work.

    If you are after some sort of STL compatability then the iterators should overload the ++ and * operators and ideally be derived from one of the STL iterator tags.

    Code:
    template <typename T>
    class Iterator : public std::iterator<std::forward_iterator_tag, T>
    {
    };
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  3. #3
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,016

    Re: Iterators set as functor

    The question is: at what point do you have to decide on the type of iterator to use? At compile time or at run time? For each instance individually or once for all instances?

    What you propose means that the decision is made at compile time for each instance individually. That doesn't seem to rhyme with "once" in:
    Quote Originally Posted by diofanto View Post
    which one to be used is decided once for all as the vector is created.
    But then again, "as the vector is created" also doesn't rhyme with "once", so you'll have to be clearer on this.
    Last edited by D_Drmmr; May 11th, 2009 at 10:40 AM.
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  4. #4
    Join Date
    May 2009
    Location
    Cantý, Italy
    Posts
    13

    Re: Iterators set as functor

    Thank you guys, I'm trying to put all pieces together.. I'll be more collaborative as soon as I have clearer ideas... In the meantime any suggestion is appreciated!

    The requests of my assignment are:
    "
    It must be possible to access Vector's elements in two ways:
    - by (random) iterators which return the elements in the same order they were inserted
    - by (random) iterators which return the elements sorted in some way: this order must be set by the user by means of a functor and cannot be modified once a Vector object has been instantiated.
    Choose appropriately the way in which datas are accessed (r/w) for the two sets of iterators..
    ...
    Fundamental requirement: constant time access for the elements of Vector.
    ...
    Do not use data structures within the iterator that duplicates datas already existing in the Vector
    "

  5. #5
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,725

    Re: Iterators set as functor

    Quote Originally Posted by diofanto View Post
    Do not use data structures within the iterator that duplicates datas already existing in the Vector
    "
    I wonder if that includes something like an internal array of pointers to the data, sorted by what they reference?
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  6. #6
    Join Date
    Aug 2002
    Location
    Madrid
    Posts
    4,588

    Re: Iterators set as functor

    You could include that in the vector itself, so technically you would be all right since the sentence says "Do not use data structures within the iterator" ;-)
    In any case, there is no way to do it other than creating another O(N) data structure if you want to be able to access in a sorted and non-sorted way on the same vector object.
    Get this small utility to do basic syntax highlighting in vBulletin forums (like Codeguru) easily.
    Supports C++ and VB out of the box, but can be configured for other languages.

  7. #7
    Join Date
    May 2009
    Location
    Cantý, Italy
    Posts
    13

    Re: Iterators set as functor

    Yes, I think you both John and Yves are right, the only solution I can see is to create an array of sorted pointers that point to the vector elements (actually no duplication occurs)... Well, another solution could be to sort elements while they are inserted into the vector, because I don't really care about their position inside the vector since they are accessed with iterator and (forgot to mention) insertion is required only by appending (and I can do this with iterators) and not by index... but I will clarify this point with my tutor.
    Anyway, at the moment my biggest concern is how to tell Vector "use PlainIterator or use SortedIterator"...

  8. #8
    Join Date
    Aug 2002
    Location
    Madrid
    Posts
    4,588

    Re: Iterators set as functor

    The vector doesn't need to know about the iterator. Just make different functions for begin() and end() that return the different iterators. They then hold a state (e.g. a pointer to the vector's data and the sorted index index) and access the container through that.
    Get this small utility to do basic syntax highlighting in vBulletin forums (like Codeguru) easily.
    Supports C++ and VB out of the box, but can be configured for other languages.

  9. #9
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,725

    Re: Iterators set as functor

    Quote Originally Posted by diofanto View Post
    Anyway, at the moment my biggest concern is how to tell Vector "use PlainIterator or use SortedIterator"...
    You could always derive your iterators from a base class that contains a pointer to the data and a pointer to the pointers to data. The overloaded ++ and * operators in the derived classes would use the pointer appropriate to them. Or use 'duck typing' where the Vector template assumes that the iterator template parameter contains these elements. The 'begin()' and 'end()' functions then return an iterator based on the template parameter.

    Code:
    template <typename TData, typename TIterator>
    class Vector
    {
    public:
        TIterator begin()
        {
            return TIterator(pdata, ppdata);
        }
    
        TIterator end()
        {
            return TIterator(pdata + size, ppdata + size);
        }
    
    private:
        size_t size;
        TData *pdata;     // The data.
        TData **ppdata; // Sorted pointers to the data.
    };
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  10. #10
    Join Date
    May 2009
    Location
    Cantý, Italy
    Posts
    13

    Re: Iterators set as functor

    Quote Originally Posted by JohnW@Wessex View Post
    You could always derive your iterators from a base class that contains a pointer to the data and a pointer to the pointers to data. The overloaded ++ and * operators in the derived classes would use the pointer appropriate to them. Or use 'duck typing' where the Vector template assumes that the iterator template parameter contains these elements. The 'begin()' and 'end()' functions then return an iterator based on the template parameter.

    Code:
    template <typename TData, typename TIterator>
    class Vector
    {
    public:
        TIterator begin()
        {
            return TIterator(pdata, ppdata);
        }
    
        TIterator end()
        {
            return TIterator(pdata + size, ppdata + size);
        }
    
    private:
        size_t size;
        TData *pdata;     // The data.
        TData **ppdata; // Sorted pointers to the data.
    };
    That's fantastic

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 is a CodeGuru survey question.


Featured


HTML5 Development Center