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

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


Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=171321

[not at google - send to devlin, 2012-11-30 22:29:39]

Fight!

[not at google - send to devlin, 2012-11-30 22:31:18]

I'd actually rather put this in something like base/set_util.h since the fact
that it's implemented using std::set_difference is somewhat of an implementation
detail.

The first point is whether we're ok with making usable interfaces around C++
algorithms.

[not at google - send to devlin, 2012-11-30 22:41:37]

Cool, well, review for realz then I suppose.

(I reverted the demonstration change to url_index_private_data.cc but you can
look at the old patchset obviously)

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

Questions for willchan to answer below:

https://codereview.chromium.org/11415239/diff/4001/base/stl_util.h
File base/stl_util.h (right):

https://codereview.chromium.org/11415239/diff/4001/base/stl_util.h#newcode199
base/stl_util.h:199: std::set<T> STLSetDifference(const std::set<T>& a, const
std::set<T>& b) {
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]

https://codereview.chromium.org/11415239/diff/4001/base/stl_util.h
File base/stl_util.h (right):

https://codereview.chromium.org/11415239/diff/4001/base/stl_util.h#newcode199
base/stl_util.h:199: std::set<T> STLSetDifference(const std::set<T>& a, const
std::set<T>& b) {
On 2012/11/30 23:00:16, Jeffrey Yasskin wrote:
> 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.

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.

> 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.

[not at google - send to devlin, 2012-11-30 23:50:16]

test added

[Jeffrey Yasskin, 2012-11-30 23:59:58]

lgtm

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

https://codereview.chromium.org/11415239/diff/8001/base/stl_util.h
File base/stl_util.h (right):

https://codereview.chromium.org/11415239/diff/8001/base/stl_util.h#newcode194
base/stl_util.h:194: 
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.

https://codereview.chromium.org/11415239/diff/8001/base/stl_util.h#newcode195
base/stl_util.h:195: // Returns a new std::set containing the difference of two
sets.
It does not necessarily return a new std::set. Please update the comment.

https://codereview.chromium.org/11415239/diff/8001/base/stl_util.h#newcode200
base/stl_util.h:200: std::set_difference(a1.begin(), a1.end(),
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.

https://codereview.chromium.org/11415239/diff/8001/base/stl_util_unittest.cc
File base/stl_util_unittest.cc (right):

https://codereview.chromium.org/11415239/diff/8001/base/stl_util_unittest.cc#...
base/stl_util_unittest.cc:7: #include "base/stl_util.h"
This should go first

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

https://codereview.chromium.org/11415239/diff/8001/base/stl_util.h
File base/stl_util.h (right):

https://codereview.chromium.org/11415239/diff/8001/base/stl_util.h#newcode194
base/stl_util.h:194: 
On 2012/12/01 17:22:13, willchan wrote:
> 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.

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:44]

https://codereview.chromium.org/11415239/diff/8001/base/stl_util.h
File base/stl_util.h (right):

https://codereview.chromium.org/11415239/diff/8001/base/stl_util.h#newcode194
base/stl_util.h:194: 
On 2012/12/01 17:24:19, tfarina wrote:
> On 2012/12/01 17:22:13, willchan wrote:
> > 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.
> 
> I tried to do this incrementally, but you wanted me to do all at once :(

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]

https://codereview.chromium.org/11415239/diff/8001/base/stl_util.h
File base/stl_util.h (right):

https://codereview.chromium.org/11415239/diff/8001/base/stl_util.h#newcode194
base/stl_util.h:194: 
On 2012/12/01 17:38:45, willchan wrote:
> On 2012/12/01 17:24:19, tfarina wrote:
> > On 2012/12/01 17:22:13, willchan wrote:
> > > 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.
> > 
> > I tried to do this incrementally, but you wanted me to do all at once :(
> 
> 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.

I'll put this in base.

https://codereview.chromium.org/11415239/diff/8001/base/stl_util.h#newcode200
base/stl_util.h:200: std::set_difference(a1.begin(), a1.end(),
On 2012/12/01 17:22:13, willchan wrote:
> 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.

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]

https://codereview.chromium.org/11415239/diff/8001/base/stl_util.h
File base/stl_util.h (right):

https://codereview.chromium.org/11415239/diff/8001/base/stl_util.h#newcode200
base/stl_util.h:200: std::set_difference(a1.begin(), a1.end(),
On 2012/12/03 20:22:01, kalman wrote:
> On 2012/12/01 17:22:13, willchan wrote:
> > 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.

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?

> 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?

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

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

https://codereview.chromium.org/11415239/diff/8001/base/stl_util.h
File base/stl_util.h (right):

https://codereview.chromium.org/11415239/diff/8001/base/stl_util.h#newcode200
base/stl_util.h:200: std::set_difference(a1.begin(), a1.end(),
On 2012/12/03 20:29:35, Jeffrey Yasskin wrote:
> On 2012/12/03 20:22:01, kalman wrote:
> > On 2012/12/01 17:22:13, willchan wrote:
> > > 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.
> 
> 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?

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

> 
> > 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?
> 
> I won't insist that you support other than std::sets.

But if you were writing it then...

[not at google - send to devlin, 2012-12-04 02:11:10]

it be real

[not at google - send to devlin, 2012-12-05 18:02:40]

ping

[willchan no longer on Chromium, 2012-12-05 18:25:02]

oops, looking


On Wed, Dec 5, 2012 at 10:02 AM, <kalman@chromium.org> wrote:

> ping
>
>
https://codereview.chromium.**org/11415239/<https://codereview.chromium.org/1...
>

[willchan no longer on Chromium, 2012-12-05 18:27:40]

lgtm

https://codereview.chromium.org/11415239/diff/6002/base/stl_util_unittest.cc
File base/stl_util_unittest.cc (right):

https://codereview.chromium.org/11415239/diff/6002/base/stl_util_unittest.cc#...
base/stl_util_unittest.cc:7: #include "base/stl_util.h"
Should go first, as per style guide example of basictypes_unittest.cc or
whatever it is.

[not at google - send to devlin, 2012-12-05 18:36:01]

https://codereview.chromium.org/11415239/diff/6002/base/stl_util_unittest.cc
File base/stl_util_unittest.cc (right):

https://codereview.chromium.org/11415239/diff/6002/base/stl_util_unittest.cc#...
base/stl_util_unittest.cc:7: #include "base/stl_util.h"
On 2012/12/05 18:27:40, willchan wrote:
> Should go first, as per style guide example of basictypes_unittest.cc or
> whatever it is.

done, I think. I couldn't find basictypes_unittest.cc.

[commit-bot: I haz the power, 2012-12-05 18:36:08]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/kalman@chromium.org/11415239/16001

[commit-bot: I haz the power, 2012-12-05 21:40:28]

Change committed as 171321