How to check whether a vector is a subset of another in c++

Question

I am trying to find a simple way to check whether a vector is a subset of another without sorting the order of elements in the vector. Both the vectors contain random number elements in them.

std::includes seems to work only for sorted ranges. How can I accomplish this?

What if vector #1 has duplicates? Does vector #2 have to have similar duplicates as well? — Andrew Rasmussen, Aug 02 '11 at 01:56
Why do you need to do this? What's so bad about sorting them? — Karl Knechtel, Aug 02 '11 at 01:56
Sounds like you should have picked a `std::set` in the first place, possibly. Are you _sure_ that `std::vector` is what you want? — Lightness Races in Orbit, Aug 02 '11 at 01:56
Related: http://stackoverflow.com/questions/4068141/how-do-i-check-if-one-vector-is-a-subset-of-another (though the only useful answer is about `std::includes`, about which you are correct: it assumes sorted input). — Lightness Races in Orbit, Aug 02 '11 at 01:57
@Gene: Ask the OP. He hasn't specified whether it does or not; you just jumped to the conclusion that it doesn't. — Lightness Races in Orbit, Aug 02 '11 at 02:13
If order matters, it doesn't make sense to talk about sets or subsets in the first place. Mathematically, a set is defined as order being irrelevant. Otherwise, it would be a tuple. If order matters then this operation isn't really a subset at all, but something else. From what I can infer, it seems like he can't sort it because he can't modify the data be used. — Mike Bailey, Aug 02 '11 at 02:15

Benjamin Lindley · Accepted Answer · 2011-08-02T02:33:07.880

35

Copy the vectors. Sort the copies. Then use std::includes on the copies.

template <typename T>
bool IsSubset(std::vector<T> A, std::vector<T> B)
{
    std::sort(A.begin(), A.end());
    std::sort(B.begin(), B.end());
    return std::includes(A.begin(), A.end(), B.begin(), B.end());
}

edited Aug 02 '11 at 02:33

answered Aug 02 '11 at 02:03

Benjamin Lindley

101,917
9
204
274

10

"I am trying to find a simple way to check whether a vector is a subset of another without sorting the order of elements in the vector." If sorting is the answer, your question was very, very broken. – Lightness Races in Orbit Aug 02 '11 at 02:14
@Benjamin: Agreed, there's no reason why this should be downvoted. This is the smartest way of doing this out of all the answers given. If the OP truly wants to check if two things are subsets of each other without modifying the data, this is the way to go. This is literally probably about 5 lines of code in all. If the exact requirement was "I need to check if one is a subset of the other, with `O(1)` memory usage and without displacing the data of either vectors" the answer would be one of the two below. – Mike Bailey Aug 02 '11 at 02:19
4

@Benjamin: Because you didn't answer the question of "find... without sorting..." as Tomalak stated. – Andrew Rasmussen Aug 02 '11 at 02:24
1

@arasmussen: It seems like the "without sorting" requirement is a symptom of an underlying issue that the OP never quite got at. He described something he wanted to do but not what he was actually trying to accomplish. I've seen questions (and I've been guilty of asking such things) where the poster asked for one thing thinking it was the solution but where there was a much simpler solution that didn't require strange requirements. – Mike Bailey Aug 02 '11 at 02:27
1

@arasmussen: The question wasn't "find... without sorting...". If it was, I would have voted to close the question because it is an arbitrary requirement that is not applicable to real life programming. The requirement was that the OP didn't want his *own* vector sorted. That *is* a requirement that could be applicable to real life programming, so I answered *that* question. – Benjamin Lindley Aug 02 '11 at 02:28
@Benjamin: If you're going to transparently modify the question that you're answering, at least mention that in your answer as a disclaimer. – Lightness Races in Orbit Aug 02 '11 at 02:36
@Tomalak: I didn't modify the question, I just read it differently than you. – Benjamin Lindley Aug 02 '11 at 02:36
Agree with Benjamin. There's really only one good reason why you wouldn't want to sort the original vectors: if the original order of the vectors had business relevance. So you sort a copy. – MSalters Aug 02 '11 at 07:50

Lightness Races in Orbit · Answer 2 · 2011-08-02T02:08:27.117

My answer assumes that when you say "subset", you are really searching more for the equivalent of a "substring"; that is, maintaining order of elements during the search.

Ultimately, I can't see how you could do this in anything less than O(n*m). Given that, you can just roll your own pretty simply:

