Contest 41: Set Symmetric Difference (part 2)

Online C++ programming contests.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard, raimo

Contest 41: Set Symmetric Difference (part 2)

Contest 41: Set Symmetric Difference (part 2)
Difficulty: Intermediate
Deadline: 7 August 2004 at 19:00 GMT

Description
In set theory, the difference operator, expressed A-B, is the set of all elements of A that are not in B. For example, if A = {1,2,3,4,5} and B = {3,4,5,6,7}, A-B = {1,2}.

The symmetric difference operator of two sets A and B, expressed as A\B, is defined as (A-B) union (B-A). It consists of all the elements in A not in B as well as the elements in B not in A. Using A = {1,2,3,4,5} and B = {3,4,5,6,7} as above, A\B = {1,2,6,7}.

You will write a generic function that receives two vectors of elements and performs a symmetric difference operation on them. Your function will report results through a generic callback passed as a parameter.

Prototype
Code: Select all
`template <class Element, class Callback>void symmetric_difference(const vector<Element>& set1, const vector<Element>& set2, Callback result_reporter);`

Element will meet the following requirements:
• Copyable
• assignable
• default constructable
• operators < and == implemented

The callback will be called once for each element in the symmetric difference, like so:
Code: Select all
`Element part_of_the_answer;// ...result_reporter(part_of_the_answer);`

Optimize for: speed

Example
Given the input: (1,2,3,4,5) and (3,4,5,6,7) where Element==int
Code: Select all
`result_reporter(1);result_reporter(2);result_reporter(6);result_reporter(7);`

Notes
• No number will occur more than once in any input vector, but the input vectors will not necessarily be sorted.
• There is no limit on the size of the input vectors.
• You may use STL containers, but you may not use set_* functions from the STL.
• If the template parts of this contest are confusing, please ask in the thread! The contest is not difficult, and this could be a good opportunity to learn some generic programming.

Submissions
Please attach your solution as a single .cpp file (preferably named "your_screen_name.cpp") in an email to ryan@cpp-home.com, with the subject line as "Contest 41".

Post any questions or comments in this thread. Good luck and enjoy!
Last edited by Ryan on Tue Aug 10, 2004 7:28 am, edited 2 times in total.
Ryan
Moderator

Posts: 323
Joined: Sat Jun 12, 2004 1:34 pm

The "Part 2" is a little misleading. You don't have to complete contest 40 to enter this one; nor do you need to do this one to enter contest 42. They're just all based on the same problem.
Ryan
Moderator

Posts: 323
Joined: Sat Jun 12, 2004 1:34 pm

so its like part 1, but its in a function.. and for each common thing, instead of cramming them into some list, you call some function?

so its like pretty much the same as contest one.. but with two more functions? -_-?

*edit* do we have to make the callback function? or just like submit the set function thing
:]

schloob

Posts: 1853
Joined: Mon Feb 16, 2004 10:29 am
Location: Seattle

schloob wrote:so its like part 1, but its in a function.. and for each common thing, instead of cramming them into some list, you call some function?

Yes.

schloob wrote:so its like pretty much the same as contest one.. but with two more functions? -_-?

The biggest difference is that you're now optimizing for speed.

schloob wrote:*edit* do we have to make the callback function? or just like submit the set function thing

No, but you can make one to test. Here's what I'd recommend for testing:
Code: Select all
`template <class Element>void TestCallback(const Element& e){  std::cout << e << std::endl;}`

And then use it like this:

Code: Select all
`vector<int> list1,list2;// fill the lists with test values heresymmetric_difference(list1, list2, TestCallback<int>);`
Ryan
Moderator

Posts: 323
Joined: Sat Jun 12, 2004 1:34 pm

one more question:

do we sumbit just the function or the entire program?
:]

schloob

Posts: 1853
Joined: Mon Feb 16, 2004 10:29 am
Location: Seattle

