Defining Iterators

I've been working my way through C++ primer and I've been experimenting on my own tinkering with some of the code in the book. It presents this code for a binary search of a sorted vector:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  int main() {

  std::vector<int> text{1,2,3,4,5,6,7,8,9,10};      // text is ordered
  auto beg=text.begin(),end=text.end();
  auto mid=beg+(end-beg)/2;
  int sought=5;  // search value
  while(mid!=end && *mid!=sought)
  {
  	if(sought<*mid)
  		end=mid;
  	else
  		beg=mid+1;
  	mid=beg+(end-beg)/2;
  }
}


In my own curiosity I was experimenting with defining iterators and using them with operators like is done with

 
auto mid=beg+(end-beg)/2;


and I am mainly curious why when I have a simpler definition, such as just dividing one iterator by a number like with

 
auto mid= end / 2;


I've come across various errors about operators not matching the operand or problems with mid not being able to be dereferenced depending on what I was trying. What is it about the relatively complex definition of beg+(end-beg)/2 that is functional whereas end / 2 and other simple operations like subtraction are not functional alone and why?
Last edited on
I can't possibly fathom what you're trying to accomplish here. But i will say that iterators are very fragile and if you change something in the vector (like deleting an element, adding elements) the iterators that existed could be destroyed (and most likely will be) . There is also no guarantee that iterators are sequential in memory. So when you want to make some kinda iterator swap you need to reference it with the text.begin() or text.end(). That and in a while loop you could have beg and end redefined each time around. I'm not even sure it theres any point in making one iterator equal to another does it result in an actual change in the array itself? from the simple test i did it doesn't appear to be so.

Last edited on
What is it about the relatively complex definition of beg+(end-beg)/2 that is functional whereas end / 2 and other simple operations like subtraction are not functional alone and why?
Iterators are similar to pointers. Several operation like division or addition (of pointer) don't make sense. The result is invalid.
Subtraction (of pointer) does make sense. The result is a numeric value (not a pointer) that determines the relation of the pointer. Adding a numeric value to a pointer is also useful. Hence only those operators that returns useful result are implemented.
 
beg+(end-beg)/2 


You can only add/subtract a number from an iterator type or subtract two iterators. If you add or subtract a number then the result is of type iterator. If you subtract 2 iterators you get a number which is the difference between them in terms of the underlying type units.

So in the above, end - beg gives a number which can be divided by 2 to give a number. This number is then added to beg which is an iterator type resulting in a type iterator.

 
end / 2


Here end is of type iterator and you can't divide an iterator by a number - hence an error.
Thanks for the responses. seeplus, your answer addresses exactly what I was wondering. That in the example when end-beg is done, it results in a numerical value rather than a iterator location, so then when it is divided and added to mid it is not actually iterator position information being added. This makes sense to me and has cleared up why I can't do those individual operations (such as adding two iterator positions together or dividing an iterators position in half) alone.

Big thanks to this forum in general. This is the second time I've used it after being intimidated from other sites and both times it has been very helpful to clear up confusion over process for me. cheers.
Ive been thinking about this for awhile now and I'd also like to point out that in your example program theres no checking to see if the resulting positions are outside of the range of the vector. Its possible to get an iterator that is out of bounds and an attempt to dereference it could result in an error. Its been awhile since I've dereferenced an invalid iterator so I forgot what happens.
boom!
Registered users can post here. Sign in or register to post.