a few questions about iterators

[Jess]

Hello,

Iterators are typically put into five different categories, namely
input iterator, output iterator, forward iterator, bidirectional
iterator and random iterator. The differences come from the
requirements each kind of iterator has to meet. Therefore, I think
the five categories are kind of conceptual thing, i.e. they are not
really C++ structs/classes etc, is this correct?

There are some functions that return iterators. For example, the
"back_inser ter" function returns an iterator when given a container.
Is the returned iterator an object of class type? For this particular
function, is the returned iterator a forward iterator only, or is it
random access iterator?

Another question is that if I implement a container, which has a
function "end()", then it should return one past the last element.
However, the one past element isn't in the container, if the "end()"
is

iterator end(){
return begin() + size();}

then the result may be a pointer pointing to some other structure. On
one hand, it looks a bit unsafe, hence I should reserve the last
element in my container (and not store any real value at that
position) to represent the one-past. On the other hand, since
deferencing an iterator to "end()" is undefined, perhaps I can just
return "begin()+size() ". Which strategy is better?

Thanks,
Jess

[Neelesh Bodas]

On Jul 6, 12:23 pm, Jess <w...@hotmail.c omwrote:

Hello,

Iterators are typically put into five different categories, namely
input iterator, output iterator, forward iterator, bidirectional
iterator and random iterator. The differences come from the
requirements each kind of iterator has to meet. Therefore, I think
the five categories are kind of conceptual thing, i.e. they are not
really C++ structs/classes etc, is this correct?

They are C++ classes, thats why a code like
vector<intv;
vector<int>::it erator s = v.begin();
compiles

There are some functions that return iterators. For example, the
"back_inser ter" function returns an iterator when given a container.
Is the returned iterator an object of class type?

Yeah, back_inserter() returns a back_insert_ite rator for the container
for which it is invoked.
template <class Cback_insert_it erator<Cback_in serter (C& x)

For this particular
function, is the returned iterator a forward iterator only, or is it
random access iterator?

The returned iteator is a back_insert_ite rator which is an adaptor
that functions as output iterator.

Another question is that if I implement a container, which has a
function "end()", then it should return one past the last element.
However, the one past element isn't in the container, if the "end()"
is

iterator end(){
return begin() + size();}

then the result may be a pointer pointing to some other structure. On
one hand, it looks a bit unsafe, hence I should reserve the last
element in my container (and not store any real value at that
position) to represent the one-past. On the other hand, since
deferencing an iterator to "end()" is undefined, perhaps I can just
return "begin()+size() ". Which strategy is better?

C++ guarantees that you can have an iterator to one-past-last element
of a container. Dereferencing such an itertaor is not allowed however.

>
Thanks,
Jess

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

On 2007-07-06 09:23, Jess wrote:

Hello,

Iterators are typically put into five different categories, namely
input iterator, output iterator, forward iterator, bidirectional
iterator and random iterator. The differences come from the
requirements each kind of iterator has to meet. Therefore, I think
the five categories are kind of conceptual thing, i.e. they are not
really C++ structs/classes etc, is this correct?

Yes, and no. Input, Output, ... iterators are concepts, the actual
iterators you use are objects instantiating these concepts. So
std::list<int>: :iterator is a bidirectional iterator, but it is also a
class, with members etc. just like any other class.

Consider std::list<int>: :iterator and std::set<int>:: iterator, they are
both bidirectional iterators, since they full fill all the requirements
that comes with that concept. They are also classes that can be
instantiated just like any other class. An important point though is
that they are not related through inheritance or some other OO concept,
the only relationship they have is that they are C++ Iterators as
defined by the standard.

There are some functions that return iterators. For example, the
"back_inser ter" function returns an iterator when given a container.
Is the returned iterator an object of class type? For this particular
function, is the returned iterator a forward iterator only, or is it
random access iterator?

Output iterator.

Another question is that if I implement a container, which has a
function "end()", then it should return one past the last element.
However, the one past element isn't in the container, if the "end()"
is

iterator end(){
return begin() + size();}

That's how std::vector does it. For node-based containers another
solution have to be used.

then the result may be a pointer pointing to some other structure. On
one hand, it looks a bit unsafe, hence I should reserve the last
element in my container (and not store any real value at that
position) to represent the one-past. On the other hand, since
deferencing an iterator to "end()" is undefined, perhaps I can just
return "begin()+size() ". Which strategy is better?

Reserving an extra element should not be needed.

--
Erik Wikström

[James Kanze]

On Jul 7, 2:50 pm, Jess <w...@hotmail.c omwrote:

On Jul 7, 12:21 am, James Kanze <james.ka...@gm ail.comwrote:

[...]

However, the one past element isn't in the container, if the "end()"
is
iterator end(){
return begin() + size();}

This supposes that the iterator is random access. It won't work
with most iterators. Even with random access iterators, it's at
least as likely that begin() and end() are the primitives, and
that size() is implemented:

size_type size() const
{
return end() - begin() ;
}

then the result may be a pointer pointing to some other structure.

Thanks. Do you mean I should implement begin() and end() first as
primitives and then define size() using end() - begin()?

No. It means that some implementations do it this way. You can
do it whichever way is most convenient for you.

If I have a
container that has an underlying array as a member, I think I can
probably return the "pointer-to-arrays-last-element + 1" as the result
of "end()". Would this work?

Yes.

--
James Kanze (Gabi Software) email: ja*********@gma il.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]