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

Question

I have a very large std::vector v of type std::vector<std::string> v. Now I want to compare which of the elements in the vector start with a certain substring str. What is the fastest possible way to do that?

I was thinking of a for-loop that iteratively compares the start of each element of v with the substring str. I first tried

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

Which is c mixed with c++ and I am not happy with that.

What better alternatives are there?

Answer 1

You can write completely a c++ code.

If you want to find all the elements satisfying the condition, you can not avoid iterating through the entire vector. But you could use better range-based for-loop instead of index based loop to iterate through the vector, and check wether str.find(substring) == 0(credits @PiotrSkotnicki).

Here is the example code: (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;
}

---

Alternatively using 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
    }
});

---

If you are interested only the first match in the vector of string s, making use of standard algorithm std::find_if as follows

#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

If you have an unsorted container you can't get better than O(n) in time complexity, which means iterating over the whole container in a linear manner (i.e. for loop). If your container was sorted (ex. std::set instead of std::vector) you would get O(log n) which is a lot better (binary search).

Prior to C++17, I can't come up with a better solution than yours (since creating a substring via std::string::substr means copying the substring unnecessarily). However C++17 introduced std::string_view which doesn't do any copying. There should be no noticable performance difference with compiler optimizations enabled.

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

And here is the std::set version for the quicker search:

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

You can using 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;