473,322 Members | 1,408 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

iterator range

Whenever we specify an iterator range to a container operation or an
std::algorithm, the first iterator should always be a valid iterator
ie it should point to some element in the respective container? Am I
correct?

For example, suppose

vector<stringv;

v.erase(v.begin(), v.end());
sort(v.begin(), v.end());

Here since 'v' is empty, v.begin() does not refer to an element in the
container. So
both the above statements invoke undefined behaviour. Am I correct ?

Kindly clarify.

Thanks
V.Subramanian


Feb 9 '08 #1
5 2373
su**************@yahoo.com, India wrote:
Whenever we specify an iterator range to a container operation or an
std::algorithm, the first iterator should always be a valid iterator
ie it should point to some element in the respective container? Am I
correct?
...
Yes and no.

Yes, the first iterator has to be valid. Moreover, the second iterator also has
to be valid. Both of them have to be valid.

And no, a valid iterator does not necessarily point to the existing element in
the container. The iterator that points to the imaginary element that follows
the last existing element in the container is also perfectly valid. It cannot be
dereferenced, but it still can be used with non-dereferencing iterator
operations. When defining a sequence, the first iterator (begin) can be equal to
the second iterator (end), which defines an empty sequence. In this case there's
no requirement for the first iterator to point to an existing element.

--
Best regards,
Andrey Tarasevich
Feb 9 '08 #2
* On Feb 9, 1:12 am, "Alf P. Steinbach" <al...@start.nowrote:

* On Feb 9, 2:36 am, Andrey Tarasevich <andreytarasev...@hotmail.com>
wrote:

Thanks to both Alf P. Steinbach and Andrey Tarasevich for the reply:

(Please bear with me for the following post)

From your replies above, what I understand is that:

when we specify an iterator range, to a container operation or an
std::algorithm, both the first iterator and the last iterator can be
the sentinel ie both of them can be off-the-end iterators. correct?

If so, how do we know whether the implementation of container member
operations or the std:algorithms which accept an input range, will not
dereference the first iterator when both the first and last are
sentinel.

Essentially how do we know that the following operations' definitions
on all compiler implementations will not dereference the the first
iterator which is already the sentinel because the container is empty.

vector<stringv;

v.erase(v.begin(), v.end());
sort(v.begin(), v.end());

Kindly clarify.

Thanks
V.Subramanian
Feb 9 '08 #3
On Feb 9, 12:34 pm, "subramanian10...@yahoo.com, India"
<subramanian10...@yahoo.comwrote:
From your replies above, what I understand is that:
when we specify an iterator range, to a container operation or an
std::algorithm, both the first iterator and the last iterator can be
the sentinel ie both of them can be off-the-end iterators. correct?
For all of the algorithms in the standard library, at any rate.
If so, how do we know whether the implementation of container
member operations or the std:algorithms which accept an input
range, will not dereference the first iterator when both the
first and last are sentinel.
The same way that you know that it won't start by incrementing
the begin iterator three times, even if there are only two
elements in the sequence. The specifications of the function.
(Presumably, you could write a function which has a
pre-condition that distance( begin, end ) >= 3. There are
probably even some strange cases where it makes sense.)

The specifications of all of the functions in the standard
library, and most reasonably defined user functions, allows
empty sequences.
Essentially how do we know that the following operations'
definitions on all compiler implementations will not
dereference the the first iterator which is already the
sentinel because the container is empty.
vector<stringv;
v.erase(v.begin(), v.end());
sort(v.begin(), v.end());
Because the specifications of the functions in the standard say
so.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Feb 9 '08 #4
On Feb 9, 2:24 pm, Pete Becker <p...@versatilecoding.comwrote:

[...]
Essentially how do we know that the following operations' definitions
on all compiler implementations will not dereference the the first
iterator which is already the sentinel because the container is empty.
vector<stringv;
v.erase(v.begin(), v.end());
sort(v.begin(), v.end());
We know it won't do that because we trust the implementor of sort to
understand the rules for sequences.
We know it doesn't do that because the standard doesn't allow it
to do that. The standard pretty much says (not in that
language) that none of the algorithms will ever access through
an iterator equalt to end.

Of course, there is an aspect of trust involve. We trust the
implementors to respect the specifications of what they
implement.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Feb 9 '08 #5
On 2008-02-09 14:01:48 -0500, James Kanze <ja*********@gmail.comsaid:
On Feb 9, 2:24 pm, Pete Becker <p...@versatilecoding.comwrote:

[...]
>>Essentially how do we know that the following operations' definitions
on all compiler implementations will not dereference the the first
iterator which is already the sentinel because the container is empty.
>>vector<stringv;
>>v.erase(v.begin(), v.end());
sort(v.begin(), v.end());
>We know it won't do that because we trust the implementor of sort to
understand the rules for sequences.

We know it doesn't do that because the standard doesn't allow it
to do that. The standard pretty much says (not in that
language) that none of the algorithms will ever access through
an iterator equalt to end.
Yes, that's one of the rules for sequences.
>
Of course, there is an aspect of trust involve. We trust the
implementors to respect the specifications of what they
implement.
Yes, that's another way of saying what I said.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Feb 9 '08 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

38
by: Grant Edwards | last post by:
In an interview at http://acmqueue.com/modules.php?name=Content&pa=showpage&pid=273 Alan Kay said something I really liked, and I think it applies equally well to Python as well as the languages...
26
by: Michael Klatt | last post by:
I am trying to write an iterator for a std::set that allows the iterator target to be modified. Here is some relvant code: template <class Set> // Set is an instance of std::set<> class...
13
by: Mike Austin | last post by:
Hi all. Just working on a small virtual machine, and thought about using vector iterators instead of pointer arithmetic. Question is, why does an iterator plus any number out of range not...
5
by: Chris | last post by:
Hey all. Anyone who is familiar with Python programming knows that you can have code like this: list = This code puts all the items processed by the for loop in a list plus 1. Is there a way...
3
by: toton | last post by:
Hi, I want ro iterate over a few container class within a range specified, instead of begin & end. How to construct a range class, which takes start & end, and iteration is available within that...
16
by: mailforpr | last post by:
How do I do that? The thing is, the only information I have about the iterator is the iterator itself. No container it is belonging to or anything. Like template<Iteratorvoid...
0
by: toton | last post by:
Hi, I have a complex design of some dynamic situation. First I am posting the design, then a few questions regarding the problem I am facing. Hope some of the experts will answer the questions....
3
by: Belebele | last post by:
I have an Element class which is abstract and I would like to have an object of the Iterator class to iterate over a range of elements. I would like to use std::for_each to instrument the...
3
by: JurgenvonOerthel | last post by:
I want to replace one element in a list<stringby a list<stringand I need to obtain an iterator to the first element in the inserted list. In code: void...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.