CODEWITHSUNDEEP
c++algorithmsortingiterator
Hasek
Hasek

Reputation: 239

Rearrange by predicate using iterators

In a function with given signature I want to rearrange elements of sequence [first, last) in a such way, that all elements satisfying predicate are placed before ones that don't and return an iterator to a first element that doesn't satisfy given predicate.

My algorithm is

My code

template<class Iterator, class Predicate>
Iterator Rearrange(Iterator first, Iterator last, Predicate pred) {
  auto res = first;
  if (first == last) {
    ;
  }
  else {
    auto run = first;
    auto end = last;
    auto tmp = *first;
    while (run != end) {
      if (pred(*run) == false) {
      again: tmp = *(--end);
    *end = *run;
    *run = tmp;
    if (pred(*run) == false) {
      goto again;
    }
      }
      ++run;
    }
  }
  return res;
}

it gives me

terminate called after throwing an instance of 'std::range_error'
  what():  dereferencing end of sequence
Aborted

which I can't find and understand. Namely, I can read that somewhere I'm trying to dereference element outside of container, but can't see it in my program. Can anyone help me fix a coding error or improve logic of my algorithm?

Upvotes: 2

Views: 191

Answers (1)

Angew is no longer proud of SO
Angew is no longer proud of SO

Reputation: 171167

If the input range is non-empty and no element in it satisfies the predicate, your code will be stuck in the goto loop and not reach the while again. Eventually, --end will take end before first.

If this is a learning exercise, I suggest you get rid of goto; you don't want to be learning bad practices and while goto can have rare legitimate uses, replacing loops is not one of them. Also, the dance with tmp can be replaced with std::swap.

If this is not a learning exercise, just use std::partition which does exactly what you want.

Upvotes: 3

Related Questions