CODEWITHSUNDEEP
c++subset
aj1204
aj1204

Reputation: 57

Most efficient way to calculate complement of set A with respect to set B (vectors)?

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

Answers (2)

Mark Ransom
Mark Ransom

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

Jarod42
Jarod42

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

Related Questions