Itolet Itolet - 3 months ago 12
C++ Question

How do I efficiently copy unique objects from one vector to another (which is made up of a subset of identical objects)?

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
. To do this, I want to copy elements from
minTreeInput
back into
minTreeOutput
until the latter contains the required number of edges. Of course, each edge object that is copied over must not already be stored
minTreeOutput
. Can't have duplicate edges in this graph.

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
(graph) that are not in
minTreeOutput
(tree) without having to check each individual element in the former against the latter?

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