Reputation: 57
I have a string vector containing all possible subsets of characters chosen from an n-length string (the subsets are stored as strings for the context of the greater problem, but there are no permutations of the same subset). I need to compare each such subset back to the original string and calculate its complementary subset of characters.
What is the most efficient way to do this?
Upvotes: 2
Views: 2152
Reputation: 308538
Since your vectors are already sorted, std::set_difference
does exactly what you need.
std::vector<std::string> result;
std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
Upvotes: 2
Reputation: 218323
It seems 'order' is the same so you may do
std::string compute_complement(const std::string& s, const std::string& sub)
{
std::string res;
auto it = sub.begin();
for (auto c : s) {
if (it != sub.end() && *it == c) {
++it;
} else {
res += c;
}
}
return res;
}
else you have to order the string
(with std::sort
)
Upvotes: 1