CODEWITHSUNDEEP
c++c++11vector
LearningToCode
LearningToCode

Reputation: 651

Remove duplicate vectors from vector of vectors

I am trying to implement the solution to the problem found at Link.

Here is my snippet of code

bool compareVec(vector<int> a, vector<int> b) {
    return std::equal(a.begin(), a.end(), b.begin());
}
vector<vector<int> > ans;
ans.erase(std::remove_if(ans.begin(), ans.end(), compareVec), ans.end());

I am getting the following errors

/usr/include/c++/4.8/bits/stl_algo.h: In instantiation of 
'_RandomAccessIterator std::__find_if(_RandomAccessIterator, 
_RandomAccessIterator, _Predicate, std::random_access_iterator_tag) [with 
_RandomAccessIterator = __gnu_cxx::__normal_iterator<std::vector<int>*, 
std::vector<std::vector<int> > >; _Predicate = bool (*)(std::vector<int>, 
std::vector<int>)]':

/usr/include/c++/4.8/bits/stl_algo.h:4465:41:   required from '_IIter   
std::find_if(_IIter, _IIter, _Predicate) [with _IIter = 
__gnu_cxx::__normal_iterator<std::vector<int>*, std::vector<std::vector<int>
 > >; _Predicate = bool (*)(std::vector<int>, std::vector<int>)]'

/usr/include/c++/4.8/bits/stl_algo.h:1144:64:   required from '_FIter 
std::remove_if(_FIter, _FIter, _Predicate) [with _FIter = 
__gnu_cxx::__normal_iterator<std::vector<int>*, std::vector<std::vector<int> 
> >; _Predicate = bool (*)(std::vector<int>, std::vector<int>)]'

solution.cpp:40:64:   required from here
/usr/include/c++/4.8/bits/stl_algo.h:214:23: error: too few arguments to    
function
if (__pred(*__first))
                   ^
/usr/include/c++/4.8/bits/stl_algo.h:218:23: error: too few arguments to   
function
if (__pred(*__first))
                   ^
/usr/include/c++/4.8/bits/stl_algo.h:222:23: error: too few arguments to 
function
if (__pred(*__first))
                   ^

Can anyone help me out in debugging this? Thanks in advance

EDIT

The elements of vector are sorted and all these vectors are also sorted.

Unique also gives an error. I am unable to figure out why?

Why is the example given in the link I provided, not helpful here?

Upvotes: 0

Views: 1827

Answers (2)

Brian Rodriguez
Brian Rodriguez

Reputation: 4366

std::remove_if requires a unary predicate. You pass a binary predicate, which causes your errors (/usr/include/c++/4.8/bits/stl_algo.h:222:23: error: too few arguments to function → your function takes two arguments, not one). Further, std::remove_if does its removals with no consideration of other elements (which is why it accepts a unary predicate), so it isn't actually what you're looking for.

What you want to use is std::unique, which does require the compareVec you've implemented. However, std::vector already provides the operator== overload, so that implementation is actually redundant! Also, you say that you get an error when using std::unique. Try passing your parameters as const&.

Thus, when your outer vector and inner vectors are already sorted, the solution is as it'd be for any other vector of sorted elements:

outer.erase(std::unique(outer.begin(), outer.end()), outer.end());

Upvotes: 3

AndyG
AndyG

Reputation: 41220

Okay, since this is not marked with C++11, I will use a functor instead of a lambda.

The first problem you have is that remove_if takes a UnaryPredicate, which means it should only accept a single argument.

The second issue is also related to your understanding of remove_if. After you fix compareVec to only accept one argument, you're left wondering how you could possibly compare all elements against each other.

You could approach this one of two ways:

  • Sort your vector of vectors (< operator is defined lexicographically for vector) and then use std::unique (Examples) (More examples).
    • In the link you provided (same as the one I just linked to), notice that they sort first, and you do not.
  • Or, if there's no clear definition of < for your elements, only ==, you could perform an O(N2) lookup/erase on each subsequent item (shown below):

Comparison functor (could make as a lambda in C++11 and greater)

struct CompareVec
{
    CompareVec(const std::vector<int>& _in) : compare_against(_in){}

    bool operator()(const std::vector<int>& rhs) const
    {
        return compare_against == rhs;
    };

    const std::vector<int>& compare_against;
};

To be used like so:

for (size_t i = 0; i < ans.size(); ++i)
{
    CompareVec comparator(ans[i]);
    ans.erase(std::remove_if(ans.begin()+i+1, ans.end(), comparator), ans.end());
}

Live Demo (Compiled in C++11 for want of initializing test vectors with initializer lists)

Edit

In C++11 we can get rid of the CompareVec functor and replace it with a lambda:

for (size_t i = 0; i < ans.size(); ++i)
{
    ans.erase(std::remove_if(ans.begin()+i+1, ans.end(), 
    [&ans, &i](const std::vector<int>& _rhs)
    { 
        return ans[i] == _rhs;
    }) , ans.end());
}

Demo2

Upvotes: 2

Related Questions