c++ - 在容器中查找以给定字符开头的所有单词

Question

我需要帮助来搜索容器中的元素。

例如:我在容器中有以下单词:

crr.push_back("fred");
crr.push_back("barney");
crr.push_back("pavel");
crr.push_back("zoot");
crr.push_back("jim");
crr.push_back("peter");
crr.push_back("patrick");

我用它来寻找:

const bool Contains(vector<char*>& Vec, char* Element)
{
    if (find(Vec.begin(), Vec.end(), Element) != Vec.end())
        return true;

    return false;
}

int main()
{
    if (Contains(crr, "patrick"))
    {
        system("cls");
        printf("Found\n");
    }
    else
    {
       system("cls");
       printf("Nah\n");
    }
}

它支持 Found 因为在容器中找到了 "patrick"，但是我需要找到所有单词，例如，以 'p' 开头的单词。例如，输出可能是:

pavel
peter
patrick

我如何实现这一点？谢谢。

Answer 1

您可以复制所有以'p' 开头的单词进入 std::vector<std::string>容器，然后显示其内容。这可以在线性时间运行中完成，即 O(n)。空间复杂度也是线性的，因为您需要一个专用 vector 来存储以 'p' 开头的每个单词.

您可以使用函数模板 std::copy_if 来实现这一点通过提供合适的谓词，例如以下 lambda starts_with_p :

// returns true whether the string starts with 'p', false otherwise
auto starts_with_p = [](std::string word) {
    if (word.front() == 'p')
        return true;
    return false;
};

现在，只需使用 std::copy_if使用该谓词:

std::vector<std::string> matched_words;

std::copy_if(crr.begin(), crr.end(), 
             std::back_inserter(matched_words), starts_with_p);

载体matched_words包含原始容器中以 'p' 开头的所有单词.您现在可以轻松地显示它们:

for (const auto& word: matched_words)
    std::cout << word << std::endl;

---

如果您不想要线性空间复杂度而是常数一，即 O(1)，并且您的容器 crr支持随机访问迭代器，你可以先对你的集合进行排序crr与 std::sort 函数模板并使用 std::equal_range 对其执行二进制搜索为了获得所有以'p' 开头的单词的子范围:

std::sort(crr.begin(), crr.end());

auto cmp_1st_char = [](std::string a, std::string b) {
    return a.front() < b.front();
};

auto p = std::equal_range(crr.begin(), crr.end(), "p", cmp_1st_char);

for (auto it = p.first; it != p.second; ++it)
    std::cout << *it << std::endl;

但是请注意，排序的运行时间复杂度为 O(n log n)。因此，对于这两种选择，您将面临运行时间和空间复杂性之间的权衡。