Tech Off Post

Single Post Permalink

View Thread: (STL) move_if algorithm, what's your take on it ?
  • User profile image

    > 1. I'm not sure what the difference is between forward iterators and input iterators.
    > Isn't forward iterator the most generic iterator ? I'll have to refresh my c++ knowledge.

    The read-only iterator hierarchy goes: input, forward, bidi, random. Input iterators are single-pass iterators, which means that this does NOT work for them:

    InIt i = ...; // get i from somewhere
    Val v1 = *i; // get a value from i
    InIt old = i; // copy i, this is OK so far but bogus code is imminent
    ++i; // increment i, still OK so far, but old is now UNUSABLE
    Val v2 = *old; // FORBIDDEN!!!

    The best example of an input iterator is istream_iterator. As you read values, they're consumed from the stream, so you can't go back and replay them.

    Forward iterators are multi-pass iterators, merely constrained to go forwards and never backwards. The best example of a forward iterator is forward_list::iterator (i.e. a singly-linked list).

    > I based move_if on how remove_if works.

    Ah, that wasn't clear to me. Your new implementation is much better; here are some notes:

    5. Your (first == last) check is unnecessary. When an algorithm is inherently correct for empty ranges, you should let it automatically work.

    6. You don't actually need new_end - you can use first instead.

    7. is_prime is really is_even!

    8. count_if() followed by move_if() performs 2N tests. Instead, move_if() to back_inserter() would perform N tests. (In that case, the destination n should start out empty.) If you're concerned about reallocation overhead (which usually isn't a big deal), you can say n.reserve(v.size());.

    9. print_vec_int should take const vector<int>&.

    10. But at the same time, there's no reason to take const int&.

    > Your suggestion of using make_move_iterator() with copy_if() while the moving works it doesn't fix up the input container.

    Yes, that was intentional. If I wasn't too concerned about consuming a little extra space, I would use partition_copy() with make_move_iterator() and back_inserter() to 2 output vectors, then swap one of the outputs with the input.