C++Talk.NET Forum Index C++Talk.NET
C++ language newsgroups
 
Archives   FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Searching in sorted containers

 
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ Language (Moderated)
View previous topic :: View next topic  
Author Message

Guest
PostPosted: Sun Jun 11, 2006 12:59 am    Post subject: Searching in sorted containers Reply with quote


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



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Back to top
Thomas Maeder
Guest
PostPosted: Mon Jun 12, 2006 2:36 am    Post subject: Re: Searching in sorted containers Reply with quote


<ivan.bogouchev (AT) gmail (DOT) com> writes:

Quote:
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.


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Back to top
Carl Barron
Guest
PostPosted: Mon Jun 12, 2006 2:37 am    Post subject: Re: Searching in sorted containers Reply with quote


In article <448b045c$0$27289$626a54ce (AT) news (DOT) free.fr>,
<ivan.bogouchev (AT) gmail (DOT) com> wrote:

Quote:
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.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Back to top
Ulrich Eckhardt
Guest
PostPosted: Mon Jun 12, 2006 2:42 am    Post subject: Re: Searching in sorted containers Reply with quote
Ванко Патиланко wrote:
Quote:
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




[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Back to top
kanze
Guest
PostPosted: Wed Jun 14, 2006 3:31 pm    Post subject: Re: Searching in sorted containers Reply with quote
Ulrich Eckhardt wrote:
Quote:
[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.)

Quote:
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 oriente objet/
Beratung in objektorientierter Datenverarbeitung
9 place Smard, 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! ]
Back to top
Greg Herlihy
Guest
PostPosted: Wed Jun 14, 2006 10:01 pm    Post subject: Re: Searching in sorted containers Reply with quote
Ванко ПатиЛанко wrote:
Quote:
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


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Back to top
Display posts from previous:   
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2006 phpBB Group
SEO toolkit © 2004-2006 webmedic.