Найдите больший вектор строки в большом векторе строки

В С++, какой самый быстрый способ (или приличный способ) проверить каждый элемент в строковом векторе размером ок. 800 000, чтобы увидеть, находится ли он в другом строковом векторе размером ок. размер 200000? Моя цель — протолкнуть все струны первого, найденные во втором, в третий.

Моя попытка новичка никогда не прекратится:

vector<string> combosVsWords(vector<string> words, vector<string> lettercombos)
{
    vector<string> firstwords;

    for (int i = 0; i != lettercombos.size(); i++)
    {
        if (find(words.begin(), words.end(), lettercombos[i]) !=   words.end())
            firstwords.push_back(lettercombos[i]);
    }       
}

c++ find vector large-data
person Austin    schedule 05.07.2015    source источник
comment
Не могли бы вы поместить каждый вектор в свой собственный набор STL и создать третий набор, используя функцию пересечения STL?   -  person Jacob Calvert    schedule 05.07.2015
comment
Честно говоря, я понятия не имею, что это значит, я очень новичок в C++ и программировании в целом. редактировать: о, стандартная библиотека, хм, позвольте мне немного изучить это.   -  person Austin    schedule 05.07.2015
comment
Если ваш вектор, который вы передаете, имеет так много строк, вы должны передать их в свою функцию по константной ссылке, а не по значению. Во-вторых, можно ли сортировать слова и комбинации букв? Если это так, то первое предложение использовать std::set_intersection будет вариантом.   -  person PaulMcKenzie    schedule 05.07.2015
comment
мне просто поставить const впереди? Надеюсь, это не указатели, потому что я еще не добрался до них. Да, с сортировкой все в порядке. Я проверю функцию пересечения.   -  person Austin    schedule 05.07.2015
comment
@AustinMW Hopefully that's not a pointer sort of thing Вы спросили, как быстрее всего. Ничто другое не указывает, что вы можете или не можете использовать. В любом случае, я опубликовал ответ, что, если можно отсортировать векторы, есть способ получить пересечение двух векторов.   -  person PaulMcKenzie    schedule 05.07.2015

Ответы (2)


arrow_upward
2
arrow_downward

Если vectors можно отсортировать, то с использованием std::set_intersection должно работать следующее:

#include <algorithm>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
//...
using namespace std;

vector<string> combosVsWords(vector<string>& words, 
                             vector<string>& lettercombos)
{
    vector<string> firstwords;

    // Sort the vectors 
    sort(words.begin(), words.end());
    sort(lettercombos.begin(), lettercombos.end());

    // get the set intersection of the vectors and place
    // the result in firstwords
    set_intersection(words.begin(), words.end(), lettercombos.begin(), 
                     lettercombos.end(), back_inserter(firstwords));

    return firstwords;
}
person PaulMcKenzie    schedule 05.07.2015

arrow_upward
1
arrow_downward

Что вы могли бы сделать, поместите каждый вектор в набор, например:

std::set<std::string> setA (vectorA.begin(), vectorA.end()), setB (vectorB.begin(), vectorB.end());

Затем получите пересечение наборов, например:

std::set<int> intersect;

set_intersection(setA.begin(),setA.end(),setB.begin(),setB.end(),
              std::inserter(intersect,intersect.begin()))

Значения в пересечении будут перекрывающимися значениями из setA и setB.

Эти вопросы также могут помочь. Как преобразовать вектор в набор

Как установить пересечение

person Jacob Calvert    schedule 05.07.2015