Add STLSetDifference to stl_util.h, because std::set_difference is extremely

base/stl_util.h

 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 // Derived from google3/util/gtl/stl_util.h
 
 #ifndef BASE_STL_UTIL_H_
 #define BASE_STL_UTIL_H_
 
+#include <algorithm>
+#include <set>
 #include <string>
 #include <vector>
 
 // Clears internal memory of an STL object.
 // STL clear()/reserve(0) does not always free internal memory allocated
 // This function uses swap/destructor to ensure the internal memory is freed.
 template<class T>
 void STLClearObject(T* obj) {
   T tmp;
   tmp.swap(*obj);
@@ skipping 164 matching lines @@
   T* container_;
 };
 
 // Test to see if a set, map, hash_set or hash_map contains a particular key.
 // Returns true if the key is in the collection.
 template <typename Collection, typename Key>
 bool ContainsKey(const Collection& collection, const Key& key) {
   return collection.find(key) != collection.end();
 }
 
+// Returns a new std::set containing the difference of two sets.
+// A convenient wrapper around std::set_difference.
+template <typename T>
+std::set<T> STLSetDifference(const std::set<T>& a, const std::set<T>& b) {

[Jeffrey Yasskin, 2012/11/30 23:00:16]

I agree with the decision to only provide one overload, and have it return the
result instead of writing the result to an output iterator or another set.
That's simpler, matches most uses in the codebase, and is compatible with either
other output option if we decide to add them in the future.

You should template the arguments, and it may be worth DCHECKing that the inputs
are sorted so that people notice quickly if they pass in a hash_set. Or we can
keep this part of the interface as it is, because it's easy to generalize later.

I was thinking that you should template the result type. However, it looks like
it would be hard to write the output iterator for both set<> and vector<>. In
particular, std::inserter(a_vector, a_vector.end()) causes undefined behavior
after the first insert, since that insert invalidates the argument iterator.

3 options:
1) Define a helper template class that uses partial specialization to select the
right inserter depending on the input type. People would call this function like
STLSetDifference<ResultType>(set1, set2). We can't partially specialize
functions, or I'd suggest just specializing STLSetDifference to select the right
inserter.  If you pick this option, definitely write a test with vector outputs.

2) template STLSetDifference on the ResultType, but use std::set internally so
that users get a compile error if they pass a non-set type as the template
parameter. This provides forward-compatibility with option 1, at the cost of
making calls more verbose.

3) Return std::set<T> unconditionally, with no template parameter. If we ever
change our minds about this, we'd have to update the callers. I don't remember
if default template arguments were allowed in C++98, so we might or might not be
able to use them to avoid updating callers.

[Jeffrey Yasskin, 2012/11/30 23:06:21]

I'm just being dumb. insert_iterator uses 'iter = cont.insert(val, iter)' to
keep its iterator pointing into the actual container, so it works fine on
vectors. Go with option 1, please.

+  std::set<T> difference;
+  std::set_difference(a.begin(), a.end(),
+                      b.begin(), b.end(),
+                      std::inserter(difference, difference.end()));
+  return difference;
+}
+
 #endif  // BASE_STL_UTIL_H_