Itolet - 3 months ago 12

C++ Question

**How can I efficiently copy objects (or a range of objects) from vector A into vector B,**

**where vector B already contains certain objects identical to those from vector A,**

**so that no objects copied from vector A are already listed in vector B?**

I have a graph stored as a vector of edges in

`std::vector<MinTreeEdge>minTreeInput`

I have a minimum spanning tree created from this graph, stored in

`std::vector<MinTreeEdge>minTreeOutput`

I'm trying to add a randomly add a certain number of edges back into

`minTreeOutput`

`minTreeInput`

`minTreeOutput`

`minTreeOutput`

Below is what I've come up with so far. It works, but it's really long and I know the loop will have to be run many times depending on the graph and tree. I'd like to know how to do this properly:

`// Edge class`

struct MinTreeEdge

{

// For std::unique() between objects

bool operator==(MinTreeEdge const &rhs) const noexcept

{

return lhs == rhs.lhs;

}

int lhs;

int node1ID;

int node2ID;

int weight;

......

};

......

// The usage

int currentSize = minTreeOutput.size();

int targetSize = currentSize + numberOfEdgesToReturn;

int sizeDistance = targetSize - currentSize;

while(sizeDistance != 0)

{

//Probably really inefficient

for(std::vector<MinTreeEdge>::iterator it = minTreeInput.begin(); it != minTreeInput.begin()+sizeDistance; ++it)

minTreeOutput.push_back(*it);

std::vector<MinTreeEdge>::iterator mto_it;

mto_it = std::unique (minTreeOutput.begin(), minTreeOutput.end());

currentSize = minTreeOutput.size();

sizeDistance = targetSize - currentSize;

}

Alternatively, is there a way to just list all the edges in

`minTreeInput`

`minTreeOutput`

Answer

How can I efficiently copy objects (or a range of objects) from vector A into vector B, where vector B already contains certain objects identical to those from vector A, so that no objects copied from vector A are already listed in vector B?

If I understand the question correctly, this can be paraphrased to "how can I create a *set intersection* of two vectors?".

Answer: with `std::set_intersection`

Note that for this to work it requires that the two vectors are sorted. This is for efficiency reasons, as you have already touched upon.

```
#include <vector>
#include <algorithm>
#include <cassert>
#include <iterator>
struct MinTreeEdge
{
// For std::unique() between objects
bool operator==(MinTreeEdge const &rhs) const noexcept
{
return lhs == rhs.lhs;
}
int lhs;
int node1ID;
int node2ID;
int weight;
};
struct lower_lhs
{
bool operator()(const MinTreeEdge& l, const MinTreeEdge& r) const noexcept
{
return l.lhs < r.lhs;
}
};
std::vector<MinTreeEdge> merge(std::vector<MinTreeEdge> a,
std::vector<MinTreeEdge> b)
{
// let's pessimistically assume that the inputs are not sorted
// we could simply assert that they are if the caller is aware of
// the requirement
std::sort(a.begin(), a.end(), lower_lhs());
std::sort(b.begin(), b.end(), lower_lhs());
// alternatively...
// assert(std::is_sorted(a.begin(), a.end(), lower_lhs()));
// assert(std::is_sorted(b.begin(), b.end(), lower_lhs()));
// optional step if the inputs are not already `unique`
a.erase(std::unique(a.begin(), a.end()), a.end());
b.erase(std::unique(b.begin(), b.end()), b.end());
std::vector<MinTreeEdge> result;
result.reserve(a.size() + b.size());
std::set_intersection(a.begin(), a.end(),
b.begin(), b.end(),
std::back_inserter(result),
lower_lhs());
return result;
}
int main()
{
// example use case
auto a = std::vector<MinTreeEdge>{};
auto b = std::vector<MinTreeEdge>{};
b = merge(std::move(a), std::move(b));
}
```

Source (Stackoverflow)

Comments