title: C/C++ - Efficient way to compare two lists and find missing elements
body: <p>I have two lists, L<sub>1</sub> and L<sub>2</sub>, of data containing multiple elements, each unique, of an abstract data type (ie: <code>structs</code>). Each of the two lists:</p>
  
  <ul>
  <li>May contain between zero and one-hundred (inclusive) elements.</li>
  <li>Contains no duplicate elements (each element is unique).</li>
  <li>May or may not contain elements in the other list (ie: L<sub>1</sub> and L<sub>2</sub> might be identical, or contain completely different elements).</li>
  <li>Is not sorted.</li>
  <li>At the lowest level, is stored withing a <code>std::vector&lt;myStruct&gt;</code> container.</li>
  </ul>
  
  <p>What I am typically expecting is that periodically, a new element is added to L<sub>2</sub>, or an element is subtracted/removed from it. I am trying to detect the differences in the two lists as efficiently (ie: with minimal comparisons) as possible:</p>
  
  <ul>
  <li>If an entry is not present in L<sub>2</sub> and is present in L<sub>1</sub>, carry out one operation: <code>Handle_Missing_Element()</code>.</li>
  <li>If an entry is present in L<sub>2</sub> and not present in L<sub>1</sub>, carry out another operation: <code>Handle_New_Element()</code>.</li>
  </ul>
  
  <p>Once the above checks are carried out, L<sub>1</sub> is set to be equal to L<sub>2</sub>, and at some time in the future, L<sub>2</sub> is checked again.</p>
  
  <p>How could I go about finding out the differences between the two lists? There are two approaches I can think of:</p>
  
  <ol>
  <li>Compare both lists via every possible combination of elements. Possibly O(n<sup>2</sup>) execution complexity (horrible).</li>
  </ol>
  
  <hr>
  
  <pre><code>bool found;
  for i in 1 .. L2-&gt;length()
    found = false;
    for j in 1 .. L1-&gt;length()
      if (L1[j] == L2[i]
        // Found duplicate entry
        found = true;
      fi
    endfor
  endfor
  </code></pre>
  
  <ol start="2">
  <li>Sort the lists, and compare the two lists element-wise until I find a difference. This seems like it would be in near-linear time. The problem is that I would need the lists to be sorted. It would be impractical to manually sort the underlying vector after each addition/removal for the list. It would only be reasonable to do this if it were somehow possible to force <code>vector::push_back()</code> to automatically insert elements such that insertions preseve the sorting of the list.</li>
  </ol>
  
  <p>Is there a straightforward way to accomplish this efficiently in C++? I've found similar such problems, but <a href="https://stackoverflow.com/questions/5225820/compare-two-vectors-c">I need to do more than just find the intersection of two sets</a>, or do such a test with just a set of integers, where sum-related tricks can be used, as I need to carry out different operations for "new" vs "missing" elements.</p>
  
  <p>Thank you.</p>