Searching in sorted containers
Ванко Патиланко
suppose we have the following class:
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?
I need to write something like:
std::vector<A> v;
/* Fill v */
std::sort(v.begin(), v.end());
std::lower_bound(v.begin(), v.end(), /* want to put a string here */));
Thanks in advance
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Thomas Maeder
Ванко Патиланко <ivan.bo...@gmail.com> writes:
> 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?
>
> I need to write something like:
>
> std::vector<A> v;
> /* Fill v */
> std::sort(v.begin(), v.end());
> std::lower_bound(v.begin(), v.end(), /* want to put a string here */));
Use the 4 argument form of std::lower_bound and pass a predicate that
compares an A object and a std::string.
Carl Barron
<ivan.bo...@gmail.com> wrote:
> Hello all,
>
> suppose we have the following class:
>
> 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?
>
> I need to write something like:
>
> std::vector<A> v;
> /* Fill v */
> std::sort(v.begin(), v.end());
> std::lower_bound(v.begin(), v.end(), /* want to put a string here */));
>
> Thanks in advance
>
since A is ordered by the member function getName(). The simplest
solution without further information on class A is to use
boost::transform_iterator. Something like:
std::vector<A>::iterator = std::lower_bound
(
boost::make_transform_iterator(v.begin(),
std::mem_fun_ref(&A::getName));
boost::make_transform_iterator(v.end(),
std::mem_fun_ref(&A::getName)),
the_string
).base();
comes to mind. The boost::make_transform_iterator's above create
a random access iterator whose value_type is std::string and iterates
through the vector. The created iterator has a member function base
which converts the created iterator back to the original iterator.
Ulrich Eckhardt
> 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.
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.
Uli
kanze
> [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
Greg Herlihy
> Hello all,
>
> suppose we have the following class:
>
> 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?
>
> I need to write something like:
>
> std::vector<A> v;
> /* Fill v */
> std::sort(v.begin(), v.end());
> std::lower_bound(v.begin(), v.end(), /* want to put a string here */));
The easiest solution would be to overload the < (less than) operator
with a std::string and a class A object as its operands:
bool operator<(const A& lhs, const std::string& rhs)
{
return lhs.getName() < rhs;
}
bool operator<(const std::string& lhs, const A& rhs)
{
return lhs < rhs.getName();
}
int main()
{
std::vector<A> v;
/* Fill v */
std::sort(v.begin(), v.end());
// "search" converts to a std::string...
std::lower_bound(v.begin(), v.end(), "search");
}
Greg