# Heapsort implementation in C++14

Please review the following implementation of heapsort and pay attention to the following:

1. Have I correctly chosen the names InputIt and BidirIt for my iterators?
2. Is there a way to make the initialise iterator and then advance it pattern occupy one line instead of two?
3. Is the it != ix - 1 comparison of iterators ok?

Here is the code:

#include <iterator>
#include <functional>

template<
class InputIt,
class Key = std::less_equal<
std::iterator_traits<InputIt>::value_type
>
>
void plunge(
const InputIt ix, // first element of heap
const InputIt iy, // one-past last element of heap
const InputIt iz, // element to be plunged
Key key = Key()   // comparison key to use (up or down)
) {
auto ii = iz;
auto il = ix;
std::advance(il, 2 * std::distance(ix, ii) + 1);

while (il < iy) {
auto ir = il + 1;

auto it = ir < iy && key(*ir, *il) ? ir : il;

if (key(*ii, *it)) {return;}

std::iter_swap(ii, it);
std::     swap(ii, it);

il = ix;
std::advance(il, 2 * std::distance(ix, ii) + 1);
}
}

template<
typename BidirIt,
typename Key = std::greater_equal<
std::iterator_traits<BidirIt>::value_type
>
>
void heapsort(const BidirIt ix, const BidirIt iy, Key key = Key()) {
auto it = ix;

for (; it != ix - 1; --it) {
plunge(ix, iy, it, key);
}

for (it = iy - 1; it != ix - 1; --it) {
std::iter_swap(ix, it);
plunge(ix, it, ix, key);
}
}

• Just a comment not answering the question: there are also heap operations in the standard, such as std::sort_heap. – Juho Jul 29 '16 at 21:48
• Look at std::next() for turning initialize-then-advance into one line. – user2296177 Jul 31 '16 at 8:20
• I updated the answer with quote from standard. I recommend you to read the whole paragraphs that begin with 24.2 to enrich your knowledge about iterators and write standard conformant code. – Incomputable Aug 8 '16 at 17:37
• If you have stumbled upon this question, this other one might be interesting too: stackoverflow.com/questions/24650626/… – alisianoi Aug 20 '16 at 12:41

1. Input iterator is not suitable for your plunge function. The reason is in std::advance(). It increments the iterators, which invalidates all previous ones. Bidirectional iterators are ok.
2. Use std::next() as mentioned in the comment by user2296177.
3. No. Only random access iterators are mandated to support the operation.

Here is the piece of C++ 14 standard that proves answer #1.

Paragraph 24.2.3 of N4296 (Input Iterators). Note from table 107 - Input Iterator requirements (in addition to Iterator).

Expression:

++r;


pre: r is dereferenceable. post: r is dereferenceable or r is past-the-end. post: any copies of the previous value of r are no longer required either to be dereferenceable or to be in the domain of ==.

where r is Input Iterator. Additionally, it is stated that post increment has the same effect. Either pre or post increment should be used to implement std::distance(), so it invalidates all copies of Input Iterators according to the standard.

template<
class InputIt,
class Key = std::less_equal<
std::iterator_traits<InputIt>::value_type
>
>


Combo of first and last if preferred when referring to range. value is used to refer to some instance of T. ii and il make things even worse. Don't be lazy to type!