H
Caligulaminus schrieb:
it = std::lower_bound insensitive
while it != Ende && *it equals string insensitive
if *it equals string sensitive
...
++it
Arcoth schrieb:
Wo liegt das Problem? Du kannst doch die Range von Elementen konstruieren, die passen. D.h. alle, die mit ca, cA, Ca oder CA beginnen. Diese ist natürlich unsortiert, aber eine lineare Suche ist effizient genug.
Hm, ihr hab recht, hab ich wohl zu kompliziert gedacht...
Ich hab es jetzt so implementiert und es klappt:
#include <iostream>
#include <algorithm>
#include <string>
#include <cctype>
struct comparator_no_case
{
bool operator()(std::string const &lhs, std::string const &rhs) const
{
return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), [](char c1, char c2)
{
return tolower(c1) < tolower(c2);
});
}
};
struct predicate_exact_match
{
bool operator()(std::string const &lhs, std::string const &rhs) const
{
return lhs == rhs;
}
};
template<class ForwardIt, class T, class Compare>
ForwardIt binary_search_iter(ForwardIt first, ForwardIt last, T const &value, Compare comp)
{
first = std::lower_bound(first, last, value, comp);
return first != last && !comp(value, *first) ? first : last;
}
template<class ForwardIt, class T, class SortCompare, class SearchPredicate>
ForwardIt binary_search_with_predicate(ForwardIt first, ForwardIt last, T const &value, SortCompare sort_comp, SearchPredicate search_pred)
{
auto it = binary_search_iter(first, last, value, sort_comp);
while (it != last && !sort_comp(*it, value))
{
if (search_pred(*it, value))
return it;
++it;
}
return last;
}
int main()
{
std::vector<std::string> x = { "B", "aB", "uGG", "LaB", "ttA", "cA", "AB", "Kcc", "CA", "bbA" };
std::sort(x.begin(), x.end(), comparator_no_case());
for (auto const &xi : x)
std::cout << xi << "\n";
auto it = binary_search_with_predicate(x.begin(), x.end(), "CA", comparator_no_case(), predicate_exact_match());
if (it != x.end())
std::cout << "\nfound item: " << *it << "\n\n"; // Got "CA"
}
