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

Question

我有一个非常大的 std::vector v std::vector<std::string> 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 mixed with c++，我对此并不满意。

有什么更好的选择？

Answer 1

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

如果要找到所有满足条件的元素，就免不了要遍历整个vector。但是你可以使用更好的 range-based for-loop instead of index based loop to iterate through the vector, and check wether str.find(substring) == 0(credits @PiotrSkotnicki).

示例代码如下： (See online)

#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, along with a lambda function you could write the following. Read more about the lambdas here: What is a lambda expression in C++11? (See online)

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

如果您只对字符串向量中的第一个匹配项感兴趣，请使用标准算法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
}

Answer 2

如果你有一个未排序的容器，你不能在时间复杂度上比 O(n) 更好，这意味着以线性方式遍历整个容器（即对于环形）。如果您的容器已排序（例如 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";        
}

Live example

这里是 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;
}

Live example

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;

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

How to check if elements of std::vector<std::string> start with certain sub-string?

c++

stdstring

stdvector

c++-standard-library

c++11