C++ predicate function?

I have no idea where to start with this question:





Write a predicate function





bool same_set(vector%26lt;int%26gt; a, vector%26lt;int%26gt; b)





that checks whether two vectors have the same elements in some order, ignoring multiplicities. For example, the two vectors





1 4 9 16 9 7 4 9 11





and





11 11 7 9 16 4 1





would be considered identical. You will probably need one or more helper functions.

C++ predicate function?
There are pretty smart techniques to do this (involving search trees and such), but I'll keep it simple here.





A mathematician would say that two sets A and B are equal if and only if A is a subset of B and B is a subset of A. Or:





bool same_set(vector%26lt;int%26gt; a, vector%26lt;int%26gt; b)


{


if (!is_subset(a,b))


return false;


if (!is_subset(b,a))


return false;


return true;


}





A 'dumb' way to check wether A is a subset of B is checking wether each element of A is in B:





bool is_subset(vector%26lt;int%26gt; subset, vector%26lt;int%26gt; set)


{


vector%26lt;int%26gt;::iterator iter;





for (iter = subset.begin(); iter %26lt; subset.end(); iter++)


{


if (!is_in(*iter, set))


return false;


}


return true;


}





A way to check wether something is part of a set should be trivial; just keep searching for it until you've found it in the set:





bool is_in(int element, vector%26lt;int%26gt; set)


{


vector%26lt;int%26gt;::iterator iter;


for(iter = set.begin(); iter != set.end(); iter++)


{


if (*iter == element)


return true;


}


return false;


}