Remove duplicate vectors from vector of vectors

Question

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?

Your `compareVec` is currently making a copy of both vectors to compare each time it's called. *cringe*. Take them by const reference instead. — AndyG, Dec 29 '15 at 20:34
Also, the callable that you pass to `remove_if` should only take one argument. You can achieve what you need with a lambda that captures. Also, this isn't how to remove duplicates properly. [Try this](http://stackoverflow.com/q/1041620/27678) — AndyG, Dec 29 '15 at 20:38
Both the answers are useful, but the first one is easier to understand, so marking it correct. +1 for AndyG's answer — LearningToCode, Dec 29 '15 at 21:59

Brian Rodriguez · Accepted Answer · 2016-01-02T19:06:59.393

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());

`std::vector` has both an `operator<` and `operator==` defined so they can be compared directly without needing `std::lexicographical_compare` or `std::equal` — Blastfurnace, Dec 29 '15 at 21:36

score 2 · Answer 2 · edited May 23 '17 at 11:44

~~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(N²) 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

Why do we need a loop for i? For std::unique, we just wrote the a single statement? — LearningToCode, Dec 29 '15 at 21:20
`std::equal` only makes sense here if both containers are the same size. It's probably simpler to just say `return compare_against == rhs;` — Blastfurnace, Dec 29 '15 at 21:21
@AndyG: `std::equal` will happily read past the end of a container if the first range is larger. If it's shorter it stops too early. C++14 is adding a two-range overload that gracefully handles unequal length ranges. — Blastfurnace, Dec 29 '15 at 21:25
@Blastfurnace: And, you're right. I was mistaken when I read the documentation for it. The versions that allow differently sized containers are C++14 only *and* I should have provided begin and end for the second container. — AndyG, Dec 29 '15 at 21:27
@LearningToCode: `unique` only removes adjacent equivalent items. Unless your vector of vectors is sorted, it's useless. — AndyG, Dec 29 '15 at 21:28

Remove duplicate vectors from vector of vectors

2 Answers2

Edit