Substraction or decrement random access iterator pointing to begin

Question

Consider following piece of code

void foo( bool forwad )
{
    vector<MyObject>::iterator it, end_it;
    int dir;

    it = some_global_vector.begin() + some_position;
    if( forward )
    {
        dir = 1;
        it += 1;
        end_it = some_global_vector.end();

    }
    else
    {
        dir = -1;
        it -= 1;
        end_it = some_global_vector.begin()-1;
    }

    while( it != end_it )
    {
       if( do_domething() )
         break;

       it += dir;
    }
}

As you can see there is some doubt when forward == false becouse there is an substraction from begin() and iterator it can be substracted when it points at begin(). I can't find anywhere if it is ok until I not dereference this bad pointing iterator).

EDIT

I read ISO C++ Standard and have some conclusions. There is no promise that vector::begin() can't internaly point to memory at adress 0, and I was thinking that It is the end, but all containers depend on standard alocator. This alocator depends on new operator. And also, there is no information that new will never return 0. But standard alocator depends also on delete operator and this operator is supose to do nothing if you pass 0. So by this fact, new can't return 0 becouse there will be no way to delete that pointer, and by that, non empty vector can't return begin() that points to 0.

Conclusion:

If above is right decrementing interator that points at vector::begin() should be safe, since internal memory of the vector is continouse.

Am I right?

ULTIMATE ANSWER

Even if it works now and will be working in the future it is undefined behavour according to the standard. If you do this, you are doing this on your own risk. See this simmilar question for more informations.

For the purpose of your question, you can probably simplify your example code to just `vector::iterator it = vec.begin(); it--;` — Oliver Charlesworth, Dec 16 '11 at 12:07
Maybe you should refactor so that you use reverse iterators for the backward motion. — Kerrek SB, Dec 16 '11 at 12:14
I can do that and i will probably use it, if i can't do what i showed in an example. — BeginEnd, Dec 16 '11 at 12:23
You can use `std::distance` (include ``) to calculate how many iterations you need to do and change your `while` loop to a `for` loop. — jrok, Dec 16 '11 at 12:28

Bo Persson · Accepted Answer · 2011-12-16T17:07:06.143

6

You cannot decrement an iterator passed begin, or compute begin() - 1.

While the implementation is required to have a position for one passed the last element, it is not required to have any address space available before begin. So begin() - 1 might not be a valid address (and definitely not a valid iterator).

On question number 2:

Even though if (p == 0) tests if the pointer is null, that doesn't mean that a null pointer has to be represented by all bits zero. It could also be all bits 1, or something else. Compiler magic will make the test work anyway.

Another example of an invalid address is that when you deallocate a large block of memory, the heap manager just could possibly also remove the corresponding virtual address space from your process.

Another memory block starting just after the deallocated space could then have an address, say, 0x10000 where the address 0x10000 - 1 does no longer exist. Some hardware, which uses dedicated address registers for pointers, is known to trap when loading an invalid pointer. It just could detect that 0x10000 - 1 isn't mapped to RAM anymore and abort your program. The standard is written to allow this, because such hardware exists.

We don't say that this is what normally happens on common desktop operating systems, just what could happen according to the language standard.

edited Dec 16 '11 at 17:07

answered Dec 16 '11 at 12:11

Bo Persson

90,663
31
146
203

I am not asking if it is a valid address, i have no intention to use this address in accessing memory where it points to. I am just asking if it can be used for comparacion purpose like `vector::end()` which is also invalid and can't be dereferenced. – BeginEnd Dec 16 '11 at 12:16
The problem is that there might be *no address at all* before `begin`. In a segmented memory, for example, the allocation might start at offset 0 in the segment. – Bo Persson Dec 16 '11 at 12:28
3

@beginend: What if your vector holds 100byte objects, and the vector begins at address 4? Begin()-1 would underflow. It is undefined to have a iterator before begin. Period. – Mooing Duck Dec 16 '11 at 17:06
@Bo Persson: i will accept this even if I do not like it and I am not convinced. If you're right having and operating on invalid pointer/dangling **but not accesing memory** where it points to could also lead to program termination? – BeginEnd Dec 16 '11 at 19:28
@Mooing Duck: having that iterator is undefined? or undefined is using it? And yes, it will underflow. But is it really important when I am using it in `!=` statement in **this** case? – BeginEnd Dec 16 '11 at 19:29
@BeginEnd - An old example of CPUs with separate address registers is the Motorola 68000 series. It didn't load pointers to unmapped memory. A more current example is the Intel x86 which has segment registers. The registers are just not reloaded by Windows or Linux, but the hardware for checking invalid pointers is still there. – Bo Persson Dec 16 '11 at 19:36
1

@BeginEnd: _Having_ that iterator is undefined. (Though, in every single processor/OS/compiler I know of, it would work fine...) The point is, restructure your code to go until it reaches the beginning, then do the beginning. – Mooing Duck Dec 16 '11 at 19:44
@Mooing Duck: yes if it is effect of the iterator operation (ex: incrementing past the end), but resizing `vector` can invalidate all obtained iterators. What then? – BeginEnd Dec 16 '11 at 20:19
@BeginEnd: You're right, what I said was not quite right. _Obtaining_ an iterator before the beginning is undefined (same with more-than-one past the end). _Dereferencing_ an invalid iterator is also undefined. – Mooing Duck Dec 16 '11 at 20:55

Substraction or decrement random access iterator pointing to begin

1 Answers1

Linked

Related