Input iterators?

[desktop]

In accelerated C++ on page 146 there is this example:

template <class In, class Out>
Out copy(In begin, In end, Out dest)
{
While (begin != end)
*dest++ = *begin++;
return dest;
}

They say that the function takes 3 iterators, but is that not just
another name for a pointer?

If we are dealing with a string begin would be a pointer to the first
char, end would be a pointer to the last char and dest would contain the
copy.

Or does iterator mean something more complicated?

 

[Zeppe]

In accelerated C++ on page 146 there is this example:

template <class In, class Out>
Out copy(In begin, In end, Out dest)
{
While (begin != end)
*dest++ = *begin++;
return dest;
}

They say that the function takes 3 iterators, but is that not just
another name for a pointer?

If we are dealing with a string begin would be a pointer to the first
char, end would be a pointer to the last char and dest would contain the
copy.

Or does iterator mean something more complicated?

To simplify the concept, the iterators enclose the idea of pointer to a
set element. The set can be a string or a vector, and in this case it's
very similar to a classical pointer, but it can be a list, a map or any
other conceptual set, and the behaviour of the iterator is not always so
straightforward.

So, they are conceptually more abstracted than a pointer, that is a very
low level idea.

Regards,

Zeppe

 

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

In accelerated C++ on page 146 there is this example:

template <class In, class Out>
Out copy(In begin, In end, Out dest)
{
While (begin != end)
*dest++ = *begin++;
return dest;
}

They say that the function takes 3 iterators, but is that not just
another name for a pointer?

If we are dealing with a string begin would be a pointer to the first
char, end would be a pointer to the last char and dest would contain the
copy.

Or does iterator mean something more complicated?

An iterator is a concept in C++, anything that fulfills the requirements
can be used as iterators. In most (all?) cases a simple pointer does
fulfill the requirements of an iterator and can thus be use where an
iterator is required.

But an iterator can be so much more, consider for example std::map,
which is usually implemented as a RB-tree, std::map has a number of
methods that returns iterators, you can as an example iterate through
all elements in the map, this you can not do with a pointer since it
would require that all elements were contiguously laid out in memory.
The same goes for std::list which is a double-linked list.

To take the example with a string (a C++ one, and not a C char array)
there is no guarantee that the second char in the string is on the
memory-location after the first, but using iterators we let them worry
about that and just increment it to get an iterator to the next character.

 

[desktop]

An iterator is a concept in C++, anything that fulfills the requirements
can be used as iterators. In most (all?) cases a simple pointer does
fulfill the requirements of an iterator and can thus be use where an
iterator is required.

But an iterator can be so much more, consider for example std::map,
which is usually implemented as a RB-tree, std::map has a number of
methods that returns iterators, you can as an example iterate through
all elements in the map, this you can not do with a pointer since it
would require that all elements were contiguously laid out in memory.
The same goes for std::list which is a double-linked list.

To take the example with a string (a C++ one, and not a C char array)
there is no guarantee that the second char in the string is on the
memory-location after the first, but using iterators we let them worry
about that and just increment it to get an iterator to the next character.

Ok so reducing iterators to pointers only works if the only structure
that are used is an integer array (under the assumption that elements in
integer arrays are placed after each other in memory).

In other cases this assumption does not necessary hold and therefore its
necessary to use an iterator which I assume it designed to work on a lot
of different structures which makes it good in generic programming.

 

[Andrew Koenig]

In accelerated C++ on page 146 there is this example:
....

They say that the function takes 3 iterators, but is that not just another
name for a pointer?

It would be more accurate to say that a pointer is a kind of iterator, but
that there are other kinds of iterators too.

Please reread the discussion that starts near the bottom of page 144 and
continues on page 145. Also note that the book doesn't actually talk about
pointers until page 170, on the basis that once you understand iterators,
pointers are easy to understand.

 

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

Ok so reducing iterators to pointers only works if the only structure
that are used is an integer array (under the assumption that elements in
integer arrays are placed after each other in memory).

