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

base/stl_util.h

Index: base/stl_util.h
diff --git a/base/stl_util.h b/base/stl_util.h
index b3ddfa3b4fe8f85bb9568768d1a2af9fd7c75d19..4e0826c5ffb3acd307e19d67239891fcc6ff8d33 100644
--- a/base/stl_util.h
+++ b/base/stl_util.h
@@ -7,6 +7,8 @@
 #ifndef BASE_STL_UTIL_H_
 #define BASE_STL_UTIL_H_
 
+#include <algorithm>
+#include <set>
 #include <string>
 #include <vector>
 
@@ -191,4 +193,15 @@ 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_