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_inserter" 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]

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<int> v;

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

Yeah, back_inserter() returns a back_insert_iterator for the container
for which it is invoked.

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

 

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

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_inserter" 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.

 

[James Kanze]

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?

Correct. I think the correct term here is that they are
concepts. Templates use duck-typing, and a concept represents
the set of constraits (or requirements) the type must conform to.

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

Certainly. The type is an instantiation of the
std::back_insertion_iterator class template, so it is a class
type. This type implements the concept of OutputIterator; in
other words, it fulfills all of the constraints and requirements
that the standard defines for an OutputIterator.

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

In this particular case, neither. It's an output iterator.

Note that in the case of iterators, there is a hierarchy of
concepts. The requirements of an output iterator are a subset
of those of a forward iterator, so any iterator which meets the
requirements of a forward iterator automatically meets those of
an output iterator.

Note that if we were doing this using static typing, and the
inheritance system, the fact that the requirements of A are a
subset of those of B would be expressed by the fact that A is a
base class of B. C++ leverages off this in one particular case,
the iterator tags, but in general, duck typing does not require
inheritance.

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

Sort of. Don't get hung up on physical location. What is
required is that "end()" return an iterator whose *value* meets
certain requirements: in particular, it should compare equal
with what you get when you increment an iterator designating the
last element, and---unlike iterators designating elements, a
program which calls operator* or operator-> on it has undefined
behavior.

Think in terms of behavior, not in terms of actual value.

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.

If you're thinking about std::vector, the result probably will
contain a pointer which points to one past the end. Which is
fine; you're allowed to manipulate (i.e. copy, compare, etc.)
such pointers. You're not allowed to dereference them, but
you're not allowed to do something like "*v.end()" either.

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.

It shouldn't be necessary; I don't even think it's really
possible. (How do you initialize this last element, given that
you aren't allowed to use the default constructor?)

On the other hand, since deferencing an iterator to "end()" is
undefined, perhaps I can just return "begin()+size()". Which
strategy is better?

There is no "better" strategy. It all depends on the design of
your container and your iterators.

 

[Jess]

Correct. I think the correct term here is that they are
concepts. Templates use duck-typing, and a concept represents
the set of constraits (or requirements) the type must conform to.


Certainly. The type is an instantiation of the
std::back_insertion_iterator class template, so it is a class
type. This type implements the concept of OutputIterator; in
other words, it fulfills all of the constraints and requirements
that the standard defines for an OutputIterator.


In this particular case, neither. It's an output iterator.

Note that in the case of iterators, there is a hierarchy of
concepts. The requirements of an output iterator are a subset
of those of a forward iterator, so any iterator which meets the
requirements of a forward iterator automatically meets those of
an output iterator.

Note that if we were doing this using static typing, and the
inheritance system, the fact that the requirements of A are a
subset of those of B would be expressed by the fact that A is a
base class of B. C++ leverages off this in one particular case,
the iterator tags, but in general, duck typing does not require
inheritance.


Sort of. Don't get hung up on physical location. What is
required is that "end()" return an iterator whose *value* meets
certain requirements: in particular, it should compare equal
with what you get when you increment an iterator designating the
last element, and---unlike iterators designating elements, a
program which calls operator* or operator-> on it has undefined
behavior.

Think in terms of behavior, not in terms of actual value.


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() ;
}

Thanks. Do you mean I should implement begin() and end() first as
primitives and then define size() using end() - begin()? 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? Thanks a lot.
Jess

 

[James Kanze]

On Jul 7, 12:21 am, James Kanze <[email protected]> wrote:

[...]

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.