Самый эффективный способ поиска массива строковых объектов в C++?

Question

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

Часть задания, над которым я работаю, это написать программу, которая ищет массив строк (адресную книгу) и возвращает совпадения, если найдено полное или частичное совпадение. Я могу сделать это легко, используя массив C-Strings, причем функция strstr() работает через цикл for и устанавливает указатель на результат запуска ключевого слова пользователя в массив (см. Ниже).

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

#include <iostream> 
#include <cstring> 
using namespace std; 

int main() 
{ 

    bool isFound = false;   // Flag to indicate whether contact is found 
    const int SIZE = 11;   // Size of contacts array 
    const int MAX = 50;   // Maximum characters per row 
    char contacts[SIZE][MAX] = { 
           "Jig Sawyer, 555-1223", 
           "Michael Meyers, 555-0097", 
           "Jason Vorhees, 555-8787", 
           "Norman Bates, 555-1212", 
           "Count Dracula, 555-8878", 
           "Samara Moran, 555-0998", 
           "Hannibal Lector, 555-8712", 
           "Freddy Krueger, 555-7676", 
           "Leather Face, 555-9037", 
           "George H Bush, 555-4939", 
           "George W Bush, 555-2783" 
           }; 
    char *ptr = NULL;    // Pointer to search string within contacts 
    char input[MAX];    // User search input string 


    // Get the user input 
    cout << "Please enter a contact to lookup in the address book: "; 
    cin.getline(input,MAX); 

    // Lookup contact(s) 
    for (int i=0; i<SIZE; i++) 
    { 
    ptr = strstr(contacts[i], input); 
    if (ptr != NULL) 
     { 
     cout << contacts[i] << endl; 
     isFound = true; 
     } 
    } 

    // Display error message if no matches found 
    if (!contactFound) 
    cout << "No contacts found." << endl; 

    return 0; 
} 

Как вы можете сказать, я люблю фильмы ужасов :)

Answer 1

Альтернативой будет использование регулярных выражений для поиска строк. Теперь есть a lot of info out there, и я просто дам простой пример, где вы пытаетесь сопоставить поддиапазон записей (адресов) с word2Search (который я жестко запрограммировал, чтобы избежать загромождения примера).

Я также использую (уже упомянутый в комментариях метод) шаг предварительной обработки, на котором сортируется массив.Остерегайтесь двух вещей:

• Сортировку делается для того, чтобы быстро метод поиска, то есть бинарный поиск (реализован с lower_boundupper_bound здесь)

• Если слово, которое вы ищете не в начале записи нет смысла сортировать записи, так как вы не сможете найти допустимый диапазон (здесь itite) для поиска (например, если вы ищете номера, сортировка строки будет выполняться в лексикографическом сравнение строк, поэтому было бы неплохо найти 555 среди строк, начинающихся с MJ и так далее)

Объяснение в комментариях:

int main() 
{ 
    // 1. Minor change - an array of strings is used 
    string contacts[] = { 
     "Jig Sawyer, 555-1223", 
     "Michael Meyers, 555-0097", 
     "Jason Vorhees, 555-8787", 
     "Norman Bates, 555-1212", 
     "Count Dracula, 555-8878", 
     "Samara Moran, 555-0998", 
     "Hannibal Lector, 555-8712", 
     "Freddy Krueger, 555-7676", 
     "Leather Face, 555-9037", 
     "George H Bush, 555-4939", 
     "George W Bush, 555-2783" 
    }; 
    // 2. The array is sorted to allow for binary search 
    sort(begin(contacts), end(contacts)); 
    // 3. Example hard coded a word to search 
    string word2Search = "George"; 
    // 4. A regular expression is formed out of the target word 
    regex expr(word2Search); 
    // 5. Upper and lower bounds are set for the search 
    char f = word2Search[0]; 
    std::string val1(1, f); 
    std::string val2(1, ++f); 
    // 6. Perform the search using regular expressions 
    for (auto it(lower_bound(begin(contacts), end(contacts), val1)), 
     ite(lower_bound(begin(contacts), end(contacts), val2)); it != ite; ++it) 
    { 
     if (regex_search(it->begin(), it->end(), expr)) { 
      cout << *it << endl; 
     } 
    } 

    return 0; 
} 

Answer 2

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

Наиболее эффективный метод определяет количество данных и организацию данных.

Для небольших наборов данных разница во времени между различными методами поиска обычно незначительна - некоторые другие элементы в вашей программе занимают больше времени (например, ввод или вывод).

Со строковыми данными большую часть времени проводят, сравнивая каждый символ одной строки с другой. Другие операции, такие как перемещение индексов вокруг, незначительны.

Поскольку сравнение методов поиска уже выполнено, выполните поиск в Интернете для «Сравнение строк строки исполнения».