Any array will do, since arrays are guaranteed to be a contiguous piece
of memory.

In other cases this assumption does not necessary hold and therefore its
necessary to use an iterator which I assume it designed to work on a lot
of different structures which makes it good in generic programming.

Yes, each class, such as vector, map and list, has it's own iterator-
type. Consider the following code:

std::vector<int> vec;
typedef std::vector<int>::iterator iter;

for (iter i = vec.begin(); i != vec.end(); ++i)
std::cout << *i << std::endl;

Then you can just replace std::vector<int> with, for example,
std::list<std::string> and it will work.

 

[desktop]

Any array will do, since arrays are guaranteed to be a contiguous piece
of memory.


Yes, each class, such as vector, map and list, has it's own iterator-
type. Consider the following code:

std::vector<int> vec;
typedef std::vector<int>::iterator iter;

for (iter i = vec.begin(); i != vec.end(); ++i)
std::cout << *i << std::endl;

Then you can just replace std::vector<int> with, for example,
std::list<std::string> and it will work.

Ok I thought that a pointer or an iterator was just a number, but it
seems that the compiler treats them as different types:

int myints[] = {1,2,3,4,5,1,2,3,4,5};
std::vector<int> myvector (myints,myints+10);

int match1[] = {1,2,3};

int ff = match1; // gives an error indicating that match1 is an int*
int gg = myvector.begin(); // gives an error indicating that
myvector.begin() is an iterator.


BTW: Why is this legal:
std::vector<int> myvector (myints,myints+10);

on this page:
http://www.cppreference.com/cppvector/vector_constructors.html

it should match:

vector( input_iterator start, input_iterator end );

but as just described 'myints' like 'match1' are int* and not iterators.

 

[Zeppe]

Ok I thought that a pointer or an iterator was just a number, but it
seems that the compiler treats them as different types:

The iterator is a class in the most general situation. Actually, there
are not specific constraints on the type of the iterators, but rather on
the operation they support, as in http://www.cppreference.com/iterators.html

BTW: Why is this legal:
std::vector<int> myvector (myints,myints+10);

on this page:
http://www.cppreference.com/cppvector/vector_constructors.html

it should match:

vector( input_iterator start, input_iterator end );

but as just described 'myints' like 'match1' are int* and not iterators.

an input iterator is defined as an object that can be compared (operator
==), incremented (operator++) and dereferenced (operator&) to read the
associated container values. That's it. Everything that supports these
three operations is an iterator... so, there is nothing that prevents
the int* to be used as an iterator. Of course, you have to take care
that the pointer actually iterates on something that is allocated
properly ^^

Regards,

Zeppe

 

[James Kanze]

Erik Wikström wrote:

[...]

Ok I thought that a pointer or an iterator was just a number, but it
seems that the compiler treats them as different types:

At a certain level, everything is just a number (or a collection
of numbers). At that level, you're generally programming in
assembler. C++ is a typed language, and pointers are definitly
not numbers.

int myints[] = {1,2,3,4,5,1,2,3,4,5};
std::vector<int> myvector (myints,myints+10);

int match1[] = {1,2,3};

int ff = match1; // gives an error indicating that match1 is an int*
int gg = myvector.begin(); // gives an error indicating that
myvector.begin() is an iterator.

BTW: Why is this legal:
std::vector<int> myvector (myints,myints+10);

on this page:http://www.cppreference.com/cppvector/vector_constructors.html

it should match:

vector( input_iterator start, input_iterator end );

but as just described 'myints' like 'match1' are int* and not
iterators.

Well, the template mechanism doesn't care. All it requires is
that the two parameters have the same type. The actual
implementation of vector supposes, however, that these two types
meet the constraints of an iterator, i.e. you can increment
them, dereference them, etc. And iterators (and their
constraints) were designed so that pointers meet these
constraints: a pointer acts like an iterator.

(Note that there is a very special case here, and something
like:

std::vector< int > v( 20, 42 ) ;

also invokes this constructor... which due to some tricky
template programming, doesn't treat the integers as iterators.)