C++ Iterators: How to find the index for a heapsort

Question

Let's say I have a vector to sort:

std::vector v{9, 8, 0, 2, 7, 3, 2, 1}

Suppose I want to start sorting at the third element (index 2) until the end, and so I have an iterator pointing to 0 for begin and past 1 for end. If I use indices and pass into a function the index of the current element, to find the left child of "0" I would use 2*index+1.

Let "iter" be the iterator pointing to 0, at index 2. The following:

iter+1

would move the iterator so that *iter will now equal 2. However, I can't move the iterator to the left child by:

2*iter+1

How can I work around this and move the iterator to the right position? Is there a way to find the index of the iterator?

Answer 1

You can use std::distance. For example:

auto index = std::distance(v.begin(), iter);

Quoting:

If it is a random-access iterator, the function uses operator- to calculate this. Otherwise, the function uses the increase operator (operator++) repeatedly.

Answer 2

std::vector's iterator is a random access iterator, so the index of the iterator itr is itr - vec.begin()