Algorithms which assume sorted input should have _by_key variants

[jaredhoberock]

In practice, this would mean adding _by_key set algorithm variants.

This has value beyond Thrust; note how awkward [1] taking the difference of two std::sets is.

[1] http://stackoverflow.com/questions/7706602/how-to-subtract-one-list-of-map-keys-from-another-and-get-new-map-map-a-mab-b/7706740#7706740

How should the key and value sequences be ordered?

Option 1: [first1, last1) and [first2, last2) are the left and right key sequences

template <typename InputIterator1,
typename InputIterator2,
typename InputIterator3,
typename InputIterator4,
typename OutputIterator1,
typename OutputIterator2,
typename StrictWeakOrdering>
thrust::pair<OutputIterator1,OutputIterator2>
merge_by_key(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
InputIterator3 first3,
InputIterator4 first4,
OutputIterator1 output1,
OutputIterator2 output2,
StrictWeakOrdering comp);

Option 2: [first1, last1) and [first3, last3) are the left and right key sequences

template <typename InputIterator1,
typename InputIterator2,
typename InputIterator3,
typename InputIterator4,
typename OutputIterator1,
typename OutputIterator2,
typename StrictWeakOrdering>
thrust::pair<OutputIterator1,OutputIterator2>
merge_by_key(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2,
InputIterator3 first3, InputIterator last3,
InputIterator4 first4,
OutputIterator1 output1,
OutputIterator2 output2,
StrictWeakOrdering comp);

AFAICT there's no prior art within Thrust (in the public interface). Internally we used Option 1 for merge_by_key, but I didn't give it much consideration back when.

Forwarded from http://code.google.com/p/thrust/issues/detail?id=393

[alliepiper]

merge_by_key exists today.