Find words with this prefix

Question

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

Answer 1

1. As you are effectively reading the whole file test_in into memory in lots of small independent chunks, consider a different approach:

   1. Read the whole file as one big chunk, or preferably simply map it.
   2. Put std::string_views into that array in the vector, instead of strings.

   Most std::strings employ SSO, meaning there are two possible states (external string, active SSO), in contrast to the single one for std::string_view. Thus, no branch-misprediction.

   Additionally, std::string is generally at least twice the size of std::string_view, so this about halves the size of the vector's data.
   Due to allocator overhead, all the small bits of string data would also together likely need considerably more space than that one big chunk.

2. You copy the prefix on calling find_prefix(). Better pass a view.

3. When you know where the range you want starts, you know it won't end earlier.

4. ++prefix.back(); is blatantly wrong.

   1. If the prefix is empty, it's Undefined Behavior.

   2. If it causes signed overflow, it's Undefined Behavior.

   3. If it causes unsigned wrap-around, you simply get a completely wrong end-position, which might even lie before the start-position.

   I suggest simply writing your own comparator and using std::upper_bound() too, as it is intended to be used.

   Be aware that char is treated as unsigned char for comparison by std::char_traits<char>. You probably want to mirror that, especially as you used that rule when sorting... I won't go to the trouble of staying that general.

5. std::equal_range() with a custom comparator does what you want:

   template <class RandomAccessIterator>
   auto find_prefix(RandomAccessIterator first, RandomAccessIterator last, std::string_view prefix) {
       return std::equal_range(first, last, prefix,
           [n = prefix.size()](std::string_view a, std::string_view b) noexcept {
               return a.substr(0, n) < b.substr(0, n);
       });
   }
   

6. You don't need std::make_tuple in C++17. Just use std::tuple directly:

   return std::tuple{low, up};
   

7. By the way, return 0; is implicit for main().