0

I have a pointer to the vector iterator; I don't know what the vector is. Hence it - vec.begin() and std::distance(vec.begin(), it) are useless as I don't know what the vector vec is. I came to know that it - vec.begin() is a constant time algorithm. So I think definitely a numerical value of index is stored in a vector iterator as some private member. How to find the index without knowing the vector from its iterator?

Necktwi
  • 2,483
  • 7
  • 39
  • 62
  • 2
    No, a numerical value of `index` does not need to be stored in the iterator to make `it - vec.begin()` constant time. You can't get to the index through only one iterator. – Galik Aug 12 '16 at 05:33
  • @Galik how `it - vec.begin()` determines index? – Necktwi Aug 12 '16 at 05:46
  • "So I think definitely a numerical value of index is stored in a vector iterator as some private member". But a [vector iterator can be a pointer](http://en.cppreference.com/w/cpp/concept/RandomAccessIterator), so where would that have a private member? – Ami Tavory Aug 12 '16 at 06:17
  • _"how `it - vec.begin()` determines index?"_ The same way 5 - 3 determines that result is 2: simple pointer arithmetics – Revolver_Ocelot Aug 12 '16 at 07:34
  • @AmiTavory Yeah thats obvious. My desperation for index missed it. – Necktwi Aug 13 '16 at 19:12

2 Answers2

1

See this question: Converting a vector to an array - Is there a 'standard' way to do this?

The standard requires that vectors store their elements sequentially (Except for vectors of bools). What that means is that the iterator doesn't need to store the index of the data within the vector, just a pointer to its assigned element in the vector. The reason you can get the index by using it - vec.begin() is that you are comparing two different addresses of a vector of elements whose addresses are guaranteed to be consecutive. "vec.begin()" is simply a point of reference.

This is why you can basically get the "array" in a vector by using &theVector[0], because whenever several variables are guaranteed to have consecutive address assignments, that is exactly the same as an array.

Community
  • 1
  • 1
AlexKven
  • 138
  • 1
  • 9
0

Only aswer the last question "How to find the index without knowing the vector from its iterator?". And this is compiled by Visual Studio 2015 so watch out.

    std::vector<int> ints;
    ints.push_back(0);
    ints.push_back(1);
    ints.push_back(2);

    std::vector<int>::iterator it = ints.begin();
    ++it;
    ++it; // now it points to ints[2]

    int result_index = 0; // should output 2 later
    while (true)
    {
        std::vector<int>* cont = (std::vector<int>*)(it._Getcont());
        int* head = (cont->_Myfirst());
        int* current = it._Ptr;
        int index = current - head;
        if (index == 0)
        {
            break;
        }
        else
        {
            ++result_index;
            --it;
            continue;
        }
    }
    std::cout << result_index << std::endl; // output 2
Marson Mao
  • 2,935
  • 6
  • 30
  • 45
  • `_Getcont`, `_Myfirst`, `_Ptr`, Are they standard? – songyuanyao Aug 12 '16 at 06:52
  • @songyuanyao yeah they are, it's just normally nobody would use them :p – Marson Mao Aug 12 '16 at 06:58
  • @songyuanyao Ah, if you mean if it's standard then it maybe not, I'm compiling this using Visual Studio 2015, so I think these are Microsoft implementation only? – Marson Mao Aug 12 '16 at 07:01
  • 1
    That's what I want to say. The standard doesn't require iterator to hold a pointer to the container. So your code only works with VS. – songyuanyao Aug 12 '16 at 07:09
  • Yeah I think you're right, thanks for pointing this important issue. And I guess there's no standard way to know the index right? As I just searched the documentation and can't think of any method xD – Marson Mao Aug 12 '16 at 07:11
  • 1
    And IIRC iterator in VS hold pointers to container only when checked iterators are enabled (in debug builds) – Revolver_Ocelot Aug 12 '16 at 07:31