By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
457,911 Members | 1,137 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 457,911 IT Pros & Developers. It's quick & easy.

STL find algorithm

P: n/a
Hi,

I've a question on the STL find algorithm:
My code:

int main( void )
{
vector< ClassA* myVector;

ClassA *ptrElement1 = ...;

myVector.push_front( ptrElement1 );
...

ClassA *ptrElement2 = *(myVector.begin());

vector< ClassA* >::iterator it =
find( myVector.begin(), myVector.end(), ptrElement2 );

...
}

What is used here in the 'find' algorithm for finding 'ptrElement2'?
Since 'ptrElement2' is just a pointer (so it's a variable storing an
address), I assume that each element (also pointers) in the list is
compared with 'ptrElement2' by using the operator== on the
addresses they represent, i.e. it is checked if

(address stored in any element in the list) ==
(address stored in 'ptrElement2')

Is my assumption correct?

However, this is probably rarely wanted. Usually one want to compare
the objects (and not their addresses). To achieve this, one must
dereference ptrElement2 in the 'find' algorithm and additionally make sure
that ClassA provides a proper operator==. Right?

Regards,
Chris
Aug 20 '06 #1
Share this Question
Share on Google+
10 Replies


P: n/a
Christian Chrismann wrote:
Is my assumption correct?
Yes
Usually one want to compare
the objects (and not their addresses). To achieve this, one must
dereference ptrElement2 in the 'find' algorithm and additionally make sure
that ClassA provides a proper operator==. Right?
Yes, one way of doing this is to use find_if and provide a function as
the third argument defined as:

bool comp(ClassA const* lhs, ClassA const* rhs) { return *lhs == *rhs; }

Another one is to make your ClassA (cheaply) copyable:

class ClassA
{
public:
// ctor, functions, but no data members, which all live in impl

operator ==(ClassA const& other);
private:
boost::shared_ptr< Impl impl;
};

That way, it's cheap and feasible to use a vector of ClassAs directly
and thus you can search for it directly. Classes you use as types and
deal with very often are worth building that way.

Then there are some more bizarre alternatives, all of them require boost:

- boost::lambda

find_if(myVector.begin(), myVector.end(), *_1 == someClassA)

- boost::indirect_iterator

boost::indirect_iterator< ClassA const* >
indirect_first(myVector.begin()), indirect_last(myVector.end());
find(indirect_first, indirect_last, someClassA);

- boost::pointer_container

boost::ptr_vector< ClassA myPVector;
find(myPVector.begin(), myPVector.end(), someClassA);
I would use one of the first two solutions at first though.

Jens
Aug 20 '06 #2

P: n/a

"Christian Chrismann" <pl*****@yahoo.deskrev i meddelandet
news:44**********************@newsspool1.arcor-online.net...
Hi,

I've a question on the STL find algorithm:
My code:

int main( void )
{
vector< ClassA* myVector;
It is very unusual to store pointers in a vector. It leads to all
kinds of "interesting" problems. The standard containers are designed
to be value based.
>
ClassA *ptrElement1 = ...;

myVector.push_front( ptrElement1 );
...

ClassA *ptrElement2 = *(myVector.begin());

vector< ClassA* >::iterator it =
find( myVector.begin(), myVector.end(), ptrElement2 );

...
}

What is used here in the 'find' algorithm for finding 'ptrElement2'?
Since 'ptrElement2' is just a pointer (so it's a variable storing an
address), I assume that each element (also pointers) in the list is
compared with 'ptrElement2' by using the operator== on the
addresses they represent, i.e. it is checked if

(address stored in any element in the list) ==
(address stored in 'ptrElement2')

Is my assumption correct?
Right. You store pointers in the vector, so the find() looks for a
specific pointer.
>
However, this is probably rarely wanted. Usually one want to compare
the objects (and not their addresses). To achieve this, one must
dereference ptrElement2 in the 'find' algorithm and additionally
make sure
that ClassA provides a proper operator==. Right?
Yes. There is another variant of std::find, find_if, that instead of a
value take a function or a function like object. That way you can get
any kind of comparison you like.

The easier way if of course to store the ClassA objects in the vector,
and not use pointers.
Bo Persson
Aug 20 '06 #3

P: n/a
Bo Persson wrote:
>
"Christian Chrismann" <pl*****@yahoo.deskrev i meddelandet
news:44**********************@newsspool1.arcor-online.net...
>Hi,

I've a question on the STL find algorithm:
My code:

