Order-preserving set difference

[Dave]

Hello all,

I have three vector<int> v1, v2 and v3. I want to copy everything from v1
to v3, except for the items that are also in v2. This sounds tailor-made
for set_difference( ) but for one catch: I need the order preserved, which
set_difference( ) does not do.

As it stands now, I copy v1 to v3, manually loop over v2 and, for each
element in v2, remove the first occurrence (if any) of that element from v3.

I also considered remove_if() in conjunction with a predicate that would
check for the presence of the item in v2, but a state change of the
predicate is required, and that's not allowed.

Here's an example of the required behavior:

v1: 6 5 4 7 6 3 8 2 1
v2: 3 6 2

v3: 5 4 7 6 8 1

What is the lexically shortest way to accomplish this? Can anybody beat a
manual loop with calls to find() and erase() such as I have done?

Thanks,
Dave

[Jerry Coffin]

Re: Order-preserving set difference

In article <vppekvog6nb63a @news.supernews .com>, better_cs_now@y ahoo.com
says...[color=blue]
> Hello all,
>
> I have three vector<int> v1, v2 and v3. I want to copy everything from v1
> to v3, except for the items that are also in v2. This sounds tailor-made
> for set_difference( ) but for one catch: I need the order preserved, which
> set_difference( ) does not do.[/color]

In that case, I'd probably use remove_copy_if.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[tom_usenet]

Re: Order-preserving set difference

On Sun, 26 Oct 2003 23:27:02 -0700, "Dave" <better_cs_now@ yahoo.com>
wrote:
[color=blue]
>Hello all,
>
>I have three vector<int> v1, v2 and v3. I want to copy everything from v1
>to v3, except for the items that are also in v2. This sounds tailor-made
>for set_difference( ) but for one catch: I need the order preserved, which
>set_difference () does not do.[/color]

set_difference *requires* ordered values - the input ranges must be
sorted.
[color=blue]
>As it stands now, I copy v1 to v3, manually loop over v2 and, for each
>element in v2, remove the first occurrence (if any) of that element from v3.
>
>I also considered remove_if() in conjunction with a predicate that would
>check for the presence of the item in v2, but a state change of the
>predicate is required, and that's not allowed.[/color]

Right.
[color=blue]
>
>Here's an example of the required behavior:
>
>v1: 6 5 4 7 6 3 8 2 1
>v2: 3 6 2[/color]

These are unsorted, so the algorithm will be necessarily very
inefficient (which is fine for small numbers of elements, not fine for
thousands or millions of elements). It might be worth sorting v2 if it
is large (or using a set), and finding elements using lower_bound or
similar.
[color=blue]
>
>v3: 5 4 7 6 8 1
>
>What is the lexically shortest way to accomplish this? Can anybody beat a
>manual loop with calls to find() and erase() such as I have done?[/color]

That's lexically shortest probably, but definitely even more
inefficient than necessary since you make multiple erases from the
middle of the vector. Instead, copy elements back over erased elements
using assignment, and make only a single call to the range version of
erase (or resize if you prefer) at the end.

Tom