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 <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 163 matching lines @@
  private:
   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();
 }
 

[willchan no longer on Chromium, 2012/12/01 17:22:13]

New code should go into the base namespace. I know it's inconsistent with the
previous code, but I expect that we will migrate them as well eventually.

[tfarina, 2012/12/01 17:24:19]

I tried to do this incrementally, but you wanted me to do all at once :(

[willchan no longer on Chromium, 2012/12/01 17:38:45]

If I'm being inconsistent, that's bad. Are you sure it's the same situation
though? I suspect in your case it was that you were migrating existing code (not
new code) to a namespace.

That said, if I am recalling incorrectly, I think it's more important to have a
consistent policy (it frustrates me to no end when reviewers make inconsistent
comments) than my minor current preference for sticking this in the base
namespace. So if you can reference where I said new code in an existing file
without the base namespace should also not go into the base namespace, I'd like
to stick with that.

[not at google - send to devlin, 2012/12/03 20:22:01]

I'll put this in base.

+// Returns a new std::set containing the difference of two sets.

[willchan no longer on Chromium, 2012/12/01 17:22:13]

It does not necessarily return a new std::set. Please update the comment.

+// A convenient wrapper around std::set_difference.
+template <typename ResultType, typename Arg1, typename Arg2>
+ResultType STLSetDifference(const Arg1& a1, const Arg2& a2) {
+  ResultType difference;
+  std::set_difference(a1.begin(), a1.end(),

[willchan no longer on Chromium, 2012/12/01 17:22:13]

Jeffrey alluded to it earlier, but the part that worries me is if we pass in a
hash_set or some other container that is not sorted. I think it's worth it to
add a is_sorted() and DCHECK it here.

[not at google - send to devlin, 2012/12/03 20:22:01]

Discussing this with willchan a bit, and it's a bit complicated to get is_sorted
because I need to either write it or get it from google, which involves asking
permission.

If we make this only work for std::set (which I would argue is the only sensible
thing - how often do you want to see STLSetDifference operate on vectors? that's
crazy - and it doesn't work for hashset anyway) then we don't need to check
is_sorted. And then I'm not sure about the result type either, if we make
everything just a set then you can leave out the template parameters.

Jeffrey, what are you thoughts on this?

[Jeffrey Yasskin, 2012/12/03 20:29:35]

template<typename Container>
bool is_sorted(const Container& cont) {
  return std::adjacent_find(cont.begin(), cont.end(),
std::greater<Container::value_type>()) == cont.end();
}

Right?
I won't insist that you support other than std::sets.

[not at google - send to devlin, 2012/12/03 20:39:10]

Dunno, I don't have stl in my veins. But cool, I can do that. I'll make it
STLIsSorted unless there are objections.
But if you were writing it then...

+                      a2.begin(), a2.end(),
+                      std::inserter(difference, difference.end()));
+  return difference;
+}
+
 #endif  // BASE_STL_UTIL_H_