Another String reversal question

J

Jeff Schwab

Dhruv said:
On Mon, 22 Dec 2003 09:11:56 -0500, Francis Glassborow wrote:

[...]

The address of one past the last must be owned by the process. Note that
only requires a single extra address in the address range. One before
the start is an entirely different issue which is why it is not
supported.


Then how are reverse iterators supposed to work?

Supposed by whom? These rules were in place long before there was an STL.

A reverse iterator actually works by associating itself with one element
higher than what you'd think. When you try to convert between forward
and reverse iterators, you don't get what you might expect.

-Jeff
 
B

Buster

ok, no because as John Potter mentioned that the delete expression is
allowed to modify the pointer passed to it,

No, he didn't. He said the delete expression invalidates the pointer
passed to it. The pointer is not changed, but it is no longer a valid pointer.
so I was just wondering how it
would modify a constant passed to it. But now that you've mentioned that
C++ guarantees a Null operation, there's nothing wrong with it.

Regards,
Buster
 
B

Buster

Dhruv said:
On Mon, 22 Dec 2003 09:11:56 -0500, Francis Glassborow wrote:

[...]
The address of one past the last must be owned by the process. Note that
only requires a single extra address in the address range. One before
the start is an entirely different issue which is why it is not
supported.

Then how are reverse iterators supposed to work?

The base pointer of a reverse iterator points to a location one past
the location conceptually pointed to by the reverse iterator. Simple.

Regards,
Buster.
 
K

kanze

Dhruv said:
Dhruv said:
It would be nice if you could explain what happens on
architectures with 'address registers', and what they actually are?
[...]
The issue was that these architectures could only index 16-bits
worth of address space at a time, a separate register held the rest
of the address. Without specifically mandating the one-past-the-end
guarantees, it was quite possible that an object/array could be
placed at the end of a 64K segment. The one past the end address
could roll over to be have a value LESS than an address inside the
array (if the behavior was left undefined as other outside the
bounds of arrays are even today).
So, I guess adding 1 to the end of the array would mean that the
higher 16-bits in the register would get incremented by 1 and the
lower 16-bits would roll back to 0?

No. The lower 16 bits would wrap to 0, and the higher 16 bits would
remain unchanged.

Note that this is standard segmented architecture. And that it is still
true for modern Intel processors, if you replace lower 16 bits with
lower 32 bits. While some widespread architectures artificially limit
the Intel to linear addressing, the processor is capable of much more,
and I've worked with systems using 48 bit addresses.

The result is that the hardware will allow an object with 2^32 bytes,
but C and C++ won't (because the address of the object plus one would
not be greater than the address of the object).
[...]
Another issue is while by and large most architectures only trap
invalid acesses when you actually read or write through pointers to
invalid memory, nothing precludes a machine from trapping when you
manipulate an invalid pointer value. Again you will need the
one-past-the-end guarantee. This might happen someday when security
and reliability become more important that the current cavalier
Microsoft-induced attitude.
So, isn't one past the end of the array also some memory that the
running process might not bw owning? I have probably misunderstood
something here.
Assume this is the array:
[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
^ ^ ^
| | |
First element Last |
|
One past last.
Now, do you mean to say that the one past last element of the array is
also opwned by the process?

The C and the C++ standards require the implementation to allow the
existance of such addresses. How they do so is their problem. If
loading such an address in an address register would trap, either the
implementation must ensure that it never generates code to load it into
an address register, or (more frequently), it must ensure that there is
an extra addressable byte behind each object.
 
K

kanze

Francis Glassborow said:
Dhruv said:
So, isn't one past the end of the array also some memory that the
running process might not bw owning? I have probably misunderstood
something here.
Assume this is the array:
[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
^ ^ ^
| | |
First element Last |
|
One past last.
Now, do you mean to say that the one past last element of the array
is also opwned by the process?
The address of one past the last must be owned by the process.

No. The implementation must ensure that I can read the address value
(but not necessarily dereference it). Owning one additional byte is one
possible solution -- not loading the address into an address register
unless it is going to be dereferenced is another.
 
F

Francis Glassborow

Dhruv said:
Then how are reverse iterators supposed to work?

with difficulty:) Which is exactly why they are provided by Standard
containers. Effectively they dereference the iterator value 'before'
before the one being 'held' that means when they get to the 'first'
(i.e. rend()) they stop because there is nothing before it.
 
F

Francis Glassborow

In message said:
There is no error return value for the comparison functions passed to
qsort and bsearch.

Yes, we both know that but countless programmers think in terms of
checking if two things are equal and so consider the zero return to be
'success'.
 
G

Gabriel Dos Reis

(e-mail address removed) writes:

[...]

| > The address of one past the last must be owned by the process.
|
| No. The implementation must ensure that I can read the address value
| (but not necessarily dereference it). Owning one additional byte is one
| possible solution -- not loading the address into an address register
| unless it is going to be dereferenced is another.

comparaison may need to load the pointer into address register too.
 
D

Dhruv

with difficulty:) Which is exactly why they are provided by Standard
containers. Effectively they dereference the iterator value 'before'
before the one being 'held' that means when they get to the 'first'
(i.e. rend()) they stop because there is nothing before it.

