CODEWITHSUNDEEP
c++iterator
2013Asker
2013Asker

Reputation: 2058

C++ Iterators - Why do I have to add .begin() to get binary search middle point?

If I try to compile the following code it gives an error:

  vector<string> articles;

  articles.push_back("Article 1...");
  articles.push_back("Article 2...");
  articles.push_back("Article 3...");
  articles.push_back("Article 4...");

  vector<string>::iterator beg = articles.begin(), end = articles.end();
  vector<string>::iterator mid = (end - beg) / 2;

and only compiles if I change mid to:

  vector<string>::iterator mid = articles.begin() + (end - beg) / 2;

What does .begin() change in the initialization?

Also, shouldn't the following code give the middle point as well? (Added .begin() because it doesn't compile without it)

  vector<string>::iterator mid = articles.begin() + articles.size() / 2;

It gives the same results.

Thanks.

Upvotes: 1

Views: 596

Answers (1)

AnT stands with Russia
AnT stands with Russia

Reputation: 320531

end - beg gives you the distance between beg and end. It is a number, not an iterator. Then you divide it by 2 to get half of that distance. And then you have to convert that distance back into an iterator. For that you add it to beg

mid = beg + (end - beg) / 2

For example, if your vector has 10 elements in it, then (end - beg) / 2 will evaluate to 5. Now you have to create an iterator that points to 5th element in the vector. This is done as beg + 5.

You are right when you are saying that the same result can be obtained by adding half of the vector's size to the beginning iterator of the vector. However, as you said it yourself this is a part of iterative binary search algorithm, meaning that it will have to compute mid on each iteration of binary search with beg and end no longer pointing to the beginning and end of the original vector. This is why the beg + (end - beg) / 2 formula is more versatile way to compute the middle iterator.

Upvotes: 5

Related Questions