6
\$\begingroup\$

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
\$\endgroup\$
7
  • \$\begingroup\$ I don't think this works. If 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\$
    – user673679
    May 22, 2019 at 19:32
  • \$\begingroup\$ beg and end of different types? \$\endgroup\$
    – vnp
    May 22, 2019 at 19:41
  • 2
    \$\begingroup\$ I recommend creating an example (a small file with includes, the code above, and some usage cases). Some more elaboration on the code, the problem and conditions in which the code will be run (input patterns, whether from file or not, etc) will be welcome too. I know the code is short, but there can be a lot to say about it. \$\endgroup\$ May 22, 2019 at 20:18
  • \$\begingroup\$ @Incomputable is it alright now? \$\endgroup\$ May 22, 2019 at 20:41
  • 1
    \$\begingroup\$ @Ayxan, certainly. Lets see what others think \$\endgroup\$ May 22, 2019 at 22:33

1 Answer 1

9
\$\begingroup\$
  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().

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.