473,322 Members | 1,714 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

Order-preserving set difference

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
Jul 19 '05 #1
2 2461
In article <vp************@news.supernews.com>, be***********@yahoo.com
says...
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.


In that case, I'd probably use remove_copy_if.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jul 19 '05 #2
On Sun, 26 Oct 2003 23:27:02 -0700, "Dave" <be***********@yahoo.com>
wrote:
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.
set_difference *requires* ordered values - the input ranges must be
sorted.
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.
Right.

Here's an example of the required behavior:

v1: 6 5 4 7 6 3 8 2 1
v2: 3 6 2
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.

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?


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
Jul 19 '05 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

7
by: svilen | last post by:
hello again. i'm now into using python instead of another language(s) for describing structures of data, including names, structure, type-checks, conversions, value-validations, metadata etc....
9
by: Steven T. Hatton | last post by:
The following works: template <typename T> struct ID3M{ static const T ID; }; template <typename T> const T ID3M<T>::ID = {{1,0,0},{0,1,0},{0,0,1}};
15
by: | last post by:
The data file is a simple Unicode file with lines of text. BCP apparently doesn't guarantee this ordering, and neither does the import tool. I want to be able to load the data either sequentially...
27
by: Abdullah Kauchali | last post by:
Hi folks, Can one rely on the order of keys inserted into an associative Javascript array? For example: var o = new Object(); o = "Adam"; o = "Eve";
8
by: kaosyeti | last post by:
i have a (hopefully) small problem. i have created a system where a user enters customer information into a table through a form. this table has no primary key. there are 9 fields on the form to...
13
by: bevanward | last post by:
Hi All I am finding unexpected results when inserted into a newly created table that has a field of datatype int identity (1,1). Basically the order I sort on when inserting into the table is...
3
by: Hartmut Dippon | last post by:
Hi all, I hope somebody can help me with following problem: I have an application where I can drag&drop files/dirs from within explorer onto my form. If multiple files/dirs are selected I...
1
by: aRTx | last post by:
<? /* Directory Listing Script - Version 2 ==================================== Script Author: Artani <artan_p@msn.com>. www.artxcenter.com REQUIREMENTS ============ This script requires...
54
by: Rasjid | last post by:
Hello, I have just joined and this is my first post. I have never been able to resolve the issue of order of evaluation in C/C++ and the related issue of precedence of operators, use of...
25
by: DanicaDear | last post by:
Hello again Bytes...I missed you! First, background: In a hotstick lab, we ship orders every two years. We ship a new order and the customer uses the new box to return the previous year's order....
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.