custom iterator

Discussion in 'C++' started by Grahamo@nospam.com, Sep 12, 2005.

  1. Guest

    Hi,

    I'm implementing a custom iterator (random access type ) so I can use
    stl algorithms such as sort on my legacy containers. I'm having
    problems compiling however. when implementing my customIterator class I
    have defined the operators below (as well as others but they're not
    important right now, I don't think).

    class customIterator
    {

    customerIterator& operator*() const;
    int operator-(const customIterator& x);
    int operator-(const contIter& rhs) const
    customIterator& operator++();
    customIterator operator++(int);
    customIterator& operator--();
    customIterator operator--(int);
    customIterator& operator+=(difference_type n);
    customIterator& operator-=(difference_type n);
    customIterator operator+(difference_type rhs) const;
    customIterator operator-(difference_type rhs) const;
    int& operator[](int n);
    bool operator==(const customIterator& x) const;
    bool operator<(const customIterator& x) const;

    }


    The problem is when I come to pass one of these iterators into
    std::sort, I'm missing all sorts of operators like operator>(int),
    operator/(int), operator-(int).

    These are being generated because the stl::sort on my platform has code
    like this;

    while (__last - __first > __stl_threshold) {

    or uses expressions like;

    if ( (__last - __first)/2 > something... )





    Do I need to provide an operator for implicit conversion of my
    customIterator to an int so that the comparison ( __last - first >
    __stl_threshold) can be evaluated?

    Right now I'm just trying to get this to compile with a simple case
    vectors of ints.


    std::vector<int> vint;

    containerWrapper wrapper(vint);
    customIterator begin = wrapper.begin();
    customIterator end = wrapper.end();


    // compilation errors here .......
    std::sort(begin, end, aCompareFunction());

    compilation errors are like;

    1) operator> not implemented in the type customIterator for arguments
    of type int

    2) operator== not implemented in the type customIterator for arguments
    of type int

    3) operator/ not implemented in the type customIterator for arguments
    of type int


    etc. etc.

    any ideas?

    thanks.
     
    , Sep 12, 2005
    #1
    1. Advertising

  2. "" <> schrieb im Newsbeitrag
    news:...
    [...]
    > class customIterator
    > {

    [...]
    > }

    [...]
    > // compilation errors here .......
    > std::sort(begin, end, aCompareFunction());
    > compilation errors are like;
    > 1) operator> not implemented in the type customIterator for arguments
    > of type int
    > 2) operator== not implemented in the type customIterator for arguments
    > of type int
    > 3) operator/ not implemented in the type customIterator for arguments
    > of type int


    you can define the missed operators globally, ie

    bool operator>(const customIterator&i1, const customIterator&i2) { return
    DistanceOf(i1, i2) > 0; }
    bool operator==(const customIterator&i1, const customIterator&i2) { return
    DistanceOf(i1, i2) == 0; }
    ....
    int DistanceOf(const customIterator&i1, const customIterator&i2)
    {
    // calculate the distance of your iterators, which may depend on the inner
    definition of the iterator
    }

    Hope this helps. Any questions?

    // oliver
     
    Oliver \(Nospam\), Sep 12, 2005
    #2
    1. Advertising

  3. * :

    > I'm implementing a custom iterator (random access type ) so I can use
    > stl algorithms such as sort on my legacy containers. I'm having
    > problems compiling however. when implementing my customIterator class I
    > have defined the operators below (as well as others but they're not
    > important right now, I don't think).
    >
    > class customIterator
    > {
    >
    > customerIterator& operator*() const;
    > int operator-(const customIterator& x);
    > int operator-(const contIter& rhs) const
    > customIterator& operator++();
    > customIterator operator++(int);
    > customIterator& operator--();
    > customIterator operator--(int);
    > customIterator& operator+=(difference_type n);
    > customIterator& operator-=(difference_type n);
    > customIterator operator+(difference_type rhs) const;
    > customIterator operator-(difference_type rhs) const;
    > int& operator[](int n);
    > bool operator==(const customIterator& x) const;
    > bool operator<(const customIterator& x) const;
    >
    > }
    >
    >
    > The problem is when I come to pass one of these iterators into
    > std::sort, I'm missing all sorts of operators like operator>(int),
    > operator/(int), operator-(int).
    >
    > These are being generated because the stl::sort on my platform has code
    > like this;
    >
    > while (__last - __first > __stl_threshold) {
    >
    > or uses expressions like;
    >
    > if ( (__last - __first)/2 > something... )


    The requirements on a random access iterator are, roughly, that it behaves
    like a pointer.

    That includes comparision and subtraction, but not division.


    > Do I need to provide an operator for implicit conversion of my
    > customIterator to an int so that the comparison ( __last - first >
    > __stl_threshold) can be evaluated?


    No, you need to define

    std::ptr_diff operator-( MyIter const& a, MyIter const& b )


    > Right now I'm just trying to get this to compile with a simple case
    > vectors of ints.
    >
    >
    > std::vector<int> vint;
    >
    > containerWrapper wrapper(vint);
    > customIterator begin = wrapper.begin();
    > customIterator end = wrapper.end();
    >
    >
    > // compilation errors here .......
    > std::sort(begin, end, aCompareFunction());
    >
    > compilation errors are like;
    >
    > 1) operator> not implemented in the type customIterator for arguments
    > of type int
    >
    > 2) operator== not implemented in the type customIterator for arguments
    > of type int
    >
    > 3) operator/ not implemented in the type customIterator for arguments
    > of type int


    I rather doubt your point (3).

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Alf P. Steinbach, Sep 12, 2005
    #3
  4. Mike Wahler Guest

    "Alf P. Steinbach" <> wrote in message
    news:...
    >* :
    >
    >> I'm implementing a custom iterator (random access type ) so I can use
    >> stl algorithms such as sort on my legacy containers. I'm having
    >> problems compiling however. when implementing my customIterator class I
    >> have defined the operators below (as well as others but they're not
    >> important right now, I don't think).


    [snip]
    >
    >> Do I need to provide an operator for implicit conversion of my
    >> customIterator to an int so that the comparison ( __last - first >
    >> __stl_threshold) can be evaluated?

    >
    > No, you need to define
    >
    > std::ptr_diff operator-( MyIter const& a, MyIter const& b )


    Did I read that right? Define something in namespace 'std'?
    Is that allowed by the standard?

    -Mike
     
    Mike Wahler, Sep 12, 2005
    #4
  5. Mike Wahler wrote:

    > "Alf P. Steinbach" <> wrote in message
    >> > No, you need to define

    > >
    > > std::ptr_diff operator-( MyIter const& a, MyIter const& b )

    >
    > Did I read that right? Define something in namespace 'std'?
    > Is that allowed by the standard?


    I don't think he was suggesting defining something in namespace std
    (although I believe even that is allowed in limited circumstances
    relating to specializing templates already in namespace std). He's
    just suggesting defining a function that returns a std::ptr_diff.
    Would you be complaining if his function returned a std::size_t?

    Best regards,

    Tom
     
    Thomas Tutone, Sep 12, 2005
    #5
  6. wrote:
    > Hi,
    >
    > I'm implementing a custom iterator (random access type ) so I can use
    > stl algorithms such as sort on my legacy containers. I'm having
    > problems compiling however. when implementing my customIterator class I
    > have defined the operators below (as well as others but they're not
    > important right now, I don't think).
    >
    > class customIterator
    > {
    >
    > customerIterator& operator*() const;
    > int operator-(const customIterator& x);
    > int operator-(const contIter& rhs) const
    > customIterator& operator++();
    > customIterator operator++(int);
    > customIterator& operator--();
    > customIterator operator--(int);
    > customIterator& operator+=(difference_type n);
    > customIterator& operator-=(difference_type n);
    > customIterator operator+(difference_type rhs) const;
    > customIterator operator-(difference_type rhs) const;
    > int& operator[](int n);
    > bool operator==(const customIterator& x) const;
    > bool operator<(const customIterator& x) const;
    >
    > }
    >
    >
    > The problem is when I come to pass one of these iterators into
    > std::sort, I'm missing all sorts of operators like operator>(int),
    > operator/(int), operator-(int).
    >
    > These are being generated because the stl::sort on my platform has code
    > like this;
    >
    > while (__last - __first > __stl_threshold) {
    >
    > or uses expressions like;
    >
    > if ( (__last - __first)/2 > something... )
    >
    >
    >
    >
    >
    > Do I need to provide an operator for implicit conversion of my
    > customIterator to an int so that the comparison ( __last - first >
    > __stl_threshold) can be evaluated?


    When you subtract one iterator from another the result is an integer.
    The > and the / above are integer operations because __last - __first is
    an integer.

    The question is why this isn't working when you seem to have declared
    the correct operator- in the code above

    > int operator-(const customIterator& x);
    > int operator-(const contIter& rhs) const


    Or maybe you haven't, what is contIter, and why did you feel the need to
    provide a const and non-const version of operator- ?

    Anyway that is the area where the problem lies.

    john
     
    John Harrison, Sep 12, 2005
    #6
  7. Guest

    thanks for the replies, they were all helpful.

    I've a question about iterator behaviour. if I have

    difference_type res = iter1 - iter2

    the SGI website says that the precondition is that iter1 is "reachable
    from iter2 or vice-versa, or both".
    that includes past-the-end iterators too, doesn't it, for either iter1
    or iter2. I mean if there are 10 iterms in a vector and I have iter1
    and iter2 such that iter1 points to vector[3] and iter2 points to
    past-the-end , then iter2-iter1 is still valid, isn't it? it's going to
    return an iterator thats pointing to element[7] in the vector. yes?

    I'm just trying to get the logic for all the right so that my iterator
    respects all their behavioural requirements. I'm using the SGI website
    for the moment as a reference, if there's any other suggested sites
    that cover iterators in this context, then I'll definitely check it
    out.

    have a nice day

    GrahamO
     
    , Sep 13, 2005
    #7
  8. On 2005-09-13 04:42:05 -0400, ""
    <> said:

    > thanks for the replies, they were all helpful.
    >
    > I've a question about iterator behaviour. if I have
    >
    > difference_type res = iter1 - iter2
    >
    > the SGI website says that the precondition is that iter1 is "reachable
    > from iter2 or vice-versa, or both".
    > that includes past-the-end iterators too, doesn't it, for either iter1
    > or iter2. I mean if there are 10 iterms in a vector and I have iter1
    > and iter2 such that iter1 points to vector[3] and iter2 points to
    > past-the-end , then iter2-iter1 is still valid, isn't it?


    Yes, so far.

    > it's going to return an iterator thats pointing to element[7] in the
    > vector. yes?


    No, it will not return an iterator at all, it will return the value 7.

    Remember that arithmetic on random access iterators (i.e. the kind of
    iterator that std::vector has) works in essentially the same fashion as
    arithmetic on pointers.


    --
    Clark S. Cox, III
     
    Clark S. Cox III, Sep 13, 2005
    #8
  9. Mike Wahler Guest

    "Thomas Tutone" <> wrote in message
    news:...
    > Mike Wahler wrote:
    >
    >> "Alf P. Steinbach" <> wrote in message
    >>> > No, you need to define
    >> >
    >> > std::ptr_diff operator-( MyIter const& a, MyIter const& b )

    >>
    >> Did I read that right? Define something in namespace 'std'?
    >> Is that allowed by the standard?

    >
    > I don't think he was suggesting defining something in namespace std
    > (although I believe even that is allowed in limited circumstances
    > relating to specializing templates already in namespace std). He's
    > just suggesting defining a function that returns a std::ptr_diff.


    Yes you're right, somehow I interpreted that code incorrectly.
    But I believe the type is 'std::ptrdiff_t'

    > Would you be complaining if his function returned a std::size_t?


    Um, if I haven't had my coffee yet. :)

    -Mike
     
    Mike Wahler, Sep 13, 2005
    #9
  10. Guest

    one other thing... I have the iterators setup and I can now perform
    things like;

    myIter i1 = wrapper.begin();
    myIter i2 = wrapper.end();

    std::swap(i1, i2 );

    I can also call std::sort(i1 , i2);

    the above swap works fine and when I output the container contents, its
    contents are correctly ordered.

    however if I try to do something like;;

    std::sort(i1, i2 -1 );

    the (borland) compiler complains that;

    [C++ Error] iterator.cpp(285): E2285 Could not find a match for
    'swap<_Tp,_Alloc>(myIter,myIter)'

    I have defined operator- as

    // difference
    int operator-(const contIter& rhs) const
    {
    return abs(m_index - rhs.m_index);
    }

    contIter operator-(int i) const
    {
    return contIter(m_container, m_index-i);
    }




    I\m obviously missing something but can't see what. any ideas?


    thanks much again

    GrahamO
     
    , Sep 13, 2005
    #10
  11. * Mike Wahler:
    > But I believe the type is 'std::ptrdiff_t'


    Typo, thanks.

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Alf P. Steinbach, Sep 13, 2005
    #11
  12. wrote:
    > thanks for the replies, they were all helpful.
    >
    > I've a question about iterator behaviour. if I have
    >
    > difference_type res = iter1 - iter2
    >
    > the SGI website says that the precondition is that iter1 is "reachable
    > from iter2 or vice-versa, or both".
    > that includes past-the-end iterators too, doesn't it, for either iter1
    > or iter2. I mean if there are 10 iterms in a vector and I have iter1
    > and iter2 such that iter1 points to vector[3] and iter2 points to
    > past-the-end , then iter2-iter1 is still valid, isn't it? it's going to
    > return an iterator thats pointing to element[7] in the vector. yes?


    This is clearly a mental block so I'll say it loud.

    THE RETURN VALUE WHEN YOU SUBTRACT TWO ITERATORS IS AN

    ***INTEGER***

    Got that? Once you have everything else will fall into place.

    john
     
    John Harrison, Sep 14, 2005
    #12
  13. wrote:
    > one other thing... I have the iterators setup and I can now perform
    > things like;
    >
    > myIter i1 = wrapper.begin();
    > myIter i2 = wrapper.end();
    >
    > std::swap(i1, i2 );
    >
    > I can also call std::sort(i1 , i2);
    >
    > the above swap works fine and when I output the container contents, its
    > contents are correctly ordered.
    >
    > however if I try to do something like;;
    >
    > std::sort(i1, i2 -1 );
    >
    > the (borland) compiler complains that;
    >
    > [C++ Error] iterator.cpp(285): E2285 Could not find a match for
    > 'swap<_Tp,_Alloc>(myIter,myIter)'


    Can't see what the problem is there, how about posting line 285 from
    iterator.cpp

    >
    > I have defined operator- as
    >
    > // difference
    > int operator-(const contIter& rhs) const
    > {
    > return abs(m_index - rhs.m_index);
    > }


    Are you sure that's right? Surely should be

    int operator-(const contIter& rhs) const
    {
    return m_index - rhs.m_index;
    }

    Your code will always return a positive value, what if rhs is further
    advanced than *this?

    >
    > contIter operator-(int i) const
    > {
    > return contIter(m_container, m_index-i);
    > }
    >
    >
    >
    >
    > I\m obviously missing something but can't see what. any ideas?
    >
    >
    > thanks much again
    >
    > GrahamO
    >


    john
     
    John Harrison, Sep 14, 2005
    #13
  14. Guest

    thanks Clarke/John,

    I've cleared up the operator- business now (combination of typos and
    errors on my behalf), thanks for your help.

    I have painted "THE RETURN VALUE WHEN YOU SUBTRACT TWO ITERATORS IS AN
    ***INTEGER*** " onto the ceiling of my bedroom wall .. well not quite
    but I've commited it to memory at least :)

    Likewise the abs problem is corrected.

    Everything is working nicely now, I can std::swap, std::sort, etc.
    using my custom iterators.

    thanks for the replies. G
     
    , Sep 14, 2005
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Hendrik Maryns
    Replies:
    18
    Views:
    1,448
  2. greg
    Replies:
    6
    Views:
    469
    Dietmar Kuehl
    Jul 17, 2003
  3. Replies:
    6
    Views:
    670
    Jim Langston
    Oct 30, 2005
  4. Steven D'Aprano

    What makes an iterator an iterator?

    Steven D'Aprano, Apr 18, 2007, in forum: Python
    Replies:
    28
    Views:
    1,220
    Steven D'Aprano
    Apr 20, 2007
  5. David Bilsby
    Replies:
    5
    Views:
    2,070
    David Bilsby
    Oct 9, 2007
Loading...

Share This Page