C++ Copy None Existing Elements from one Vector to another

Question

I have a class like this:

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

I store them inside a Vector. Now i have a function which takes a vector of these DataElement and also creates a vector of the 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
}

Now i want to copy all the Elements from the vector data into the vector additional_data if there key is not already there.

I was thinking of using copy_if but how do i check if the current element is already in the Destination?

You can use `std::find` on the `additional_data` captured in the lambda. However, this is o(N²). If this is critical, you can maintain a cache of the "already copied values". — limserhane, May 09 '22 at 13:21
Actually: Depends on the context and the datasize. And system requirements. It might even be faster to build up a map and then finally convert that back to a vector. — JHBonarius, May 09 '22 at 13:21
Better to use a map or set to copy unique items. Searching a vector would be `O(n^2)` — Goswin von Brederlow, May 09 '22 at 13:25

score 0 · Answer 1 · answered May 09 '22 at 13:29

I prefer to check if the current element is already in the Destination with an additional 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;
}

score 0 · Answer 2 · answered May 09 '22 at 13:32

You could use std::find_if to check if an element with given key is already in the vector.

However, std::find_if is O(N) and when you do it for N elements you end up with a O(N^2). Consider to use std::unordered_map instead of vectors. std::unordered_map::insert is O(1) on average for inserting a single element.

If you cannot switch to std::unordered_map, you can still use one while building the vector:

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

I wasnt sure from which vector you want to keep the element when both vectors contain one for a given key. The above code uses the one from data and the one from additional_data is only inserted when it wasnt present in data. Its just a matter of switching order of the two loops.

C++ Copy None Existing Elements from one Vector to another

2 Answers2