schloob wrote:do we sumbit just the function or the entire program?

Just the function.
Ryan
Moderator

Posts: 323
Joined: Sat Jun 12, 2004 1:34 pm

err

Code: Select all
`C:\PROJECTS\Contest 41\schloob.cpp(33) : fatal error C1001: INTERNAL COMPILER ERROR        (compiler file 'msc1.cpp', line 1786)          Please choose the Technical Support command on the Visual C++          Help menu, or open the Technical Support help file for more information`

line 33:

symmetric_difference(one,two,TestCallback<int>);

and if i change
Code: Select all
`void symmetric_difference(const vector<Element>& set1, const vector<Element&> set2, Callback result_reporter){`

to

Code: Select all
`void symmetric_difference(const vector<Element>& set1, const vector<Element> set2, Callback result_reporter){`

i now get:

Code: Select all
`schloob.obj : error LNK2001: unresolved external symbol "void __cdecl TestCallback(int)" (?TestCallback@@YAXH@Z)`

Code: Select all
`template <class Element>void TestCallback(const Element &e){  cout<<e<<endl;}`
:]

schloob

Posts: 1853
Joined: Mon Feb 16, 2004 10:29 am
Location: Seattle

For the second parameter, is the reference supposed to be inside the template parameter or outside of it? Is the original a typo?
Need information on a function I've posted? Chances are it's at the MSDN.
MXP

Posts: 6506
Joined: Mon Sep 22, 2003 5:27 pm

You must be using VC++6. It's really not very good at templates. Consider MinGW, Dev-C++, or VC++ 2003 Toolkit instead for this contest -- even more so for contest 42 if you're looking to try that one.

Try un-templatizing TestCallback:
Code: Select all
`void TestCallback(int i){ cout << i << endl; }`
Ryan
Moderator

Posts: 323
Joined: Sat Jun 12, 2004 1:34 pm

Colin Jeanne wrote:For the second parameter, is the reference supposed to be inside the template parameter or outside of it? Is the original a typo?

Oh, thanks for catching that. It's supposed to be outside, and it's fixed now.
Ryan
Moderator

Posts: 323
Joined: Sat Jun 12, 2004 1:34 pm

Also, may we modify set1 and set2?

Edit, never mind this, I realized that they are const
Last edited by MXP on Sun Aug 01, 2004 8:47 pm, edited 1 time in total.
Need information on a function I've posted? Chances are it's at the MSDN.
MXP

Posts: 6506
Joined: Mon Sep 22, 2003 5:27 pm

It wasn't explicitly stated, but do we need to output the elements from ascending order?
Need information on a function I've posted? Chances are it's at the MSDN.
MXP

Posts: 6506
Joined: Mon Sep 22, 2003 5:27 pm

Colin Jeanne wrote:It wasn't explicitly stated, but do we need to output the elements from ascending order?

No, not in this one.
Ryan
Moderator

Posts: 323
Joined: Sat Jun 12, 2004 1:34 pm

Before I send my solution I have just two questions:

1. Do we have to write the template <...> stuff in our cpp-file we send or will you do this for us so we can send just the function?

2. Just to make clear: Can we return the result elements in any order?

P.S. My function is not very fast again, but I hope it works somehow.

exomo

Posts: 879
Joined: Fri Sep 26, 2003 12:30 pm

exomo wrote:1. Do we have to write the template <...> stuff in our cpp-file we send or will you do this for us so we can send just the function?

I'm not sure I understand your question. The function you submit must be a template function, so yes, it needs the template <...> stuff. But should not provide the callback function, if that's what you meant -- I'll do that.

exomo wrote:2. Just to make clear: Can we return the result elements in any order?

Yes, the results can be "returned" (ie, passed to the callback) in any order.
Ryan
Moderator

Posts: 323
Joined: Sat Jun 12, 2004 1:34 pm

Next

Who is online

Users browsing this forum: No registered users and 0 guests