如何检查std :: vector <std :: string>元素是否以某个子字符串开头？

Question

我有一个非常大的类型为std::vector<std::string>的std::vector v。现在我想比较向量中哪些元素以某个子字符串 str 开头。有什么最快的方法可以做到这一点？

我考虑使用for循环，逐一将v的每个元素的开头与子字符串str进行比较。我先尝试了：

std::string substring = "bla";
for (long unsigned int i = 0; i < v.size(); i++)
{
    if (!strncmp(v[i].c_str(), substring.c_str(), substring.size())) 
    {
        std::cout << "Item found: " << v[i] << std::endl;
    }
}

这里有一个c和c++混合的东西，我不满意。

有更好的替代品吗？

- Gilfoyle

---

只需使用以下代码进行字符串比较：if ( v[i].substr(0, substring.size()) == substring ) { /* ... */ }。 - DimChtz

Answer 1

你可以完全编写一个 c++ 代码。

如果你想找到所有满足条件的元素，你无法避免遍历整个向量。但是，你可以使用更好的基于范围的 for循环 而不是基于索引的循环来遍历向量，并检查是否 str.find(substring) == 0（感谢 @PiotrSkotnicki）。

以下是示例代码：(在线查看)。

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

int main()
{
    const std::string substring{ "bla" };
    std::vector<std::string> vecString{ {"bllll"}, {"bllll"}, {"blasomething"} };
    // iterate through the vector by range based for-loop
    // here `auto` deduded to `std::string` as you have vector of strings(i.e. `vecString`)
    for (const auto& str : vecString)
    {
        if (str.find(substring) == 0) {
            std::cout << str << " is a match\n";
            // do something more with str
        }
    }
    return 0;
}

---

或者你可以使用 std::for_each，结合lambda函数，你可以写出以下代码。在这里阅读有关lambda表达式的更多信息：C++11中的lambda表达式是什么？ (在线查看)

#include <algorithm> // std::for_each

std::for_each(std::cbegin(vecString), std::cend(vecString), [&substring](const auto& str)
{
    if (str.find(substring) == 0)
    {
        std::cout << str << " is a match\n";
        // do something more with str
    }
});

---

如果你只对字符串向量 s 中的第一个匹配项感兴趣，可以使用标准算法std::find_if，如下所示。

#include <algorithm> // std::find_if

const auto iter = std::find_if(std::cbegin(vecString), std::cend(vecString),
    [&substring](const auto& str) {
        return str.find(substring) == 0;
    }
);
if (iter != std::cend(vecString))
{
    // do something
}

- JeJo

---

你仍然需要循环。这只会返回第一个匹配项。 - DimChtz

@DimChtz 没有注意到“所有元素”的部分。好的，那么可以使用基于范围的循环或 std::for_each。我会相应地更新。 - JeJo

@Samuel 然而，我已经根据 Piotr 的建议更新了答案，这比我之前发布的更好。 - JeJo

我只关心子字符串是否与数组中的字符串开头匹配，那么我需要使用str.find()吗？ - Gilfoyle

@ALX23z 看起来很有前途：http://quick-bench.com/PuL3ggsdyADAUL47Al3SPKgHRog（希望我做得对）。我建议将其作为答案进行证明，以便未来的读者可以从中受益。我很乐意点赞。 - JeJo

Answer 2

如果您有一个未排序的容器，时间复杂度最好也只能是 O(n)，这意味着以线性方式（例如使用 for 循环）遍历整个容器。如果您的容器已经排好序（例如使用 std::set 而不是 std::vector），则可以获得更好的时间复杂度 O(log n)，这意味着可以使用二分查找等方法进行搜索。

在 C++17 之前，我无法想到比您的解决方案更好的方法（因为通过 std::string::substr 创建子字符串会不必要地复制子字符串）。然而，C++17 引入了 std::string_view，它不会进行任何复制。启用编译器优化后，应该没有明显的性能差异。

std::vector<std::string> v { "abcd", "abcdefg", "aaaabbbb", "abc", "ab"};
std::string_view query = "abc";

for (auto const& str : v) 
{
    if (str.size() < query.size())
        continue;

    auto probe = std::string_view(str).substr(0, query.size());
    if (query == probe)
        std::cout << "Item found: " << str << "\n";        
}

实时示例

以下是使用std::set快速搜索的版本:

std::set<std::string> v { "abcd", "abcdefg", "aaaabbbb", "abc", "ab"};
std::string query = "abc";

for (auto it = v.lower_bound(query); it != v.end(); ++it)
{
    auto probe = std::string_view(*it).substr(0, query.size());
    if (query == probe)
        std::cout << "Item found: " << *it << "\n";     
    else
        break;
}

实时例子

（此链接为实时代码演示）

- Timo

Answer 3

你可以使用c++20的std::string_view::start_with：

std::vector<std::string> v = {...};
std::string_view prefix = "bla";
for (std::string_view sv : v)
    if (sv.starts_with(prefix))
        std::cout << "Item found: " << sv << std::endl;

- 康桓瑋