Finding an element in a container

T

techie

I want to find an element in a sequence or map by comparing its value
(not the key). I can search for an element with a particular value in
a sequence or map by iterating through the elements one by one using
an iterator for the container. I could alternatively use the the
std::find or std::find_if algorithms to find an element in a sequence
or map respectively. For example, to find an element in a map I could
write a function object to check the value of an element:
http://www.josuttis.com/libbook/cont/mapfind.cpp.html

I guess internally the std::find or std::find_if internally use
iterators to search for an element. Is there any advantage of using
the algorithms over for loops that use iterators. What is the best
most efficient method? Using algorithms or using iterators?
 
F

Fei Liu

techie said:
I want to find an element in a sequence or map by comparing its value
(not the key). I can search for an element with a particular value in
a sequence or map by iterating through the elements one by one using
an iterator for the container. I could alternatively use the the
std::find or std::find_if algorithms to find an element in a sequence
or map respectively. For example, to find an element in a map I could
write a function object to check the value of an element:
http://www.josuttis.com/libbook/cont/mapfind.cpp.html

I guess internally the std::find or std::find_if internally use
iterators to search for an element. Is there any advantage of using
the algorithms over for loops that use iterators. What is the best
most efficient method? Using algorithms or using iterators?
algorithm, no need to reinvent the the wheel...
 
P

peter koch

I want to find an element in a sequence or map by comparing its value
(not the key).
[snip]

I guess internally the std::find or std::find_if internally use
iterators to search for an element. Is there any advantage of using
the algorithms over for loops that use iterators. What is the best
most efficient method? Using algorithms or using iterators?

The most efficient method would often be std::find_if, the exception
possibly being if lots of local state needs to be copied. The reason
is that knowledge of the container can often lead to more efficient
algorithms. But do not expect anything better than a (small) constant
factor.

/Peter
 
Z

Zeppe

techie said:
I guess internally the std::find or std::find_if internally use
iterators to search for an element. Is there any advantage of using
the algorithms over for loops that use iterators. What is the best
most efficient method? Using algorithms or using iterators?

The advantage is the clearness. Usually when you have to search for an
element a good std::find_if is very crear and nice, even if you have to
write two lines of code for the comparison function. Otherwise, if it
happens that a for with the iterators is just a faster and cleanest way
to perform the search in some particular case for whatever reason, just
go that way, your choice.

Regards,

Zeppe
 
J

James Kanze

I want to find an element in a sequence or map by comparing its value
(not the key). I can search for an element with a particular value in
a sequence or map by iterating through the elements one by one using
an iterator for the container. I could alternatively use the the
std::find or std::find_if algorithms to find an element in a sequence
or map respectively. For example, to find an element in a map I could
write a function object to check the value of an element:http://www.josuttis.com/libbook/cont/mapfind.cpp.html
I guess internally the std::find or std::find_if internally use
iterators to search for an element. Is there any advantage of using
the algorithms over for loops that use iterators. What is the best
most efficient method? Using algorithms or using iterators?

There is no real difference in efficiency. In both cases, you
are doing a linear search. The advantage of find or find_if is
that the name of the function says this immediately, up front.
The disadvantage is that if you don't already have a
predicate handy for the job, you have to write one---if the
logic of the predicate is connected to the logic of the calling
function, this means separating the logic into two separate
places, since the predicate cannot be a local class. (Normally,
this will very rarely be the case, unless you write functions
which are too complex to begin with. But it's still not always
the most readable solution to replace a three token in the loop
predicate with a full class definition outside of the function.)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,906
Latest member
SkinfixSkintag

Latest Threads

Top