Re: Searching in sorted containers
Ulrich Eckhardt wrote:
[Someone] wrote:
class A {
public:
const string& getName() const;
bool operator<(const A& rhs) const {
return getName() < rhs.getName();
}
/* more fields and methods here */
};
and that we have a container sorted on the value of the
getName() method.
How can one search for the item with a given value of the
getName() method knowing that algorithms like
std::lower_bound wouldn't accept a string as a search item?
You can't. The typical workaround is to create a temporary A
that matches the searched one or to simply use find_if with
iterators. Obvious disadvantages are that one requires the
(possibly costly) creation of an object and the other only
does linear search.
As Thomas Maeder pointed out, you can. The standard guarantees
the order of the parameters when calling the predicate object in
lower_bound, and makes no requirement that the value type of the
iterator correspond in any way to the type of the third
parameter. (On the other hand, there is a rather obvious error
in the standard in that it requires the type of the third
parameter to be LessThanComparable, even when you provide the
comparison function.)
That said, I know that the STLport standardlibrary (currently
only the unreleased CVS version) contains an extension that
allows you to specify anything in place of the key for the
sorted containers, provided the sorting predicate has
operator() overloads not only for the key-type but also for
the other type. Take a look at the unittests for examples.
That sounds useful. Of course, since the order of the
parameters are passed to the comparison function in sorted isn't
defined, you need three overloads. (But the original question,
of course, concerned lower_bound.)
--
James Kanze GABI Software
Conseils en informatique orient?e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S?mard, 78210 St.-Cyr-l'?cole, France, +33 (0)1 30 23 00 34
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]