Home > database >  Is there a standard algorithm to check if container A is a superset of container B?
Is there a standard algorithm to check if container A is a superset of container B?

Time:03-02

I was looking for a standard algorithm that, given two containers A and B, both with no duplicates, returns true if all the elements of A compares to true with an element of B. I used std::all_of with a predicate that checks membership in the other container, but I was wondering if there was a more elegant solution..

CodePudding user response:

Is there a STL algorithm to check if two containers contain same elements?

I suppose that you mean "elements that compare equal". One object can only be an element of one container (at least in case of all standard containers).

i was looking for an std:: algorithm that given two containers A and B, returns true if all the elements of A are contained in B.

This question is different from the one in the title.

For the first, there std::is_permutation. However, for some container types, there are more efficient algorithms. For example, if the container is sorted (such as std::set), then you can simply compare for equality.

For the second, there's no general algorithm. If the containers are sorted, then you can use std::includes. Otherwise you can write an algorithm that sorts first, and then uses std::includes.

I used std::all_of with a predicate that checks membership in the other container

If the larger container has fast lookup (such as unordered set), then this solution is good.

CodePudding user response:

std::includes does this provided both containers are sorted.

#include <algorithm>
#include <vector>
#include <iostream>

int main() {

  std::vector< int > A = {1, 2, 3, 4, 7};
  std::vector< int > B = { 1, 2 ,3};
  std::vector< int > C = { 3, 4, 5};

  bool BinA = std::includes(A.begin(), A.end(), B.begin(), B.end());
  bool CinA = std::includes(A.begin(), A.end(), C.begin(), C.end());
  std::cout<< "B in A = " << BinA <<std::endl;
  std::cout<< "C in A = " << CinA <<std::endl;
}

https://godbolt.org/z/dnoM4xPbY

If you they are not sorted, and you can't/don't want to sort them, then I believe the all_of approach is about as efficient as possible. If performance is critical I think sorting first is more efficient but you should check for your particular case.

  • Related