Problem with iterators

[desktop]

1)

I have this code:

std::list<int> mylist;
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(3);
mylist.push_back(4);

std::list<int>::iterator it_p = mylist.begin();
std::list<int>::iterator it_q = mylist.end();

std::set<int> myset(it_p,it_q);

int first = *myset.begin();
int second = *myset.end();
std::cout << "first = " << first << std::endl;
std::cout << "second = " << second << std::endl;


I copy the elements from the "list" to the "set" with the two iterators:
"it_p" and "it_q". When I print "first" and "second" I get 1 and 4. But
should:

int second = *myset.end();

not return the value of the element *after* the last which is undefined?
I thought that I had to decrement myset.end() by one to get the value 4.



2)

Another thing. As I understand each container supports a specific
iterator. Eg. list only supports forward iterators while set supports
bidirectional iterators.

But where (have tried) google do I find a list of each iterator that a
container supports?

 

[Victor Bazarov]

1)

I have this code:

std::list<int> mylist;
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(3);
mylist.push_back(4);

std::list<int>::iterator it_p = mylist.begin();
std::list<int>::iterator it_q = mylist.end();

std::set<int> myset(it_p,it_q);

int first = *myset.begin();
int second = *myset.end();

This causes undefined behaviour. The iterator returned by 'end()' is
non-dereferenceable. You probably want '*myset.rbegin()'.

std::cout << "first = " << first << std::endl;
std::cout << "second = " << second << std::endl;


I copy the elements from the "list" to the "set" with the two
iterators: "it_p" and "it_q". When I print "first" and "second" I get
1 and 4. But should:

int second = *myset.end();

not return the value of the element *after* the last which is
undefined? I thought that I had to decrement myset.end() by one to
get the value 4.

Whatever you think your program should do, it's all wrong. The code
has undefined behaviour.

2)

Another thing. As I understand each container supports a specific
iterator. Eg. list only supports forward iterators

Wrong. std::list supports bidirectional iterators.

while set supports
bidirectional iterators.

But where (have tried) google do I find a list of each iterator that a
container supports?

Get a copy of the Standard.

V

 

[desktop]

This causes undefined behaviour. The iterator returned by 'end()' is
non-dereferenceable. You probably want '*myset.rbegin()'.


Whatever you think your program should do, it's all wrong. The code
has undefined behaviour.


Wrong. std::list supports bidirectional iterators.

Ok in the standard it says that list, vector and dequeue all are
Sequences. On page 469 it says that iterator should at least be forward.
But since binary minus '-' gives a compile error I assume they don't
support random access iterator. Is the *at least* formulation not a bit
un-precise?

Further the i and j iterators has to be of type input iterator. I don't
know of any containers that supports this type or any way that you can
make an input iterator.

Is it to make restrictions on the use of these iterators if they are
used in the eg. constructor (you are only allowed to use the operators
for input iterators even though no containers return this kind of iterator)?

 

[Andre Kostur]

1)

I have this code:

std::list<int> mylist;
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(3);
mylist.push_back(4);

std::list<int>::iterator it_p = mylist.begin();
std::list<int>::iterator it_q = mylist.end();

std::set<int> myset(it_p,it_q);

int first = *myset.begin();
int second = *myset.end();

Undefined behaviour. You cannot dereference an end() iterator.

std::cout << "first = " << first << std::endl;
std::cout << "second = " << second << std::endl;


I copy the elements from the "list" to the "set" with the two iterators:
"it_p" and "it_q". When I print "first" and "second" I get 1 and 4. But
should:

int second = *myset.end();

not return the value of the element *after* the last which is undefined?
I thought that I had to decrement myset.end() by one to get the value

4.

Undefined behaviour has been invoked. One can no longer predict the
behaviour.

 

[jpalecek]

desktop napsal:

1)

I have this code:

std::list<int> mylist;
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(3);
mylist.push_back(4);

std::list<int>::iterator it_p = mylist.begin();
std::list<int>::iterator it_q = mylist.end();

std::set<int> myset(it_p,it_q);

int first = *myset.begin();
int second = *myset.end();
std::cout << "first = " << first << std::endl;
std::cout << "second = " << second << std::endl;


