Сравнение строк по префиксу

243

17 января 2018, 17:27

Есть корректно работающий шаблон для поиска диапазона строк в векторе, которые начинаются с определенного символа.

template <typename RandomIt>
std::pair<RandomIt, RandomIt> FindStartsWith(
        RandomIt range_begin, RandomIt range_end,
        char prefix) {
    std::string target1 = {prefix};
    auto first = std::lower_bound(range_begin, range_end, target1);
    auto next = static_cast<char>(prefix + 1);
    std::string target2 = {next};
    auto last = std::upper_bound(range_begin, range_end, target2);
    return std::make_pair(first, last);
};

Вариант для префикса в виде строки выдает неверные результаты. Подскажите в чем может быть ошибка.

template <typename RandomIt>
std::pair<RandomIt, RandomIt> FindStartsWith(
        RandomIt range_begin, RandomIt range_end,
        const std::string& prefix) {
    std::string target = prefix;
    auto first = std::lower_bound(range_begin, range_end, target);
    ++target[prefix.size() - 1];
    auto last = std::upper_bound(range_begin, range_end, target);
    return std::make_pair(first, last);
};

Answer 1

А что бы вам не воспользоваться стандартным equal_range с соответствующим предикатом? Что-то вроде

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;
vector<string> v{ "abvsd","hdvjh","hvdsg","dvass","dvahj","dv","dvar","dvb","jhkfb"};
template <typename RandomIt>
std::pair<RandomIt, RandomIt>
FindStartsWith(RandomIt range_begin, RandomIt range_end,
               const std::string& prefix)
{
    return std::equal_range(range_begin,range_end,prefix,
                            [&prefix](const std::string& a,const std::string& b)
                            {
                                return a.compare(0,prefix.length(),b.substr(0,prefix.length())) < 0;
                            });
}
int main(int argc, const char * argv[])
{
    sort(v.begin(),v.end());
    auto f = FindStartsWith(v.begin(),v.end(),"dva");
    for(auto i = f.first; i != f.second; ++i)
        cout << *i << endl;
}

Answer 2

Идея правильная, но ваш исходный шаблон никогда не являлся "корректно работающим", в чем вы можете запросто убедиться, выполнив поиск строк, начинающихся с 'a', в последовательности

{ "a", "ab", "b", "bc" }

Если вы хотите применить идиоматический прием с увеличением искомого значения "на чуть-чуть", то искать конец последовательности после такого увеличения надо имено через std::lower_bound, а не через std::upper_bound как у вас. Т.е. в вашем исходном варианте оба вызова должны быть именно std::lower_bound.

То же самое относится и к вашему второму варианту. Идея совершенно правильная и все будет прекрасно работать (если вы исключаете возможность переполнения), если вы вызовете std::lower_bound во втором случае. Это все, что вам надо исправить.

И, дополнительно, если вы знаете, что параметр внутри функции вы заведомо будете копировать, то лучше сразу передавать его по значению (это позволит компилятору генерировать более оптимальный код, если аргумент является временным значением)

template <typename RandomIt>
std::pair<RandomIt, RandomIt> FindStartsWith(
        RandomIt range_begin, RandomIt range_end,
        std::string prefix) 
{
  auto first = std::lower_bound(range_begin, range_end, prefix);
  ++prefix.back();
  auto last = std::lower_bound(range_begin, range_end, prefix);
  return { first, last };
}