binary_search mit unterschiedlichem Vergleich als Sotrierung

happystudent

Hallo,

angenommen ich habe eine Liste aus strings die alphabetisch, aber Case-Insensitiv, sortiert wurde wie in folgendem Beispiel.

Bemerkung: Ich verwende hier ein eigenes binary_search , weil das aus std (aus mir nicht verständlichen Gründen) nur ein bool zurück gibt und keinen Iterator auf das gefundene Objekt (was std::binary_search relativ nutzlos für mich macht).

Die eigentliche Frage ist jetzt: eine Binärsuche kann man ja nur auf sortierten Daten ausführen. Die Daten hier sind Case-Insensitiv sortiert.
Kann ich jetzt trotzdem irgendwie mittels Binärsuche effizient nach einem Element suchen und zwar Case-Sensitiv, ohne die Liste entsprechend umsortieren zu müssen?

Im Beispiel unten will ich etwa in der Liste das Element "CA" finden (und zwar Case-Sensitiv, also exakter Match). Dafür würde ich jetzt gerne Binärsuche verwenden um die Sortierung der Daten auszunutzen. Geht das, obwohl die Sortierung nicht genau passt?

Ich verwende in dem Beispiel noch in beiden Fällen den selben Vergleich, daher ist das Ergebniss auch logischweise nicht wie erwartet "CA", sondern "cA".
Verwende ich naiverweise einfach einen Case-Sensitiven Vergleich für die Binärsuche, wird gar kein Element gefunden, das scheint also schonmal nicht zu klappen...

#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));
		});
	}
};

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;
}

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_iter(x.begin(), x.end(), "CA", comparator_no_case());

	if (it != x.end())
		std::cout << "\nfound item: " << *it << "\n\n"; // expected "CA", got "cA"
}

Caligulaminus

it = std::lower_bound insensitive
while it != Ende && *it equals string insensitive
    if *it equals string sensitive
        ...
    ++it

Columbo

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.

happystudent

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"
}