title: Combining two lists by key using Thrust
body: <p>Given two key-value lists, I am trying to combine the two sides by matching the keys and applying a function to the two values when the keys match. In my case I want to multiply the values. A small example to make it more clear:</p>
  
  <pre><code>Left keys:   { 1, 2, 4, 5, 6 }
  Left values: { 3, 4, 1, 2, 1 }
  
  Right keys:   { 1, 3, 4, 5, 6, 7 };
  Right values: { 2, 1, 1, 4, 1, 2 };
  
  Expected output keys:   { 1, 4, 5, 6 }
  Expected output values: { 6, 1, 8, 1 }
  </code></pre>
  
  <p>I have been able to implement this on the CPU using C++ using the next code:</p>
  
  <pre><code>int main() {
      int leftKeys[5] =   { 1, 2, 4, 5, 6 };
      int leftValues[5] = { 3, 4, 1, 2, 1 };
      int rightKeys[6] =   { 1, 3, 4, 5, 6, 7 };
      int rightValues[6] = { 2, 1, 1, 4, 1, 2 };
  
      int leftIndex = 0, rightIndex = 0;
      std::vector&lt;std::tuple&lt;int, int&gt;&gt; result;
      while (leftIndex &lt; 5 &amp;&amp; rightIndex &lt; 6) {
          if (leftKeys[leftIndex] &lt; rightKeys[rightIndex]) {
              leftIndex++;
          }
          if (leftKeys[leftIndex] &gt; rightKeys[rightIndex]) {
              rightIndex++;
          }
          result.push_back(std::make_tuple(leftKeys[leftIndex], leftValues[leftIndex] * rightValues[rightIndex]));
          leftIndex++;
          rightIndex++;
      }
  
      // Print results
      for (int i = 0; i &lt; result.size(); i++) {
          std::cout &lt;&lt; "Key: " &lt;&lt; std::get&lt;0&gt;(result[i]) &lt;&lt; "; Value: " &lt;&lt; std::get&lt;1&gt;(result[i]) &lt;&lt; "\n";
      }
  }
  </code></pre>
  
  <p>However, I have the input keys and values in Thrust's <code>device_vector</code>s and I need the results on the GPU as well. Therefore it would be more efficient if I did not need to copy all inputs to the host and all outputs back to the device. </p>
  
  <p>The problem is that I cannot find a Thrust function that can be used to combine two lists using a set of keys (and apply a function to both values). Does such a function exist or is there an easy way to implement it myself of should I just do this on the host?</p>
  
  <p><strong>Update:</strong></p>
  
  <p>The following assumptions can be made about the input:</p>
  
  <ul>
  <li>The keys are always sorted.</li>
  <li>No duplicate keys exist within a single list (between the lists, duplicate keys of course do exist, otherwise the result would be empty).</li>
  </ul>
  
  <p><strong>Update 2:</strong></p>
  
  <p>While implementing the second approach in @Robert's answer I get stuck at the transformation. My code so far is below:</p>
  
  <pre><code>struct multiply_transformation : public thrust::binary_function&lt;std::tuple&lt;int, int&gt;, std::tuple&lt;int, int&gt;, std::tuple&lt;int, int&gt;&gt;
  {
      __host__ __device__
          thrust::tuple&lt;int, int&gt; operator()(thrust::tuple&lt;int, int&gt; d_left, thrust::tuple&lt;int, int&gt; d_right)
      {
          if (thrust::get&lt;0&gt;(d_left) == thrust::get&lt;0&gt;(d_right)) {
              return thrust::make_tuple(thrust::get&lt;0&gt;(d_left), thrust::get&lt;1&gt;(d_left) * thrust::get&lt;1&gt;(d_right));
          }
          return thrust::make_tuple(-1, -1);
      }
  };
  
  
  thrust::device_vector&lt;int&gt; d_mergedKeys(h_leftCount + h_rightCount);
  thrust::device_vector&lt;int&gt; d_mergedValues(h_leftCount + h_rightCount);
  thrust::merge_by_key(d_leftCountKeys.begin(), d_leftCountKeys.begin() + h_leftCount,
      d_rightCountKeys.begin(), d_rightCountKeys.begin() + h_rightCount,
      d_leftCounts.begin(), d_rightCounts.begin(), d_mergedKeys.begin(), d_mergedValues.begin());
  
  typedef thrust::tuple&lt;int, int&gt; IntTuple;
  thrust::zip_iterator&lt;IntTuple&gt; d_zippedCounts(thrust::make_tuple(d_mergedKeys.begin(), d_mergedValues.begin()));
  thrust::zip_iterator&lt;IntTuple&gt; d_zippedCountsOffset(d_zippedCounts + 1);
  
  multiply_transformation transformOperator;
  thrust::device_vector&lt;IntTuple&gt; d_transformedResult(h_leftCount + h_rightCount);
  thrust::transform(d_zippedCounts, d_zippedCounts + h_leftCount + h_rightCount - 1, d_zippedCountsOffset, d_transformedResult.begin(), transformOperator);
  </code></pre>
  
  <p>However, I get the error that no overloaded function <code>thrust::transform</code> matches the argument list. In the above code <code>h_leftCount</code> and <code>h_rightCount</code> are the sizes of the left and right inputs. <code>d_leftCountKeys</code>, <code>d_rightCountKeys</code>, <code>d_leftCounts</code>, and <code>d_rightCounts</code> are <code>thrust::device_vector&lt;int&gt;</code>. </p>