I copy the elements from the "list" to the "set" with the two iterators:
"it_p" and "it_q". When I print "first" and "second" I get 1 and 4. But
should:

int second = *myset.end();

not return the value of the element *after* the last which is undefined?
I thought that I had to decrement myset.end() by one to get the value 4.

Yes, you have to do it. The code you've posted just invokes undefined
behaviour,
which means that it can result to anything the implementor decides,
particularly, it can return 4, but on a different platform, it might
crash the
program or return -45246961 or whatever else.

2)

Another thing. As I understand each container supports a specific
iterator. Eg. list only supports forward iterators while set supports
bidirectional iterators.

But where (have tried) google do I find a list of each iterator that a
container supports?

Each container has a specific iterator class. This class satisfies
some
concept (similar to interface), theses are the Input/Forward/
Bidirectional/...
[btw. there is a hierarchy between these]. What each container's
iterator has
to satisfy, can be read in the SGI STL manual. For example, with list,
there is

list is a model of reversible container

and on a page about reversible container, there is

.... the iterators must be Bidirectional Iterators

so we know a list must hav an iterator at least as strong as
Bidirectional.

Regards
Jiri Palecek

 

[jpalecek]

desktop napsal:

Ok in the standard it says that list, vector and dequeue all are
Sequences. On page 469 it says that iterator should at least be forward.
But since binary minus '-' gives a compile error I assume they don't
support random access iterator. Is the *at least* formulation not a bit
un-precise?

Did you get compile time error on list, deque or vector? list only
has
bidirectional iterator, whereas deque and vector are Random Access
Containers which support random access iterators.

Further the i and j iterators has to be of type input iterator. I don't
know of any containers that supports this type or any way that you can
make an input iterator.

Virtually any iterator you can make is input iterator. For example,
forward
iterator is a refinement of input iterator. So any iterator of any
container
will do. There are also "pure" input iterators like istream_iterator.

Is it to make restrictions on the use of these iterators if they are
used in the eg. constructor (you are only allowed to use the operators
for input iterators even though no containers return this kind of iterator)?

Yes. This means you can use istream_iterator in the constructor as
well.

Regards
Jiri Palecek

 

[desktop]

desktop napsal:

1)

I have this code:

std::list<int> mylist;
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(3);
mylist.push_back(4);

std::list<int>::iterator it_p = mylist.begin();
std::list<int>::iterator it_q = mylist.end();

std::set<int> myset(it_p,it_q);

int first = *myset.begin();
int second = *myset.end();
std::cout << "first = " << first << std::endl;
std::cout << "second = " << second << std::endl;


I copy the elements from the "list" to the "set" with the two iterators:
"it_p" and "it_q". When I print "first" and "second" I get 1 and 4. But
should:

int second = *myset.end();

not return the value of the element *after* the last which is undefined?
I thought that I had to decrement myset.end() by one to get the value 4.

Yes, you have to do it. The code you've posted just invokes undefined
behaviour,
which means that it can result to anything the implementor decides,
particularly, it can return 4, but on a different platform, it might
crash the
program or return -45246961 or whatever else.

2)

Another thing. As I understand each container supports a specific
iterator. Eg. list only supports forward iterators while set supports
bidirectional iterators.

But where (have tried) google do I find a list of each iterator that a
container supports?

Each container has a specific iterator class. This class satisfies
some
concept (similar to interface), theses are the Input/Forward/
Bidirectional/...
[btw. there is a hierarchy between these]. What each container's
iterator has
to satisfy, can be read in the SGI STL manual. For example, with list,
there is

list is a model of reversible container

and on a page about reversible container, there is

.... the iterators must be Bidirectional Iterators

so we know a list must hav an iterator at least as strong as
Bidirectional.

Actually the C++ Standard says that i should be at least be forward see
page 469 item [5]:

http://www.usatlas.bnl.gov/~dladams/cpp/INCITS+ISO+IEC+14882-2003.pdf

 

[desktop]

desktop napsal:

Did you get compile time error on list, deque or vector? list only
has
bidirectional iterator, whereas deque and vector are Random Access
Containers which support random access iterators.


Virtually any iterator you can make is input iterator. For example,
forward
iterator is a refinement of input iterator. So any iterator of any
container
will do. There are also "pure" input iterators like istream_iterator.