Oh! Ingenious.

Regards,
-Dhruv.
 
S

Siemel Naran

A iterator actually works by associating itself with one element
higher than what you'd think. When you try to convert between forward
and reverse iterators, you don't get what you might expect.

That depends on what you're trained to expect.
 
K

kanze

Gabriel Dos Reis said:
(e-mail address removed) writes:

| > The address of one past the last must be owned by the process.
| No. The implementation must ensure that I can read the address
| value (but not necessarily dereference it). Owning one additional
| byte is one possible solution -- not loading the address into an
| address register unless it is going to be dereferenced is another.
comparaison may need to load the pointer into address register too.

In that case, the implementation must allocate one extra byte. It's
never been the case with any hardware I've used. In fact, if I remember
right, on a Motorola 68000 (or maybe it was some other processor), the
hardware didn't support comparison of address registers. Which was a
pain: if you wrote something like:
if ( p != NULL && *p != '\0') ...
the compiler had to put p in different registers in each of the two
parts of the expression.
 
K

kanze

Yes, we both know that but countless programmers think in terms of
checking if two things are equal and so consider the zero return to be
'success'.

But not the authors of qsort or bsearch:).

I do know that some programmers tend to think of strcmp as meaning
strequ. With sometimes disasterous results:

if ( strcmp( a, b ) )
// Strings are equal...
 
K

kanze

with difficulty:) Which is exactly why they are provided by Standard
containers. Effectively they dereference the iterator value 'before'
before the one being 'held' that means when they get to the 'first'
(i.e. rend()) they stop because there is nothing before it.

Note that long before the STL, it was standard practice in C to use half
open intervals -- the standard loop over an array, for example, was:

for ( int i = 0 ; i < arraySize ; i ++ )
doSomethingWith( array[ i ] ) ;

Applying this logic to reverse "iterators" (where iterator is used to
mean anything used to designate an element, including indexes): the
iterator designates the top end, which is the open open end of the
interval. Thus, the standard reverse loop was:

for ( int i = arraySize ; i > 0 ; i -- )
doSomethingWith( array[ i - 1 ] ) ;

At least, that was the way I always wrote it, even back in my C days.
In the case of a while loop, when iterating up, the incrementation is at
the end of the loop; when iterating down, the decrementation is the
first instruction in the loop.

All of this seems something trivially obvious to me. The while loop
handling was the standard procedure in Pascal and Modula-2 (before I
started using C) -- for loops are somewhat limited in those languages,
and aren't used much.

What's the point in starting array indexes at 0 otherwise?

Anyway, reverse iterators in the STL only encapsulate this standard
technique. They are nice syntactic sugar, but there's hardly any "with
difficulty" -- they just use the standard idioms that every one has used
for ages.
 
D

Dhruv

On Wed, 24 Dec 2003 13:51:14 -0500, kanz wrote:

[...]
Anyway, reverse iterators in the STL only encapsulate this standard
technique. They are nice syntactic sugar, but there's hardly any "with
difficulty" -- they just use the standard idioms that every one has used
for ages.

That's exactly the problem with me. I've been around for just 19 something
years since the time I was 'instantiated' ;-)


Merry Christmas,
-Dhruv.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
474,175
Messages
2,570,942
Members
47,490
Latest member
Finplus

Latest Threads

Top