Iterator invalidation / Quicksort bug

[mbozzi]

I am writing a quicksort for an exercise. I gave it a shot, and it didn't work. I just spent the past few hours staring at it, and still have no clue what's wrong. My guess is that I'm invalidating my pivot iterator, but I don't know where.

After reducing it nearly all the way down to a working example I found online at ( http://en.cppreference.com/w/cpp/algorithm/partition ) I came up with this:

template <typename Iterator, typename Comp> void
  quicksort(Iterator const begin, Iterator const end, Comp const comp) {
    if (begin != end) {
      auto const middle_it = std::distance(begin,end) / 2;
      auto const pivot_it  = std::next(begin, middle_it);

      Iterator middle1 = std::partition(begin, end,
                                     [=] (auto const& element) {
                                       return comp(element, *pivot_it);
                                     });
      Iterator middle2 = std::partition(middle1, end,
                                     [=] (auto const & element) {
                                       return ! comp(*pivot_it, element);
                                     });

      quicksort(begin, middle1, comp);
      quicksort(middle2, end, comp);
    }
  }

Which is wrong for some reason --- on a short (~16 element) vector shuffled randomly, the output won't be fully sorted most of the time. Oops.

Here's the thing -- if I change
auto const pivot_it = std::next(begin, middle_it); to auto const pivot = *std::next(begin, middle_it); (i.e., I make pivot a value instead of an iterator), and remove the dereference operators on pivot in the lambda functions, the sorting routine works.

Any ideas why?

Here's my code:

# include <algorithm>
# include <iterator>

namespace {
  template <typename Iterator, typename Comp> void
  quicksort(Iterator const begin, Iterator const end, Comp const comp) {
    if (begin != end) {
      auto const middle   = std::distance(begin,end) / 2;
      auto const pivot = std::next(begin, middle);

      Iterator middle1 = std::partition(begin, end,
                                     [=] (auto const& element) {
                                       return comp(element, *pivot);
                                     });
      Iterator middle2 = std::partition(middle1, end,
                                     [=] (auto const & element) {
                                       return ! comp(*pivot, element);
                                     });

      quicksort(begin, middle1, comp);
      quicksort(middle2, end, comp);
    }
  }
}

# include <random>
# include <iostream>
# include <vector>
int main (int, char **) {
  std::vector <int> foo { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };

  std::random_device rd;
  std::mt19937 g(rd());
  std::shuffle(foo.begin(), foo.end(), g);

  std::cout << "shuffled array" << "\n";
  for (auto e: foo) { std::cout << e << " "; }
  std::cout << "\n\n";

  std::cout << "sorted array" << "\n";
  quicksort(foo.begin(), foo.end(), std::less<int>{});
  for (auto e: foo) { std::cout << e << " "; }
  std::cout << "\n";

  std::cout << "Is sorted?  " << std::boolalpha 
            << std::is_sorted(foo.begin(), foo.end(), std::less<int>{}) << "\n";
}

[cire]

This code won't even compile. What is the actual code you're using?

In...

 template <typename Iterator, typename Comp> void
  quicksort(Iterator const begin, Iterator const end, Comp const comp) {

...why are you using const iterators? Why are you using a const function object for comparison? Copies of all these things are being fed to the function. Do you really mean to disallow changes to those local copies?

[mbozzi]

Oops - just a typo on line 46. It's fixed.

... why are you using const iterators? Why are you using a const function object for comparison? Copies of all these things are being fed to the function. Do you really mean to disallow changes to those local copies?

I do, because I have no intention of changing them. For instance, I don't intend to alter my comparison function in the middle of my sorting routine. That would be bad. :)

Perhaps it would be smarter to pass those objects by constant reference.
I don't think that's an issue at the moment, though (since iterators can be copy-constructed without becoming invalidated). But maybe the issue is somewhere else. Let me take a look with GDB.

[cire]

I do, because I have no intention of changing them. For instance, I don't intend to alter my comparison function in the middle of my sorting routine. That would be bad. :)

You're also not allowing the comparison function object to modify its own state. That may be unnecessarily restrictive.

But maybe the issue is somewhere else.

What I mentioned there isn't an "issue" I was just curious about why you were doing so when you aren't, for instance, making it impossible to modify what the iterator refers to which would actually have some meaning for me, rather than making it impossible to modify a local-to-function-copy.

[Edit: That's silly if I reread that in the context of the OP. ]

[mbozzi]

That's an interesting point about the comparision object. But then is there a way to make sure the callee doesn't touch it, but allow the functor/closure to manage its own state?

...when you aren't, for instance, making it impossible to modify what the iterator refers to...

Well, what you said is what I intended, but clearly I'm not thinking today :D.

Uhh, how could you enforce that on the callee side? I suppose you would have to have the caller tell you which container they were using, which I guess causes some loss of generality.

What I mentioned there isn't an "issue"

Oh, I was referring to iterator invalidation, not the "const" shenanigans.

[cire]

I think the fundamental mistake you are making is an assumption about the position of the pivot element. The pivot element can be anywhere in the right-hand partition and the value of *pivot in your second call to std::partition will likely be different than it was for the first (and I'm not entirely certain what you were hoping to accomplish with it.)

In other words, you don't really have a pivot element. What you have is a pivot value and you lose track of the corresponding element.

Keeping tabs on the pivot element:

    template <typename Iterator, typename Comp>
    void quicksort(Iterator const begin, Iterator const end, Comp const comp) {
        using std::next; using std::prev; using std::iter_swap;

        if (std::distance(begin, end) < 2) return;

        auto pivot_value = *begin;

        auto pivot = std::partition(next(begin), end, [=](auto v) { return comp(v, pivot_value); });

        auto lhs_end = prev(pivot);

        iter_swap(lhs_end, begin);

        quicksort(begin, lhs_end, comp);
        quicksort(pivot, end, comp);
    }

[mbozzi]

Yeah -- I'm moving the value at the real pivot around when I call partition.

Thanks. :-)