Yes. This means you can use istream_iterator in the constructor as
well.

What confuses me if its allowed use other operators on i and j besides
from the input iterator operations.

If I pass two vector iterators (random access) as i and j they fulfill
input operators but also some extra. Is it allowed use these extra
operators or is it only legal to use input defined ones?

 

[jpalecek]

desktop napsal:

desktop napsal:

1)

I have this code:

std::list<int> mylist;
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(3);
mylist.push_back(4);

std::list<int>::iterator it_p = mylist.begin();
std::list<int>::iterator it_q = mylist.end();

std::set<int> myset(it_p,it_q);

int first = *myset.begin();
int second = *myset.end();
std::cout << "first = " << first << std::endl;
std::cout << "second = " << second << std::endl;


I copy the elements from the "list" to the "set" with the two iterators:
"it_p" and "it_q". When I print "first" and "second" I get 1 and 4. But
should:

int second = *myset.end();

not return the value of the element *after* the last which is undefined?
I thought that I had to decrement myset.end() by one to get the value 4.

Yes, you have to do it. The code you've posted just invokes undefined
behaviour,
which means that it can result to anything the implementor decides,
particularly, it can return 4, but on a different platform, it might
crash the
program or return -45246961 or whatever else.

2)

Another thing. As I understand each container supports a specific
iterator. Eg. list only supports forward iterators while set supports
bidirectional iterators.

But where (have tried) google do I find a list of each iterator that a
container supports?

Each container has a specific iterator class. This class satisfies
some
concept (similar to interface), theses are the Input/Forward/
Bidirectional/...
[btw. there is a hierarchy between these]. What each container's
iterator has
to satisfy, can be read in the SGI STL manual. For example, with list,
there is

list is a model of reversible container

and on a page about reversible container, there is

.... the iterators must be Bidirectional Iterators

so we know a list must hav an iterator at least as strong as
Bidirectional.

Actually the C++ Standard says that i should be at least be forward see
page 469 item [5]:

http://www.usatlas.bnl.gov/~dladams/cpp/INCITS+ISO+IEC+14882-2003.pdf

Yes, but in 23.2.2 item [2], on page 481, there is

A list satisfies all requirements ... of reversible container.

And in 23.1 item 9, there is that reversible containers have
Bidirectional or
Random Access category iterators. Because Random Access are stronger
than Bidirectional and Bidirectional are stronger than Forward (24.1),
we know that
a list have at leas as strong iterators as Bidirectional.

 

[desktop]

desktop napsal:

desktop napsal:
1)

I have this code:

std::list<int> mylist;
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(3);
mylist.push_back(4);

std::list<int>::iterator it_p = mylist.begin();
std::list<int>::iterator it_q = mylist.end();

std::set<int> myset(it_p,it_q);

int first = *myset.begin();
int second = *myset.end();
std::cout << "first = " << first << std::endl;
std::cout << "second = " << second << std::endl;


I copy the elements from the "list" to the "set" with the two iterators:
"it_p" and "it_q". When I print "first" and "second" I get 1 and 4. But
should:

int second = *myset.end();

not return the value of the element *after* the last which is undefined?
I thought that I had to decrement myset.end() by one to get the value 4.
Yes, you have to do it. The code you've posted just invokes undefined
behaviour,
which means that it can result to anything the implementor decides,
particularly, it can return 4, but on a different platform, it might
crash the
program or return -45246961 or whatever else.

2)

Another thing. As I understand each container supports a specific
iterator. Eg. list only supports forward iterators while set supports
bidirectional iterators.

But where (have tried) google do I find a list of each iterator that a
container supports?
Each container has a specific iterator class. This class satisfies
some
concept (similar to interface), theses are the Input/Forward/
Bidirectional/...
[btw. there is a hierarchy between these]. What each container's
iterator has
to satisfy, can be read in the SGI STL manual. For example, with list,
there is

list is a model of reversible container

and on a page about reversible container, there is

.... the iterators must be Bidirectional Iterators

so we know a list must hav an iterator at least as strong as
Bidirectional.

Actually the C++ Standard says that i should be at least be forward see
page 469 item [5]:

