Re: a few questions about iterators
On Jul 6, 9:23 am, Jess <w...@hotmail.com> wrote:
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.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34