Lower Bound-STL

  • + 3 comments

    I struggled with this as well, and I'm not 100% clear on the internals of an iterator - but I believe I understand generally what's happening. If someone reads this and can fill in specifics or correct any misunderstanding I have, please jump in. I apologize in advance for my inability to be more succinct in explaining my thought process.

    There's a TL;DR at the bottom if you are familiar with pointer arithmetic already:

    First of all - vIt is an iterator that you are using to traverse the vector, but vec.begin() is also an iterator - the begin iterator always references the location of the first element of vector vec. The way I've accepted to look at this, for now, is to just think of iterators as pointers. They are more complex than raw pointers, but they do seem to behave the same when it comes to pointer arithmetic.

    For example, let's look at elements of an integer vector and do some arithmetic on memory locations:

    cout << "Address of v[2]: " << &v[2] << endl;
    cout << "Address of v[0]: " << &v[0] << endl;
    cout << "Size of int type in bytes: " << sizeof(int) << endl;
    cout << "Difference between addresses: " << &v[2] - &v[0] << endl;
    

    This produces this output on HackerRank:

    Address of v[2]: 0x55ded6944c48
    Address of v[0]: 0x55ded6944c40
    Size of int type in bytes: 4
    Difference between addresses: 2
    

    We see the raw memory addresses of the first element in vector<int> v at v[0] and the 3rd element located at v[2]. We check the byte-size of the int type and get the result 4. If we look at the addresses, we can see that they are 8 bytes apart from each other in memory - which makes sense because each int takes up 4 bytes. If you do the math on the memory locations and subtract them from each other, do you not get 8 as an answer, instead you get 2 as an answer because the arithmetic accounts for the byte-size of the type of the math you're doing. It tells you that they're 2 integer-sized locations apart from each other in memory, which correlates to their distance from each other as an index in the vector.

    I just took this understanding of arrays/vectors and pointer arithmetic, and I migrate that into my grasp of iterators. If you think of the iterator vIt as simply pointing to the memory location of the current value it is looking at, and you think of vec.begin() as a pointer to the first element, you can see why doing vIt - vec.begin() is necessary to get the distance from the beginning that vIt is now at - a very similar situation to what happened with &v[2] - &v[0] discussed above.

    I tried to look for a way to print vIt and v.begin() as strings, to try to "see inside" so to speak, but it's not possible from what I can find. You can however do things like *vIT to see what value it's pointing at. I would suggest just playing around with reference & and de-reference * operators on things like arrays, vectors, and iterators and looking at what they contain, do some + and - on pointers, and it might help de-mystify it a bit.

    To sum it up/TL;DR:

    You can't print out iterators as a string directly, and it wouldn't help much if you could since vIt never contains the "index" you're looking for anyway, it just points to the current value in the collection it's traversing. If you de-reference it, you'll get the value it's pointing at inside the vector - still not the index. To get the index, you need to do pointer arithmetic and subtract the v.begin() pointer to the start of the vector from the vIt pointer's current location - this will give you the distance from the beginning of the vector that the vIt is currently looking at - aka the "index" you're looking for.