Как найти первое слово в векторе строк, которое соответствует заданному пользователем префиксу?

Question

Допустим, у меня есть отсортированный вектор строк:

std::vector<std::string> Dictionary
Dictionary.push_back("ant");
Dictionary.push_back("anti-matter");
Dictionary.push_back("matter");
Dictionary.push_back("mate");
Dictionary.push_back("animate");
Dictionary.push_back("animal");
std::sort(Dictionary.begin(), Dictionary.end());

Я хочу найти первое слово в векторе, которое соответствует префиксу, но в каждом найденном мной примере в качестве префикса используется жестко закодированная строка. Например, я могу определить булеву унарную функцию для поиска префикса «an»:

bool find_prefix(std::string &S) {
    return S.compare(0, 2, "an");
}

и использовать его в качестве предиката функции std::find_if(), чтобы найти итератор для первого совпадения. Но как я могу искать строку, заданную пользователем, в качестве префикса? Можно ли каким-то образом использовать бинарные предикаты? Или создать «псевдо-унарный» предикат, который зависит от переменной и параметра?

Или есть какой-нибудь другой контейнер и методы, которые я должен использовать в этой проблеме?

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

Answer 1

Вы можете записать find_prefix как лямбду. Это позволяет вам захватить строку, которую вы хотите найти, и использовать ее для сравнения:

string word = ...  // the prefix you're looking for
auto result = std::find_if(Dictionary.begin(), Dictionary.end(), 
                           [&word](string const &S) {
                           return ! S.compare(0, word.length(), word);
});

Answer 2

Поскольку вы сортируете вектор, вы должны воспользоваться возможностью сортировки вектора.

Вместо того, чтобы выполнять линейный поиск совпадения, вы можете использовать std :: lower_bound для поместите вас близко, если не прямо к записи, которая соответствует префиксу:

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

int main()
{
    std::vector<std::string> Dictionary;
    Dictionary.push_back("ant");
    Dictionary.push_back("anti-matter");
    Dictionary.push_back("matter");
    Dictionary.push_back("mate");
    Dictionary.push_back("animate");
    Dictionary.push_back("animal");
    std::sort(Dictionary.begin(), Dictionary.end());
    
    std::vector<std::string> search_test = {"an", "b", "ma", "m", "x", "anti"};
    for (auto& s : search_test)
    {
        auto iter = std::lower_bound(Dictionary.begin(), Dictionary.end(), s);
    
        // see if the item returned actually is a match
        if ( iter->size() >= s.size() && iter->substr(0, s.size()) == s )
            std::cout << "The string \"" << s << "\" has a match on \"" << *iter << "\"\n";
        else
           std::cout << "no match for \"" << s << "\"\n";
    }
}

Вывод:

The string "an" has a match on "animal"
no match for "b"
The string "ma" has a match on "mate"
The string "m" has a match on "mate"
no match for "x"
The string "anti" has a match on "anti-matter"

Тест после lower_bound выполняется, чтобы увидеть, если строка фактически совпадает с найденным lower_bound.