Блог

У меня есть vector<string> v1 = {"A","B","C"} . Я хочу проверить, включен ли v1 included vector<string> v2 = {"X","Y","A","B","C","D"} .

• Могу ли я определить, является ли набор подмножеством другого, используя STL ?
• Векторы не должны быть отсортированы
• Если подмножество найдено только один раз, алгоритм останавливается » if(counter == v1.size()){break;} «. Как вы думаете, я должен разрешить ему продолжить поиск в случае, если подмножество повторяется дважды?

 #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;
}
 

Да, вы можете использовать стандартную библиотеку. Используется std::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));
 

И проверьте, был ли найден диапазон :

 auto found = res != end(v2);
 

Живой пример здесь.

RE: Могу ли я определить, является ли набор подмножеством другого, используя STL?

Ответ на этот вопрос — да, но может быть не таким сексуальным, как вам хотелось бы. Вы могли бы использовать count_if для итерации по версии v2 и предоставить функтор, который подсчитывает, как часто подмножество встречается в этом контейнере. Если подмножество, которое вы ищете, всегда будет встречаться по порядку (т. Е. C следует за B следует за A, иначе это не считается), вы можете использовать search_n() или search() .

RE: Если подмножество найдено только один раз, алгоритм останавливается «if(counter == v1.size()){break;}». Как вы думаете, я должен разрешить ему продолжить поиск в случае, если подмножество повторяется дважды?

Это зависит от ваших потребностей. Вам нужна эта функциональность? Если это так, то вам следует его запрограммировать. Если вы этого не сделаете, существующая функциональность достаточна, проще и эффективнее, поэтому лучше.