int main( void )
{
vector< ClassA* myVector;

It is very unusual to store pointers in a vector. It leads to all
kinds of "interesting" problems. The standard containers are designed
to be value based.
Why would it be unusual? Storing pointers to objects that are owned by
some other entity in a vector is fairly common and there is nothing
wrong with it.

Aug 20 '06 #4

P: n/a
Jens Theisen wrote:
Christian Chrismann wrote:
>Is my assumption correct?

Yes
>Usually one want to compare
the objects (and not their addresses). To achieve this, one must
dereference ptrElement2 in the 'find' algorithm and additionally make
sure that ClassA provides a proper operator==. Right?

Yes, one way of doing this is to use find_if and provide a function as
the third argument defined as:

bool comp(ClassA const* lhs, ClassA const* rhs) { return *lhs == *rhs;
}
Doesn't work. find_if expects a predicate as its third argument not a
comparison function. You would need something like (not tested):

class Comp
{
public:
Comp(const ClassA *const p) : p_(p) {}
bool operator()(const ClassA *const q) {return *q == *p_;}

private:
const ClassA *p_;
};

Aug 20 '06 #5

P: n/a
Markus Schoder wrote:
Bo Persson wrote:
>"Christian Chrismann" <pl*****@yahoo.deskrev i meddelandet
news:44**********************@newsspool1.arcor-online.net...
>>Hi,

I've a question on the STL find algorithm:
My code:

int main( void )
{
vector< ClassA* myVector;
It is very unusual to store pointers in a vector. It leads to all
kinds of "interesting" problems. The standard containers are designed
to be value based.

Why would it be unusual? Storing pointers to objects that are owned by
some other entity in a vector is fairly common and there is nothing
wrong with it.
Not to mention that storing pointers in a vector (or any other
container) is the only way to store polymorphic objects in it.
Aug 20 '06 #6

P: n/a
red floyd wrote:
Markus Schoder wrote:
>Bo Persson wrote:
>>"Christian Chrismann" <pl*****@yahoo.deskrev i meddelandet
news:44**********************@newsspool1.arcor-online.net...
Hi,

I've a question on the STL find algorithm:
My code:

int main( void )
{
vector< ClassA* myVector;
It is very unusual to store pointers in a vector. It leads to all
kinds of "interesting" problems. The standard containers are
designed to be value based.

Why would it be unusual? Storing pointers to objects that are owned
by some other entity in a vector is fairly common and there is
nothing wrong with it.

Not to mention that storing pointers in a vector (or any other
container) is the only way to store polymorphic objects in it.
Fortunately not the only way. I happen to use smart pointer objects for
that mostly.

Aug 20 '06 #7

P: n/a

"Markus Schoder" <a3*************@yahoo.deskrev i meddelandet
news:44**********************@newsspool1.arcor-online.net...
Bo Persson wrote:
>>
"Christian Chrismann" <pl*****@yahoo.deskrev i meddelandet
news:44**********************@newsspool1.arcor-online.net...
>>Hi,

I've a question on the STL find algorithm:
My code:

int main( void )
{
vector< ClassA* myVector;

It is very unusual to store pointers in a vector. It leads to all
kinds of "interesting" problems. The standard containers are
designed
to be value based.

Why would it be unusual? Storing pointers to objects that are owned
by
some other entity in a vector is fairly common and there is nothing
wrong with it.
Ok, I take back the "very" from "very unusual".

We have had several posters today that attempt to store pointers or
references in a vector or a list, to try to gain some perceived
efficiency. Instead they got all kinds of problems, like lifetimes,
ownership, and extra indirections. Not to mention additional code to
compensate for the "efficiency" of not copying their objects.

The standard way is to store values in the containers, and let them
manage lifetimes, etc.

If you know what you are doing, and are extra careful, you can store
pointers as well, but it is generally not a good idea. This is where
you have the option of blowing your leg off.
Bo Persson
"In C++ it's harder to shoot yourself in the foot, but when you do,
you blow off your whole leg."
- Bjarne Stroustrup.

Aug 20 '06 #8

P: n/a
Markus Schoder wrote:
Doesn't work. find_if expects a predicate as its third argument not a
comparison function. You would need something like (not tested):
True

Jens
Aug 20 '06 #9

P: n/a
Markus Schoder wrote:
red floyd wrote:
>Not to mention that storing pointers in a vector (or any other
container) is the only way to store polymorphic objects in it.

Fortunately not the only way. I happen to use smart pointer objects for
that mostly.
The Standard doesn't provide any smart pointers (no, auto_ptr<doesn't
count), and some of us don't have access to Boost (for various reasons).
Aug 21 '06 #10

P: n/a
red floyd wrote:
Markus Schoder wrote:
>red floyd wrote:
>>Not to mention that storing pointers in a vector (or any other
container) is the only way to store polymorphic objects in it.

Fortunately not the only way. I happen to use smart pointer objects for
that mostly.

The Standard doesn't provide any smart pointers (no, auto_ptr<doesn't
count), and some of us don't have access to Boost (for various reasons).
So what? A straight forward implementation of a simple reference counted
shared pointer template is a little more than 100 lines of code. A simple
smart pointer with deep-copy semantics has the same complexity. Clearly
worth the effort when your shop has a policy banning third-party code.

Anyway, shared_ptr is part of tr1. So it's practically standard.
Best

Kai-Uwe Bux
Aug 21 '06 #11

This discussion thread is closed

Replies have been disabled for this discussion.