CODEWITHSUNDEEP
c++vector
Tristan
Tristan

Reputation: 1685

C++ - Appending one Vector to another, with removal of duplicates?

I'd like to append one vector (vectorAlpha) to the end of another vector (vectorBeta). There's two different approaches I could think of, and I'd like to know how to do each one.

The first approach was to append the second vector and remove all duplicate items from the new vector. The other approach is to leave duplicates in the individual vectors alone, but not adding any items from vectorBeta if they are already present in vectorALpha.

For instance if the vectors are vector with the following values:

vectorAlpha:

First line of alpha
An alpha line
An alpha line
Some line
Alpha fifth line

vectorBeta:

Beta first line
A beta line
A beta line
Some line
Beta fifth line

I think the first approach would result in the combined vector:

First line of alpha
An alpha line
Some line
Alpha fifth line
Beta first line
A beta line
Beta fifth line

While the second approach would just be both arrays combined, but with the 'Some line' from the second vector not added:

First line of alpha
An alpha line
An alpha line
Some line
Alpha fifth line
Beta first line
A beta line
A beta line
Beta fifth line

What would be the C++ code to use for these two appraoches?

Upvotes: 7

Views: 11759

Answers (3)

sehe
sehe

Reputation: 393924

Update: new answer here due to changed/added requirements

typedef std::...<...> Vec;
Vec vecA;
Vec vecB;

// fill your data

// sort
std::sort(vecA.begin(), vecA.end());
std::sort(vecB.begin(), vecB.end());


// join
size_t mergesize = vecA.size();

std::copy(vecB.begin(), vecB.end(), std::back_inserter(vecA));

// merge
std::inplace_merge(vecA.begin(), vecA.begin()+mergesize, vecA.end());

You could combine the join+merge steps as follows

Vec vecC;
std::merge(vecA.begin(), vecA.end(),
            vecB.begin(), vecB.end(),
            std::back_insterter(vecC));

As a final step, remove the duplicates:

Vec::iterator pte = std::unique(vecC.begin(), vecC.end());
// dups now in [pte, vecC.end()), so optionally erase:
vecC.erase(pte, vecC.end());

Upvotes: 5

sehe
sehe

Reputation: 393924

Since it became clear that

  1. you only wanted duplicates remove entries from vecB if they existed in vecA, not duplicates in general
  2. you wanted to preserve the ordering

The answer should (obviously?) be std::remove_copy_if. Call it thusly:

#include <vector>
#include <algorithm>

typedef std::vector<int> Vec;
struct Contained
{
    const Vec& _sequence;
    Contained(const Vec &vec) : _sequence(vec) {}
    bool operator()(int i) const 
    { 
        return _sequence.end() != std::find(_sequence.begin(), _sequence.end(), i);
    }
};

int main()
{
    Vec vecA;
    Vec vecB;

    std::remove_copy_if(vecB.begin(), vecB.end(), back_inserter(vecA), Contained(vecA));
}

You might want to optimize the predicate depending on the size and nature of vecA:

#include <set>

template <typename T>
struct Contained
{
    const std::set<T> _set;
    template <typename It> Contained(const It& begin, const It& end) : _set(begin, end) {}
    bool operator()(const T& i) const 
    { 
        return _set.end() != _set.find(i);
    }
};

Which would be used as Contained<int>(vecA.begin(), vecA.end()). The full code is compiling on codepad.org

Cheers

Upvotes: 6

swestrup
swestrup

Reputation: 4209

Is the order of the elements in the two vectors important? If not, then you should probably be using sets instead.

Upvotes: 3

Related Questions