как найти общие слова между двумя векторами std::string

Я пытаюсь найти общие слова между двумя векторами std::string. Я хочу поместить их в отсортированный список, отсортированный по длине, а затем слова каждой длины отсортировать по алфавиту. Мне нужно использовать функции и функторы stl.

Мои мысли: используя for_each, пройдите через первый вектор и для каждого слова сравните его с другим вектором, используя функтор (если он общий, добавьте в список в функторе). Тогда в результирующем списке будут только общеупотребительные слова. Вот где я застрял, я знаю, как сортировать по алфавиту, но как мне отсортировать их по длине, а затем отсортировать фрагменты одинаковой длины по алфавиту? Я просмотрел stl, но я не нашел то, что мне нужно. Или я просто думаю об этом неправильно. Есть идеи?

Пример:

vec1: "и", "таким образом", "это", "имеет", "а", "начало", "и", "конец"

vec2: "и", "поэтому", "звезды", "являются", "начало", "до", "падение", "до", "их", "конец"

результат: "и", "конец", "начало"


c++ stl functor
person Marina Golubtsova    schedule 26.07.2013    source источник
comment
Можете ли вы сначала отсортировать векторы?   -  person juanchopanza    schedule 26.07.2013
comment
Да, если я создам копию каждого   -  person Marina Golubtsova    schedule 27.07.2013
comment
Прошу прощения, забыл упомянуть, что у меня не может быть дубликатов слов в результирующем векторе.   -  person Marina Golubtsova    schedule 27.07.2013

Ответы (5)


arrow_upward
4
arrow_downward

Если вам разрешено сортировать vec1 и vec2, вы можете использовать std::set_intersection для сортировки векторов по заданным вами критериям и получите общие элементы, упорядоченные по тем же критериям:

#include <algorithm>
#include <iterator>

std::sort(vec1.begin(), vec1.end(), funny_comp);
std::sort(vec2.begin(), vec2.end(), funny_comp);
std::list<std::string> intersection;

std::set_intersection(vec1.begin(), vec1.end(),
                      vec2.begin(), vec2.end(),
                      std::back_inserter(intersection),
                      funny_comp);

где funny_comp сравнивает по длине строки и выполняет лексикографическое сравнение строк, если они имеют одинаковую длину:

bool funny_comp(const std::string &lhs, const std::string &rhs)
{ 
   return (lhs.size()) == rhs.size()) ? lhs < rhs
                                      : lhs.size() < rhs.size();
}

См. рабочую демонстрацию здесь.

person juanchopanza    schedule 26.07.2013
comment
есть ли способ избежать дубликатов? - person Marina Golubtsova; 27.07.2013
comment
@MarinaGolubtsova Если я вас не понимаю, это решение удаляет дубликаты. Смотрите демо. - person juanchopanza; 27.07.2013

arrow_upward
1
arrow_downward

Если векторы отсортированы, вы можете использовать std::set_intersection(), чтобы найти слова, общие для каждого из них. std::set_intersection() — это время O(N) по количеству элементов. Типа, конечно, O (N log N).

person Codie CodeMonkey    schedule 26.07.2013
comment
Никакие векторы не отсортированы, но сложность O (NlogN) все же лучше, чем у меня была - person Marina Golubtsova; 27.07.2013

arrow_upward
1
arrow_downward

Ваше решение O (n ^ 2). Это означает, что если длина векторов равна n, вы выполняете n*n операций: просматриваете один вектор и для каждого элемента просматриваете другой вектор, чтобы найти его.

Если вы можете сортировать векторы (используя функцию sort. Нет необходимости в причудливой сортировке, как вы упомянули), время будет O (n). используя set_intersection. Даже если вы не можете их отсортировать — скопируйте их в новые векторы и отсортируйте эти новые векторы. Это намного быстрее, чем то, что вы предлагаете.

person rabensky    schedule 26.07.2013
comment
Вы сказали, что если вы можете сортировать, время O (n), разве сортировка не O (n log n)? - person sgryzko; 05.05.2016

arrow_upward
1
arrow_downward

Чтобы отсортировать по длине, а затем лексически, вам нужно определить функцию сравнения (или функтор), чтобы сделать это:

struct by_len_lex { 
   bool operator()(std::string const &a, std::string const &b) { 
       if (a.length() < b.length())
           return true;
       if (a.length() > b.length())
           return false;
       return a < b;
    }
};

// ...
std::sort(strings1.begin(), strings1.end(), by_len_lex());
std::sort(strings2.begin(), strings2.end(), by_len_lex());

// find intersection:
std::set_intersection(strings1.begin(), strings1.end(), 
                      strings2.begin(), strings2.end(),
                      std::back_inserter(results),
                      by_len_lex());

Обратите внимание: поскольку вы определяете критерии сортировки, вам необходимо указать одни и те же критерии как при сортировке , так и при выполнении пересечения.

person Jerry Coffin    schedule 26.07.2013
comment
Это делает это, но создает кучу дубликатов - person Marina Golubtsova; 27.07.2013
comment
Итак, я добавил std::unique к вашему алгоритму, не будет ли он более сложным? - person Marina Golubtsova; 27.07.2013
comment
@MarinaGolubtsova: Если у вас есть дубликаты в исходном вводе, это сохранит их в выводе. Если вы хотите их устранить, вы можете использовать std::unique для их устранения. - person Jerry Coffin; 27.07.2013

arrow_upward
0
arrow_downward

Это может быть не лучшим решением, но можно использовать карту следующим образом:

#include <iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

int main()
{
vector <string> v1{"and", "thus", "it", "has", 
                  "a", "beginning", "and", "end"};

vector <string> v2{"and" ,"therefore", "stars", 
                   "are", "beginning", "to","fall","to",
                   "their", "end"};

map <string,int> m;

auto check=[&](const string& x) { return m.find(x) != m.end() ; } ;

for_each(v1.begin(),
         v1.end(),
         [&](const string& x){ 
                m[x] =1;
            } 
         );

for_each(v2.begin(),
         v2.end(),
         [&](const string& x){ 
            if(check(x)) 
                cout<<x<<endl;
            } 
         );

}
person P0W    schedule 26.07.2013