c++iteratordecrement

Subtraction or decrement random access iterator pointing to begin


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 because there is a subtraction from begin() and iterator it can be subtracted 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 internally point to memory at address 0, and I was thinking that it is the end, but all containers depend on standard allocator. This allocator depends on new operator. And also, there is no information that new will never return 0. But standard allocator depends also on delete operator and this operator is supposed to do nothing if you pass 0. So by this fact, new can't return 0 because 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 iterator that points at vector::begin() should be safe, since internal memory of the vector is continuous.

Am I right?

ULTIMATE ANSWER

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


Solution

  • 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.