c++ - 计算集合 A 相对于集合 B( vector )的补码的最有效方法？

Question

我有一个字符串 vector ，其中包含从长度为 n 的字符串中选择的所有可能的字符子集(这些子集存储为更大问题的上下文中的字符串，但没有相同子集的排列)。我需要将每个这样的子集与原始字符串进行比较，并计算其互补的字符子集。

最有效的方法是什么？

Answer 1

看起来'order'是一样的，所以你可以这样做

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

否则你必须订购string(使用std::sort)