This function (find_prefix
) is supposed to find words starting with a given prefix in a container. The container is sorted. This function is a fairly performance-critical part of the code, so I am open for any optimization suggestions. Here is a brief usage case; test_in
is a file with \n
separated English words:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iterator>
#include <tuple>
#include <fstream>
template <typename It_beg, typename It_end, typename Prefix>
auto find_prefix(const It_beg beg,
const It_end end,
Prefix prefix)
{
auto low = std::lower_bound(beg, end, prefix);
++prefix.back();
auto up = std::lower_bound(beg, end, prefix);
return std::make_tuple(low, up);
}
int main()
{
std::string s;
std::fstream file("test_in");
if (!file)
{
std::cerr << "Failed to open the file\n";
return -1;
}
std::vector<std::string> svec;
svec.reserve(470000);
while (file >> s)
{
svec.push_back(s);
}
std::sort(svec.begin(), svec.end());
while (std::cin >> s)
{
auto [beg, end] = find_prefix(svec.cbegin(), svec.cend(), s);
std::copy(beg, end, std::ostream_iterator<std::string>(std::cout, "\n"));
}
return 0;
}
When the input is "stack" we get this output:
stack
stack's
stack-garth
stackable
stackage
stacked
stackencloud
stacker
stackering
stackers
stacket
stackfreed
stackful
stackgarth
stackhousiaceous
stacking
stackless
stackman
stackmen
stacks
stackstand
stackup
stackups
stackyard
prefix.back()
is already the max value the result will be incorrect (and incrementing the max value will also be undefined behaviour for signed types). \$\endgroup\$beg
andend
of different types? \$\endgroup\$