custom iterator

G

Grahamo

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.
 
G

Guest

[...]
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
 
A

Alf P. Steinbach

* (e-mail address removed):
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).
 
M

Mike Wahler

Alf P. Steinbach said:
* (e-mail address removed):
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
 
T

Thomas Tutone

Mike said:
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
 
J

John Harrison

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
 
G

Grahamo

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
 
C

Clark S. Cox III

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.
 
M

Mike Wahler

Thomas Tutone said:
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
 
G

Grahamo

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
 
J

John Harrison

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
 
J

John Harrison

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
 
G

Grahamo

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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top