Как использовать STL для нечувствительного к регистру двоичного поиска строки

Question

Если у меня есть вектор строк, как мне выполнить бинарный поиск для определенной строки, используя сравнение без учета регистра? Я не могу придумать простой способ сделать это.

Answer 1

Предоставление функции сравнения для std :: sort, сортировка вашего контейнера в нижнем регистре (используйте для этого вспомогательные строковые алгоритмы),

Затем выполните двоичную строку для отсортированного вектора, снова предоставьте для этого операцию сравнения без учета регистра.

Использование лямбда-выражения действительно поможет

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

РЕДАКТИРОВАТЬ: вот пример

#include <boost/algorithm/string.hpp>
#include <algorithm>
::::

auto comp=[](const std::string& a, const std::string& b){   
   return boost::ilexicographical_compare
                       <std::string, std::string>(a,b);
});

std::sort(vs.begin(), vs.end(), comp);
std::binary_search(vs.begin(), vs.end(), value_to_search_for, comp);

Эта же функция сравнения также будет работать с std :: find, если вы не собираетесь сортировать список.

ПРОВЕРЕНО

http://en.cppreference.com/w/cpp/algorithm/find

http://en.cppreference.com/w/cpp/algorithm/binary_search

http://en.cppreference.com/w/cpp/algorithm/sort

Answer 2

Если вам нужно только знать, существует ли такой элемент, используйте std :: binary_search. Если вам нужен доступ к этому элементу и вы знаете его позицию, используйте std :: lower_bound.

Answer 3

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <strings.h> // strncasecmp()

inline int icompare(std::string const& a, std::string const& b) {
    size_t a_len = a.size(), b_len = b.size();
    size_t cmp_len = std::min(a_len, b_len);
    // strncasecmp() is a non-standard function, use the one available for your platform.
    if(int r = strncasecmp(a.data(), b.data(), cmp_len))
        return r;
    return (a_len > b_len) - (a_len < b_len);
}

struct LessNoCase {
    bool operator()(std::string const& a, std::string const& b) const {
        return icompare(a, b) < 0;
    }
};

template<class Iterator, class T>
Iterator binary_search_caseless(Iterator beg, Iterator end, T const& value) {
    Iterator i = std::lower_bound(beg, end, value, LessNoCase());
    return i != end && !icompare(*i, value)
        ? i   // found
        : end // not found
        ;
}

int main() {
    char const* strings[] = {
        "abc",
        "def",
        "ghi"
    };

    std::vector<std::string> v(
        strings + 0,
        strings + sizeof strings / sizeof *strings
        );

    // prepare for binary search
    std::sort(v.begin(), v.end(), LessNoCase());

    // do the binary search
    std::cout << "index of 'abc' is " << binary_search_caseless(v.begin(), v.end(), "ABC") - v.begin() << '\n';
    std::cout << "index of 'ABC' is " << binary_search_caseless(v.begin(), v.end(), "ABC") - v.begin() << '\n';
    std::cout << "index of 'DEF' is " << binary_search_caseless(v.begin(), v.end(), "DEF") - v.begin() << '\n';
    std::cout << "index of 'xyz' is " << binary_search_caseless(v.begin(), v.end(), "xyz") - v.begin() << '\n';
}

Выходы:

./test
index of 'abc' is 0
index of 'ABC' is 0
index of 'DEF' is 1
index of 'xyz' is 3

Answer 4

использование find_if предоставление пользовательского предиката:

find_if (myvector.begin(), myvector.end(), MyPredicate);

http://www.cplusplus.com/reference/algorithm/find_if/

Также см. Это для получения справки по написанию многократно используемого предиката: Создание карты :: операция поискарегистронезависимый

Answer 5

std::find не поддерживает параметр предиката, поэтому правильный алгоритм, который вы ищете: std::find_if.

std::find_if( vec.begin(), vec.end(), InsensitiveCompare("search string") );

... где InsensitiveCompare - функтор, который возвращает true для сравнения без учета регистра. Например:

struct InsensitiveCompare
{
  std::string comp;

  InsensitiveCompare( std::string const &s ) : comp(s) {}

  bool operator() ( std::string const &test ) const
  {
    // return true here if test compares with comp.
  }
}

Answer 6

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

Answer 7

Вы можете использовать find из заголовка algorithm, чтобы найти определенное значение в контейнере, но я не думаю, что он использует алгоритм двоичного поиска (нет предварительных условий для сортировки контейнера перед его передачей вfind).Более подробную информацию можно найти здесь .

В algorithm также доступно binary_search, опять же более подробная информация здесь .