template <typename T1, typename T2>
bool contains(std::vector<T1> const& a, std::vector<T2> const& b) {
   for (typename std::vector<T1>::const_iterator i = a.begin(), y = a.end(); i != y; ++i) {
      bool match = true;

      typename std::vector<T1>::const_iterator ii = i;
      for (typename std::vector<T2>::const_iterator j = b.begin(), z = b.end(); j != z; ++j) {
          if (ii == a.end() || *j != *ii) {
              match = false;
              break;
          }
          ii++;
      }

      if (match)
         return true;
   }

   return false;
}

Live demo.

(You could probably be more creative with the template parameters.)

2011 was a scary time for C++! – ChengDuum Sep 25 '20 at 22:42 — ChengDuum, Sep 25 '20 at 22:42

Andrew Rasmussen · Answer 3 · 2011-08-02T02:19:08.217

3

This is assuming duplicates do NOT matter. So if you have two instances of the number 99 in vector a, then as long as vector b has at least one instance of the number 99, then it will be declared as a subset.

bool isSubset(const std::vector<int>& a, const std::vector<int>& b)
{
    for (std::vector<int>::const_iterator i = a.begin(); i != a.end(); i++)
    {
        bool found = false;

        for (std::vector<int>::const_iterator j = b.begin(); j != b.end(); j++)
        {
            if (*i == *j)
            {
                found = true;
                break;
            }
        }

        if (!found)
        {
            return false;
        }
    }

    return true;
}

edited Aug 02 '11 at 02:19

answered Aug 02 '11 at 01:59

Andrew Rasmussen

14,912
10
45
81

1

so instead of n*log(n) complexity the proposed solution has n^2 complexity (and it's also a bad c++) – Gene Bushuyev Aug 02 '11 at 02:01
He didn't mention complexity, and this is a very simple-to-understand solution in my opinion – Andrew Rasmussen Aug 02 '11 at 02:02
@Gene: How are you going to get `O(n log m)`? The input is not sorted. The best you can hope for is amortised `O(n*m)`, I'm sure. – Lightness Races in Orbit Aug 02 '11 at 02:03
i know i can check for elements of one vector on the other and tell if it is a subset. I was wondering if there was another method. – Praveen Aug 02 '11 at 02:04
1

Why do you want another method? You don't want to sort it, you don't want to iterate through each of them... Is there a larger problem that you aren't telling us? – Andrew Rasmussen Aug 02 '11 at 02:05
@Tomalak: sorting has `n*log(n)` complexity, there isn't faster way in general. – Gene Bushuyev Aug 02 '11 at 02:06
With sorting it would just be `O(n log n)`, where `n` is the larger size. Comparison would just be something like `O(m)` (I think) so it's still `O(n log n)`. – Mike Bailey Aug 02 '11 at 02:07
no there is no larger problem. i was just thinking if the others had a simple solution as in using std::includes but modifying it so that it works for unsorted elements as well – Praveen Aug 02 '11 at 02:07
@Gene, why do you call that bad C++... Did you want me to use indices instead of iterators? – Andrew Rasmussen Aug 02 '11 at 02:08
1

@Gene: Who's sorting? This question is about searching in an _unsorted_ range. – Lightness Races in Orbit Aug 02 '11 at 02:09
@Tomalak -- and I'm asking again, what's wrong with sorting them, that's the best way to solve the problem – Gene Bushuyev Aug 02 '11 at 02:11
1

@Gene, Such as? I'm asking as a student. – Andrew Rasmussen Aug 02 '11 at 02:12
2

@arasmussen -- unnecessary copies, uninitialized variables, with unnecessary long life-time, generally c-style code – Gene Bushuyev Aug 02 '11 at 02:16
1

@arasmussen: Accept the vectors by const reference, and declare your iterators within the loops are the major offenses. – Dennis Zickefoose Aug 02 '11 at 02:16
Have the above modifications fixed all "bad" C++ offenses? Thanks for your input. – Andrew Rasmussen Aug 02 '11 at 02:20

score 0 · Answer 4 · answered Dec 20 '17 at 22:48

0

With no sorting...

template <typename T>
bool isSubsetOrEqual(std::vector<T> const& a, std::vector<T> const& b) {
   for(auto const& av:a){
      if(std::find(b.begin(),b.end(),av)==b.end())
          return false;
   }
   return true;
}

answered Dec 20 '17 at 22:48

thayne

426
5
18

How to check whether a vector is a subset of another in c++

4 Answers4

Linked

Related