CODEWITHSUNDEEP
c++vectorc++11
888
888

Reputation: 3406

Get all vector elements that don't belong to another vector

In C# if I want to get all elements in a List List1, which don't belong to another List List2 I can do

var result List1.Except(List2);

Is there something equivalent for std::vectors in C++? (C++11 is allowed)

Upvotes: 4

Views: 4038

Answers (4)

Asha
Asha

Reputation: 11232

You need to write your own function something like this:

for (auto element : List1)
{
  auto it = std::find(List2.begin(), List2.end(), element);
  if(it == List2.end())
  {
     result.push_back(element);
  }
}

Upvotes: 3

user2218982
user2218982

Reputation:

For any arbitrary container you can always use the std::remove_if + container::erase combination:

    template <typename Cont, typename FwdIt>
    void subtract(Cont& cont, FwdIt first, FwdIt last) {
        using std::begin; using std::end;
        using const_reference = typename Cont::value_type const&;
        cont.erase(std::remove_if(begin(cont), end(cont),
            [first, last](const_reference value){
                return last != std::find(first, last, value);
             }), end(cont));
    }

    template <typename Cont1, typename Cont2>
    void subtract(Cont1& cont1, Cont2 const& cont2) {
        using std::begin; using std::end;
        subtract(cont1, begin(cont2), end(cont2));
    }

In the case of std::list you can overload the subtract function, because std::list has a dedicated remove_if member function:

    template <typename T, typename Alloc, typename FwdIt>
    void subtract(std::list<T, Alloc>& l, FwdIt first, FwdIt last) {
        l.remove_if([first, last](T const& value){
            return last != std::find(first, last, value);
        });
    }

    template <typename T, typename Alloc, typename Cont>
    void subtract(std::list<T, Alloc>& l, Cont const& cont) {
        using std::begin; using std::end;
        subtract(l, begin(cont), end(cont));

}

These implementation are generic and make no assumption about the sorting of the sequences. If only your second container is guaranteed to be sorted, you can use std::binary_seach instead of find. If both sequences are sorted, you should use std::set_difference.

Upvotes: 1

WhozCraig
WhozCraig

Reputation: 66194

The following populates List3 with the content from List1 that is not in List2. I hope it is what you're looking for:

std::vector<Type> List1, List2;
//
// populate List1 and List2
//

std::vector<Type> List3;
std::copy_if(List1.begin(), List1.end(), std::back_inserter(List3),
     [&List2](const Type& arg)
     { return (std::find(List2.begin(), List2.end(), arg) == List2.end());});

Alternatively, this is likely better performing, since you don't have to search the entire list to determine lack of existence. Rather you can get an early "hit" and just move to the next node. Note the logic flip in the predicate:

std::vector<Type> List3;
std::remove_copy_if(List1.begin(), List1.end(), std::back_inserter(List3),
     [&List2](const Type& arg)
     { return (std::find(List2.begin(), List2.end(), arg) != List2.end());});

Upvotes: 7

ogni42
ogni42

Reputation: 1276

You should consider if a std::list is the right data structure for that, as it is - at least in C++ - not sorted by default, so in the worst case you will have to iterate size(list2) times through all elements of the list1, using an algorithm like Asha pointed out.

A better approach would be the use of an ordered container, e.g. multiset and use std::set_difference to create a result.

Upvotes: 1

Related Questions