CODEWITHSUNDEEP
c++
Roy
Roy

Reputation: 3624

How do you find the iterator in the middle of two iterators?

I'm trying to convert my implementation of quicksort into a template that can be used with other containers besides a vector.

Originally I used indexes to find the middle index, e.g. (first + last) / 2. How can I find the middle of two iterators?

Upvotes: 12

Views: 11485

Answers (4)

vladinkoc
vladinkoc

Reputation: 967

To find middle iterator you should use: 

first + (last - first) / 2

Upvotes: 0

StilesCrisis
StilesCrisis

Reputation: 16290

std::distance can measure the distance between two iterators as efficiently as possible.

std::advance can increment an iterator as efficiently as possible.

I still wouldn't want to quicksort a linked list, though :)

Upvotes: 16

Keldon Alleyne
Keldon Alleyne

Reputation: 2130

How about something like this?

bool isMovingFirst = true;
while(first != last) {
  if(isMovingFirst) {
    ++first;
  } else {
    --last;
  }
  isMovingFirst = !isMovingFirst;
}

Upvotes: 1

Anycorn
Anycorn

Reputation: 51465

use:

http://www.cplusplus.com/reference/std/iterator/distance/

and

http://www.cplusplus.com/reference/std/iterator/advance/

Upvotes: 5

Related Questions