title: Find first match in two sorted ranges using STL
body: <p>I have two sorted ranges. I would like to find the first matching element in the ranges, if any.</p>
  <p>The <strong>operations (on sorted ranges)</strong> sections in <a href="https://en.cppreference.com/w/cpp/algorithm" rel="nofollow noreferrer">cppreference</a> do not appear to contain exactly what I want. <code>std::set_intersection</code> is close, but it finds <em>all</em> the matching elements.</p>
  <p>Of course I could write my own template algorithm, but it's a bit of a chore to write algorithms up to the STL quality standard.</p>
  <p>Another option is to somehow adapt <code>std::set_intersection</code> by using a special output iterator. We could write something like</p>
  <pre><code>template &lt;typename T&gt;
  struct OneElementIter
  {
      T &amp;operator*() {
          if (full) return dummy;
          full = true;
          return t;
      }
      void operator++() {}
      bool full = false;
      T t;
      T dummy;
  };
  </code></pre>
  <p>and use it for the output iterator of <code>std::set_intersection</code>. This will waste effort scanning the input ranges past the first match, but it's still O(n) complexity.</p>
  <p>However, writing STL-quality iterators is a chore too. I'm not aware of anything in <code>&lt;iterator&gt;</code> that can do this without writing a new iterator class.</p>
  <p>If the STL container library included a fixed-size FIFO queue whose <code>push_back</code> is a no-op when full, then we could use a <code>std::back_inserter</code> on a queue of size <code>1</code> as the output iterator. But no such container exists.</p>
  <p>Is there any elegant way to do this with existing STL tools I'm missing?</p>