Contest 41: Set Symmetric Difference (part 2)

[Ryan]

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
Your function should call:

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!

[Ryan]

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.

[schloob]

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

[Ryan]

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.

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.

*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 here
symmetric_difference(list1, list2, TestCallback<int>);

[schloob]

one more question:

do we sumbit just the function or the entire program?

[Ryan]

do we sumbit just the function or the entire program?

Just the function.

[schloob]

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;
}

[MXP]

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

[Ryan]

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]

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.

[MXP]

Also, may we modify set1 and set2?

Edit, never mind this, I realized that they are const

[MXP]

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

[Ryan]

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

No, not in this one.

[exomo]

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.

[Ryan]

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.

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.