Finding an element in a container

Discussion in 'C++' started by techie, May 15, 2007.

  1. techie

    techie Guest

    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?
     
    techie, May 15, 2007
    #1
    1. Advertising

  2. techie

    Fei Liu Guest

    techie wrote:
    > 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...
     
    Fei Liu, May 15, 2007
    #2
    1. Advertising

  3. techie

    peter koch Guest

    On 15 Maj, 16:07, techie <> wrote:
    > 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
     
    peter koch, May 15, 2007
    #3
  4. techie

    Zeppe Guest

    techie wrote:

    > 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
     
    Zeppe, May 15, 2007
    #4
  5. techie

    James Kanze Guest

    On May 15, 4:07 pm, techie <> wrote:
    > 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.)

    --
    James Kanze (GABI Software) email:
    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
     
    James Kanze, May 16, 2007
    #5
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Vivi Orunitia
    Replies:
    11
    Views:
    4,481
    Martijn Lievaart
    Feb 4, 2004
  2. Maitre Bart
    Replies:
    2
    Views:
    526
    Maitre Bart
    Feb 11, 2004
  3. Steven T. Hatton
    Replies:
    4
    Views:
    3,905
    Rob Williscroft
    Dec 5, 2004
  4. Replies:
    4
    Views:
    804
    Daniel T.
    Feb 16, 2006
  5. HANM
    Replies:
    2
    Views:
    723
    Joseph Kesselman
    Jan 29, 2008
Loading...

Share This Page