search

asherliu / thrust

Automatically exported from code.google.com/p/thrust
Apache License 2.0
0 stars 0 forks source link

Algorithms which assume sorted input should have _by_key variants #393

Closed GoogleCodeExporter closed 8 years ago

GoogleCodeExporter commented 8 years ago 
In practice, this would mean adding _by_key set algorithm variants.

Original issue reported on code.google.com by jaredhoberock on 9 Oct 2011 at 9:50

GoogleCodeExporter commented 8 years ago 
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

Original comment by jaredhoberock on 9 Oct 2011 at 9:52

GoogleCodeExporter commented 8 years ago

Original comment by jaredhoberock on 24 Jan 2012 at 1:03

GoogleCodeExporter commented 8 years ago 
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.

Original comment by wnbell on 24 Jan 2012 at 7:18

GoogleCodeExporter commented 8 years ago

Original comment by wnbell on 18 Feb 2012 at 8:10

GoogleCodeExporter commented 8 years ago 
Forwarded to https://github.com/thrust/thrust/issues/51

Original comment by jaredhoberock on 7 May 2012 at 8:55