C＆＃x2B;＆＃x2B;将无现有元素从一个向量复制到另一个矢量

Question

我有这样的课程：

struct DataElement {
    std::string key;
    std::string value;
    std::string placeholder;
    // some other data members
}

我将它们存储在矢量中。 现在，我有了一个功能，该函数采用了这些dataElement的vector，并且还创建了vector dataElement的。

std::vector<DataElement> doAction(std::vector<DataElement>& data) {
    auto additional_data = create_additional_data() //returns std::vector<DataElement>
    //merge data and additional_data
    return additional_data
}

现在，我想将所有元素从vector数据复制到vector afred_data（如果尚不存在的密钥）。

我正在考虑使用copy_if，但是如何检查当前元素是否已经在目标中？

Answer 1

我更喜欢检查当前元素是否已经在目的地中使用附加unordered_map

std::vector<DataElement> doAction(std::vector<DataElement>& data) {
    std::vector<DataElement> result = data;
    std::unordered_map<std::string, DataElement> merged;
    for(const auto& e: data){
     merged[e.key] = e;
    }

    auto additional_data = create_additional_data() //returns std::vector<DataElement>
    // Time complexity: O(N)
    for(const auto &e: additional_data){
    // it's O(1) complexity
    if(merged.find(e.key) == merged.end()){
        result.push_back(e);
        merged[e.key] = e;
       }
    }
    //merge data and additional_data
    return result;
}

Answer 2

您可以使用std :: find_if检查给定键的元素是否已经在向量中。

但是，std :: find_if是o（n），当您为n元素进行操作时，您最终会带有o（ n^2）。考虑使用std :: unordered_map而不是向量。 std :: unordered_map :: insert是o（1）插入单个元素。

如果您不能切换到std :: Unordered_map，则在构建向量时仍然可以使用一个：

#include <string>
#include <vector>
#include <unordered_map>

struct DataElement {
    std::string key;
    std::string value;
    std::string placeholder;
    // some other data members
};

std::vector<DataElement> create_additional_data() { return {}; }

std::vector<DataElement> doAction(std::vector<DataElement>& data) {
    auto additional_data = create_additional_data();

    std::vector<DataElement> result;
    std::unordered_map<std::string,DataElement> temp;

    
    for (const auto& e : data) { temp.insert({e.key,e}); }
    //merge data and additional_data

    // element is not inserted when key is already present !
    for (const auto& e : additional_data) { temp.insert({e.key,e});} 

    for (const auto& e : temp) { result.push_back(e.second); }

    return result;
}

当两个向量都包含一个用于给定键时，我不确定您要保留哪个向量。上面的代码使用数据中的一个代码，仅在data中不存在from_data中的代码。这只是两个循环切换顺序的问题。