title: How can I return a copy of a vector containing elements not in a set?
body: <p>Suppose I have the following two data structures:</p>
  
  <pre><code>std::vector&lt;int&gt; all_items;
  std::set&lt;int&gt; bad_items;
  </code></pre>
  
  <p>The <code>all_items</code> vector contains all known items and the <code>bad_items</code> vector contains a list of bad items. These two data structures are populated entirely independent of one another.</p>
  
  <p>What's the proper way to write a method that will return a <code>std::vector&lt;int&gt;</code> contain all elements of <code>all_items</code> not in <code>bad_items</code>?</p>
  
  <p>Currently, I have a clunky solution that I think can be done more concisely. My understanding of STL function adapters is lacking. Hence the question. My current solution is:</p>
  
  <pre><code>struct is_item_bad {
      std::set&lt;int&gt; const* bad_items;
      bool operator() (int const i) const {
          return bad_items.count(i) &gt; 0;
      }
  };
  
  std::vector&lt;int&gt; items() const {
      is_item_bad iib = { &amp;bad_items; };
      std::vector&lt;int&gt; good_items(all_items.size());
      std::remove_copy_if(all_items.begin(),  all_items.end(), 
                          good_items.begin(), is_item_bad);
      return good_items; 
  }
  </code></pre>
  
  <p>Assume <code>all_items</code>, <code>bad_items</code>, <code>is_item_bad</code> and <code>items()</code> are all a part of some containing class. Is there a way to write them <code>items()</code> getter such that:</p>
  
  <ul>
  <li>It doesn't need temporary variables in the method?</li>
  <li>It doesn't need the custom functor, <code>struct is_item_bad</code>?</li>
  </ul>
  
  <p>I had hoped to just use the <code>count</code> method on <code>std::set</code> as a functor, but I haven't been able to divine the right way to express that w/ the <code>remove_copy_if</code> algorithm.</p>
  
  <p><strong>EDIT:</strong> Fixed the logic error in <code>items()</code>. The actual code didn't have the problem, it was a transcription error.</p>
  
  <p><strong>EDIT:</strong> I have accepted a solution that doesn't use <code>std::set_difference</code> since it is more general and will work even if the <code>std::vector</code> isn't sorted. I chose to use the C++0x lambda expression syntax in my code. My final <code>items()</code> method looks like this:</p>
  
  <pre><code>std::vector&lt;int&gt; items() const {
      std::vector&lt;int&gt; good_items;
      good_items.reserve(all_items.size());
      std::remove_copy_if(all_items.begin(), all_items.end(),
                          std::back_inserter(good_items),
                          [&amp;bad_items] (int const i) {
                              return bad_items.count(i) == 1;
                          });
  }
  </code></pre>
  
  <p>On a vector of about 8 million items the above method runs in 3.1s. I bench marked the <code>std::set_difference</code> approach and it ran in approximately 2.1s. Thanks to everyone who supplied great answers.</p>