http://www.usatlas.bnl.gov/~dladams/cpp/INCITS+ISO+IEC+14882-2003.pdf

Yes, but in 23.2.2 item [2], on page 481, there is

A list satisfies all requirements ... of reversible container.

And in 23.1 item 9, there is that reversible containers have
Bidirectional or
Random Access category iterators. Because Random Access are stronger
than Bidirectional and Bidirectional are stronger than Forward (24.1),
we know that
a list have at leas as strong iterators as Bidirectional.

Ok I guess what I was referring to was for Sequences which is the
"general abstraction" and not list which is a "concrete" realization.

 

[Andre Kostur]

Ok in the standard it says that list, vector and dequeue all are
Sequences. On page 469 it says that iterator should at least be
forward. But since binary minus '-' gives a compile error I assume
they don't support random access iterator. Is the *at least*
formulation not a bit un-precise?

Nope. Says at minimum, sequence containers must support forward
iterators. They may support more. (And correct, lists do not support
random-access iterators, vectors do).

Further the i and j iterators has to be of type input iterator. I
don't know of any containers that supports this type or any way that
you can make an input iterator.
istream_iterator

Is it to make restrictions on the use of these iterators if they are
used in the eg. constructor (you are only allowed to use the operators
for input iterators even though no containers return this kind of
iterator)?

No, it's placing minimum requirements on the input, like any good design
would. There's nothing stopping you from using a bidirectional iterator
where an input iterator is called for. The operations on a bidir
iterator is a superset of what is available on an input iterator.

 

[Victor Bazarov]

[..]
What confuses me if its allowed use other operators on i and j besides
from the input iterator operations.

I am guessing you're referring to the constructor of 'std::set' that
takes iterators. The least restricting requirement is that it takes
input iterators. All other iterators _are_ input iterators because
they satisfy the requirements for input iterators.

If I pass two vector iterators (random access) as i and j they fulfill
input operators but also some extra. Is it allowed use these extra
operators or is it only legal to use input defined ones?

What do you mean "allowed use these extra operators"? Any class that
satisfies the requirements for "input iterators" would do. Even
a plain pointer (to an element of an array).

V

 

[desktop]

Nope. Says at minimum, sequence containers must support forward
iterators. They may support more. (And correct, lists do not support
random-access iterators, vectors do).


No, it's placing minimum requirements on the input, like any good design
would. There's nothing stopping you from using a bidirectional iterator
where an input iterator is called for. The operations on a bidir
iterator is a superset of what is available on an input iterator.

What I meant was the restriction on the operations in the constructor.
Since the minimum requirement are input iterators I cannot use something
like:

input_iterator - 1;

in the constructor since that only applies for random access iterators.
I can only use "up to" input iterator operations.

 

[desktop]

[..]
What confuses me if its allowed use other operators on i and j besides
from the input iterator operations.

I am guessing you're referring to the constructor of 'std::set' that
takes iterators. The least restricting requirement is that it takes
input iterators. All other iterators _are_ input iterators because
they satisfy the requirements for input iterators.

If I pass two vector iterators (random access) as i and j they fulfill
input operators but also some extra. Is it allowed use these extra
operators or is it only legal to use input defined ones?

What do you mean "allowed use these extra operators"? Any class that
satisfies the requirements for "input iterators" would do. Even
a plain pointer (to an element of an array).

In the std::set constructor I assume there is no operations like:

input_iterator - 1;

since that operations is only defined for random access iterators. The
only operations that are allowed are those "up to" input iterator
operations.

 

[Victor Bazarov]

[..]
What I meant was the restriction on the operations in the constructor.
Since the minimum requirement are input iterators I cannot use
something like:

input_iterator - 1;

in the constructor since that only applies for random access
iterators. I can only use "up to" input iterator operations.

That's the nature of the input iterators. If you need to input
a certain number of elements (and you know how many there are),
don't use a c-tor with iterators, use a counted loop. Otherwise
you are asking basically to "stop one step before you touch the
wall". How would an iterator without the ability to see ahead
of it (like the input iterator) know when it is "one step before
touching"? It can only "touch", recognize that the end value
has been reached. It's like in the old joke: "Could you tell
me when to get off this bus to reach Piccadilly? -- Yes. Watch
me, you will need to exit one stop _before_ me."

