Making move_if support input iterators will make it become "partition_move" or did you have something else in mind ?

With find_if  in move_if it'll be N+1, is that correct ?
Since one item is tested twice. 

#include <algorithm>
#include <vector>
#include <iostream>
#include <iterator>
#include <sstream>

using namespace std;

template <typename FwdIt, typename OutIt, typename Predicate>
inline FwdIt move_if(FwdIt first, FwdIt last, OutIt out, Predicate pred)
    first = find_if(first, last, pred);

    for (auto i = first; i != last; ++i)
        if (pred(*i)) // Should it move it ?
            *out++ = move(*i); // Move it.
            *first++ = move(*i);
    return first;

// move_if have become partition_move
template <typename InIt, typename OutIt1, typename OutIt2, typename Predicate>
inline pair<OutIt1, OutIt2> move_if(InIt first, InIt last, OutIt1 out_false, OutIt2 out_true, Predicate pred)
    for (auto i = first; i != last; ++i)
        if (pred(*i)) // Should it move it ?
            *out_true++ = move(*i); // Move it.
            *out_false++ = move(*i);
    return make_pair<OutIt1, OutIt2>(out_false, out_true);

int main()
    auto is_even = [](const char c){return (c % 2) == 0;};

    std::istringstream iss("The quick brown fox jumps over the lazy dog");
    std::istream_iterator<char> begi(iss), endi;

    vector<char> n_f, n_t;
    move_if(begi, endi, back_inserter(n_f), back_inserter(n_t), is_even);

    auto print_vec_char = [](const vector<char> &v) {
        cout << "[" << v.size() << "]";
        for_each(v.cbegin(), v.cend(), [](const char c) {
            cout << " " << c;
        cout << endl;

/* Output:
[19] e q u i c k o w o u m s o e e a y o g
[16] T h b r n f x j p v r t h l z d


> I was assuming that the whole source range would be discarded.

 How would you do it if the source range would be used ?


I a pedant so making my code as efficient as possible is a goal.

Using move_if is more efficient because you need one less container and if you really needed to preserve the input container then partition_copy would do the trick.