c++ - 在 C++ 中搜索字符串对象数组的最有效方法？

Question

我一直在寻找有关此主题的更多信息，但似乎找不到我正在寻找的答案，所以我希望您能提供帮助!

我正在做的作业的一部分是编写一个程序来搜索字符串数组(地址簿)，并在找到完全或部分匹配时返回匹配项。我可以使用 C 字符串数组轻松完成此操作，其中 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_bound upper_bound 实现)

• 如果您要搜索的单词不在记录的开头，则对记录进行排序是没有意义的，因为您将无法找到有效的范围(此处为它 ite) 进行搜索(例如，如果您搜索数字，则字符串的排序将在字符串之间的字典比较中完成，因此对于定位 555 没有任何好处 以 M J 开头的字符串等)

评论中的说明:

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