For Random Access Iterator (vector iterator), are the iterators C++ style pointers?

Question

I have the following code to randomize the elements in a list container:

    #include <vector>
    #include <list>
    #include <iterator>
    #include <algorithm>
    #include <iostream>
    using namespace std;

        template<class RandomAccesIterator>
        void randomize(RandomAccesIterator iterBegin, RandomAccesIterator iterEnd)
        {
            while (iterBegin != iterEnd)
            {
                iter_swap(iterBegin, iterBegin + rand() % (iterEnd - iterBegin));
                ++iterBegin;
            }
        }

And then later in main():

int main()
{
    //container used as to apply algorithm to.
    list<int> List = {34,77,16,2,35,76,18,2};

    //randomize example.
    cout << "calling randomize on sorted vector: " << endl;
    List.sort();
    vector<int> temp(List.begin(), List.end());
    cout << "before randomize: " << endl;
    for (vector<int>::iterator it = temp.begin(); it != temp.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;

    randomize(temp.begin(),temp.end());
    cout << "after randomize: " << endl;
    for (vector<int>::iterator it = temp.begin(); it != temp.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl<<endl;
    return 0;
}

I had a couple of questions:

1. I believe performing iterEnd - iterBegin (as shown in the template function) is a valid operation, because both iterEnd and iterBegin are C++ style pointers. and subtracting these pointers gives the distance between them. Am I correct?

2. I tried the following in the immediate window:

iterEnd
{-33686019}
    [ptr]: 0x00ba4f78 {-33686019}
    [Raw View]: {...}

it means iterEnd is a pointer, whose value is 0x00ba4f78, and it points to the garbage value of -33686019. I believe I am correct here?

So, the iterator is a pointer, for random access iterators. Is it true for all iterator types (Input/output iterators, Forward iterators, BiDirectional iterators)? If those iterators are not C++ style pointers, then what are those?

3. I also tried the following in the immediate window:

&iterEnd
0x006ff368 {-33686019}
    [ptr]: 0x00ba4f78 {-33686019}
    [Raw View]: 0x006ff368 {...}
&&iterEnd
expected an expression

Why is &iterEnd giving me an address? It should give me the message "expected an expression", as, &&iterEnd does.

4. How are random access iterators implemented? - I am asking because iterEnd gives me a pointer value and, &iterEnd also gives me a (different) pointer value. Is the random access iterator a pointer within a pointer?

Answer 1

For Random Access Iterator (vector iterator), are the iterators C++ style pointers?

Short answer -- it depends on the compiler.

The internals of a vector iterator is implementation-defined. The std::vector<T>::iterator could have operator - overloaded, thus it gives the illusion of pointer subtraction. Thus if you assume that vector iterators are simple pointers, writing code assuming they are simple pointers will break using various compilers, while for other compilers it will compile successfully.

One such famous case is Visual C++, where in version 6.0, vector iterators were simple pointers, thus many authors at that time using that compiler would write code with the assumption that a std::vector<T>::iterator was just a T*. The code compiled successfully and worked correctly due to the fact that vector iterators were implemented as pointers.

An example would be something like this:

#include <vector>

void foo(char *c)
{
}

int main()
{
   std::vector<char> vc;
   foo(vc.begin());
}

No compile errors, since vc.begin() was a simple char *.

Then came the subsequent versions of Visual C++, and that code that used to compile successfully under 6.0 is now broken. The std::vector<T>::iterator was no longer a simple T*, but a struct. A lot of code based on the (faulty) reasoning of an iterator being a simple pointer had to be changed for Visual C++ > version 6.0.