locate sub-vector in another vector 2019-05-03 09:06发布 站内文章 / C++ 11 0 0

问题:

I have a vector<string> v1 = {"A","B","C"}. I want to check if v1 is included in vector<string> v2 = {"X","Y","A","B","C","D"}.

• Can I find if a set is a subset of the other by using STL?
• The vectors should not be sorted
• If the subset is found just once the algorithm stops " if(counter == v1.size()){break;}". Do you think that I should allow it to continue the search in case the subset is repeated twice?

---

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

using namespace std;

float wordOrder ( std::vector<string> v1, std::vector<string> v2 )
{
  //declare a vector that will be used as an index. If we find the element of v1 in v2 we insert 1
  std::vector<int> index ( v2.size(),0 );
  int counter = 0;
  int s = v1.size();
  //check if size of v1 less than size of V2
  if ( v1.size() <= v2.size() ) {

    for ( int i = 0; i < v1.size(); i++ ) {
      for ( int j = 0; j < v2.size(); j++ ) {
        if ( v1[i]== v2[j]) {index[j] = 1;}
      }
    }
    //loop throught the index vector and check if we have a sequence of 1s
    for ( int i = 0; i < index.size(); i++ ) {
      if ( index[i] == 1 ) {
        for ( int j = i; j < index.size(); j++ ) {
          if ( index[j] == 1 ) {counter++;}
        }
        //if the sequence of 1s = to the size of v1 it means that we have identified the sub-vector
        if(counter == v1.size()){break;}
        else{counter = 0; continue;}
      }
    }
  }//end if
    return counter/(float)v1.size();
}


int main()
{
    std::vector<string> v1{"A","B","C"};
    std::vector<string> v2{"X","A","B","C","Y"};
    cout <<  wordOrder (v1, v2 ) << endl;
    return 0;
}

回答1:

Yes you can use the Standard Library. Use std::search to perform a range search :

vector<string> v1 = {"A","B","C"};
vector<string> v2 = {"X","Y","A","B","C","D"};

auto res = search(begin(v2), end(v2), begin(v1), end(v1));

And test if the range was found :

auto found = res != end(v2);

Live example here.

回答2:

RE: Can I find if a set is a subset of the other by using STL?

The answer to this is yes, but may not be as sexy as you would like. You could use count_if to iterate over v2 and provide a functor that counts how often a subset occurs in that container. If the subset you are searching for will always occur in order (i.e. C follows B follows A otherwise it doesn't count), you could use search_n() or search().

RE: If the subset is found just once the algorithm stops " if(counter == v1.size()){break;}". Do you think that I should allow it to continue the search in case the subset is repeated twice?

This depends on your needs. Do you need that functionality? If so, then you should program it. If you do not, the existing functionality is sufficient, simpler, and more efficient, so therefore better.