We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Lower Bound-STL
You are viewing a single comment's thread. Return to all 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, butvec.begin()
is also an iterator - thebegin
iterator always references the location of the first element of vectorvec
. 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:
This produces this output on HackerRank:
We see the raw memory addresses of the first element in
vector<int> v
atv[0]
and the 3rd element located atv[2]
. We check the byte-size of the int type and get the result4
. 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 ofvec.begin()
as a pointer to the first element, you can see why doingvIt - vec.begin()
is necessary to get the distance from the beginning thatvIt
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
andv.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 thev.begin()
pointer to the start of the vector from thevIt
pointer's current location - this will give you the distance from the beginning of the vector that thevIt
is currently looking at - aka the "index" you're looking for.