V

 

[Victor Bazarov]

[..]
What confuses me if its allowed use other operators on i and j
besides from the input iterator operations.

I am guessing you're referring to the constructor of 'std::set' that
takes iterators. The least restricting requirement is that it takes
input iterators. All other iterators _are_ input iterators because
they satisfy the requirements for input iterators.

If I pass two vector iterators (random access) as i and j they
fulfill input operators but also some extra. Is it allowed use
these extra operators or is it only legal to use input defined ones?

What do you mean "allowed use these extra operators"? Any class that
satisfies the requirements for "input iterators" would do. Even
a plain pointer (to an element of an array).

In the std::set constructor I assume there is no operations like:

input_iterator - 1;

Of course there isn't. Input iterators do not support + or -.

since that operations is only defined for random access iterators. The
only operations that are allowed are those "up to" input iterator
operations.

Well, open the source for the set constructor and look. It's really
quite simple, I am sure. I bet your compiler includes all the sources
for the Standard library. If it doesn't, download a free one (like
stlport) and look at its implementation.

V

 

[Clark Cox]

What I meant was the restriction on the operations in the constructor.
Since the minimum requirement are input iterators I cannot use
something like:

input_iterator - 1;

Of course; since the constructor claims to take an input iterator, it
cannot assume that it is given anything else. This is roughly analogous
to a function taking a pointer to a class, and someone else passing a
subclass:

struct Foo {
void FooFunction() {}
};

struct Bar : Foo {
void BarFunction() {}
};

void function(Foo *foo)
{
/* I cannot call BarFunction, even if the parameter really is a Bar */
}

int main()
{
Foo foo;
Bar bar;
function(foo);
function(bar);
return 0;
}

in the constructor since that only applies for random access iterators.
I can only use "up to" input iterator operations.

For your purposes*, that is correct.

*) There are ways, through template specialization, that the function
can determine if you've really given it an input iterator, or something
more capable (like a bidirectional iterator or a pointer), and optimize
accordingly, but you probably don't need to worry about that just yet.

 

[James Kanze]

[..]
What confuses me if its allowed use other operators on i and j besides
from the input iterator operations.

I am guessing you're referring to the constructor of 'std::set' that
takes iterators. The least restricting requirement is that it takes
input iterators. All other iterators _are_ input iterators because
they satisfy the requirements for input iterators.

If I pass two vector iterators (random access) as i and j they fulfill
input operators but also some extra. Is it allowed use these extra
operators or is it only legal to use input defined ones?

What do you mean "allowed use these extra operators"? Any class that
satisfies the requirements for "input iterators" would do. Even
a plain pointer (to an element of an array).

In the std::set constructor I assume there is no operations like:

input_iterator - 1;

since that operations is only defined for random access iterators. The
only operations that are allowed are those "up to" input iterator
operations.

The implementation is required to work if given input iterators.
How it does so is its business. In the case of set::set, I very
much doubt that there are any subtractions on the the iterators,
but in std::vector, an implementation is required to do so if
possible; it must distinguish between the different types of
iterators, and behave differently when given a random access
iterator.

 

[James Kanze]

I have this code:

std::list<int> mylist;
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(3);
mylist.push_back(4);

std::list<int>::iterator it_p = mylist.begin();
std::list<int>::iterator it_q = mylist.end();

std::set<int> myset(it_p,it_q);

int first = *myset.begin();
int second = *myset.end();
std::cout << "first = " << first << std::endl;
std::cout << "second = " << second << std::endl;

I copy the elements from the "list" to the "set" with the two
iterators: "it_p" and "it_q". When I print "first" and
"second" I get 1 and 4. But should:

int second = *myset.end();

not return the value of the element *after* the last which is
undefined? I thought that I had to decrement myset.end() by
one to get the value 4.

It's undefined behavior, of course. Just for the record, this
code core dumps with both g++ and VC++, at least in "debug"
mode.

Another thing. As I understand each container supports a specific
iterator. Eg. list only supports forward iterators while set supports
bidirectional iterators.

But where (have tried) google do I find a list of each iterator that a
container supports?

The Dinkumware site has some very good documentation, try:
http://www.dinkumware.com/manuals/.