c++ - 字符串 vector 的高效组合

Question

我需要运行一个高效的函数来生成字符串组合。我在 SO 中使用了多个答案来写一些有用的东西。将 vector 组合，然后将结果字符串按字符排序，然后通过将结果 vector 插入无序集合来删除重复项。该函数需要在长 vector (100K) 上运行 1e7 次，我需要帮助运行更高效的代码。这是我现在拥有的:

vector<string> vec_combos(vector<string> v1, vector<string> v2) {
    vector<string> res;
    unordered_set<string> s;
    for(int i=0;i<v1.size();i++) {
        for(int j=0;j<v2.size();j++){
            res.push_back(v1[i]+v2[j]);
            sort(res.back().begin(),res.back().end());
        }
    }
    for( int i = 0; i < res.size(); ++i ) s.insert( res[i] );
    res.assign( s.begin(), s.end() );
    return res;
}

int main() {
    vector<string> v1 = {"ab","bc","ca"}, v2 = {"a","b"},v3;
    // combined vector = {"aba","bca","caa","abb","bcb","cab"}
    // sort string chars = {"aab","abc","aac","abb","bbc","abc"}
    // remove duplicates = {"aab","abc","aac","abb","bbc"}
    v3 = vec_combos(v1, v2);
    for(int i=0;i<v3.size();i++) {
        cout << v3[i] << ",";
    }
    return(0);
}

Answer 1

通过引用传递，避免临时不需要的容器。你可以使用类似的东西:

std::vector<std::string> vec_combos2(const std::vector<std::string>& v1,
                                     const std::vector<std::string>& v2)
{
    std::unordered_set<std::string> words; // Or std::set<std::string>

    for (const auto& s1 : v1) {
        for (const auto& s2 : v2) {
            std::string s = s1 + s2;
            std::sort(s.begin(), s.end());
            words.insert(std::move(s));
        }
    }
    return { words.begin(), words.end() };
}

Demo