Question on find on a vector - is it just a linear search?

Discussion in 'C++' started by Angus, Mar 22, 2011.

  1. Angus

    Angus Guest

    I assume that find on a vector is a linear search a bit like iterating
    through the items in vector until first instance found?

    If so, then I suppose it is slightly more convenient than writing code
    to iterate vector.

    If more than the odd search required obviously would be better to sort
    vector and use lower_bound I guess.
    Angus, Mar 22, 2011
    #1
    1. Advertising

  2. Angus

    Noah Roberts Guest

    On 3/22/2011 7:52 AM, Angus wrote:
    > I assume that find on a vector is a linear search a bit like iterating
    > through the items in vector until first instance found?
    >
    > If so, then I suppose it is slightly more convenient than writing code
    > to iterate vector.
    >
    > If more than the odd search required obviously would be better to sort
    > vector and use lower_bound I guess.
    >


    There's also std::binary_search.

    --
    http://crazycpp.wordpress.com
    Noah Roberts, Mar 22, 2011
    #2
    1. Advertising

  3. Angus

    Jeff Flinn Guest

    Noah Roberts wrote:
    > On 3/22/2011 7:52 AM, Angus wrote:
    >> I assume that find on a vector is a linear search a bit like iterating
    >> through the items in vector until first instance found?
    >>
    >> If so, then I suppose it is slightly more convenient than writing code
    >> to iterate vector.
    >>
    >> If more than the odd search required obviously would be better to sort
    >> vector and use lower_bound I guess.
    >>

    >
    > There's also std::binary_search.


    That only tells you whether the item is contained in a sorted sequence,
    it doesn't return an iterator to the found item as does find or lower_bound.

    Jeff
    Jeff Flinn, Mar 23, 2011
    #3
  4. Jeff Flinn <> wrote:
    > That only tells you whether the item is contained in a sorted sequence,
    > it doesn't return an iterator to the found item as does find or lower_bound.


    Technically speaking std::lower_bound does not return an iterator to
    an element in the container that is equal to the searched element. It
    returns an iterator to the first location where, if you inserted the
    searched element, the container would still be sorted.

    If the searched element was already in the container, then that
    location happens to contain the first such element. However, more
    importantly, if the searched element is not already in the container,
    the iterator will still just point to somewhere in the container
    (according to the abovementioned rule). In order to see if the searched
    element is there you will have to compare the element pointed by the
    iterator to the searched element explicitly (taking into account that
    the iterator could point to the end of the container).
    Juha Nieminen, Mar 24, 2011
    #4
  5. Angus

    Angus Guest

    On Mar 24, 9:08 am, Juha Nieminen <> wrote:
    > Jeff Flinn <> wrote:
    > > That only tells you whether the item is contained in a sorted sequence,
    > > it doesn't return an iterator to the found item as does find or lower_bound.

    >
    >   Technically speaking std::lower_bound does not return an iterator to
    > an element in the container that is equal to the searched element. It
    > returns an iterator to the first location where, if you inserted the
    > searched element, the container would still be sorted.
    >
    >   If the searched element was already in the container, then that
    > location happens to contain the first such element. However, more
    > importantly, if the searched element is not already in the container,
    > the iterator will still just point to somewhere in the container
    > (according to the abovementioned rule). In order to see if the searched
    > element is there you will have to compare the element pointed by the
    > iterator to the searched element explicitly (taking into account that
    > the iterator could point to the end of the container).


    I don't think this is correct. Because if the item is NOT in the list
    then the iterator returned is the end of the container. This
    conflicts with your analysis.
    Angus, Mar 24, 2011
    #5
  6. Angus

    Jeff Flinn Guest

    Angus wrote:
    > On Mar 24, 9:08 am, Juha Nieminen <> wrote:
    >> Jeff Flinn <> wrote:
    >>> That only tells you whether the item is contained in a sorted sequence,
    >>> it doesn't return an iterator to the found item as does find or lower_bound.

    >> Technically speaking std::lower_bound does not return an iterator to
    >> an element in the container that is equal to the searched element. It
    >> returns an iterator to the first location where, if you inserted the
    >> searched element, the container would still be sorted.
    >>
    >> If the searched element was already in the container, then that
    >> location happens to contain the first such element. However, more
    >> importantly, if the searched element is not already in the container,
    >> the iterator will still just point to somewhere in the container
    >> (according to the above mentioned rule). In order to see if the searched
    >> element is there you will have to compare the element pointed by the
    >> iterator to the searched element explicitly (taking into account that
    >> the iterator could point to the end of the container).

    >
    > I don't think this is correct. Because if the item is NOT in the list
    > then the iterator returned is the end of the container. This
    > conflicts with your analysis.


    Juha is correct. Can you provide an example disproving him?

    In any case, maybe your design would be better implemented with a
    std::set or std::map which provide find methods to give the behavior you
    require.

    Jeff
    Jeff Flinn, Mar 24, 2011
    #6
  7. Angus

    James Kanze Guest

    On Mar 24, 11:11 am, Angus <> wrote:
    > On Mar 24, 9:08 am, Juha Nieminen <> wrote:
    > > Jeff Flinn <> wrote:
    > > > That only tells you whether the item is contained in a
    > > > sorted sequence, it doesn't return an iterator to the
    > > > found item as does find or lower_bound.


    > > Technically speaking std::lower_bound does not return an
    > > iterator to an element in the container that is equal to the
    > > searched element. It returns an iterator to the first
    > > location where, if you inserted the searched element, the
    > > container would still be sorted.


    That's not just a technicality. It's the basic definition of
    lower_bound.

    > > If the searched element was already in the container, then that
    > > location happens to contain the first such element. However, more
    > > importantly, if the searched element is not already in the container,
    > > the iterator will still just point to somewhere in the container
    > > (according to the abovementioned rule). In order to see if the searched
    > > element is there you will have to compare the element pointed by the
    > > iterator to the searched element explicitly (taking into account that
    > > the iterator could point to the end of the container).


    > I don't think this is correct. Because if the item is NOT in the list
    > then the iterator returned is the end of the container. This
    > conflicts with your analysis.


    I'd suggest you look up the specification of lower_bound. It
    returns an iterator to the first element less than or equal to
    the search item.

    --
    James Kanze
    James Kanze, Mar 26, 2011
    #7
  8. Angus

    James Kanze Guest

    On Mar 22, 4:53 pm, cg_chas <> wrote:
    > On Tue, 22 Mar 2011 07:52:05 -0700 (PDT), Angus <> wrote:

    [...]
    > >If more than the odd search required obviously would be better to sort
    > >vector and use lower_bound I guess.


    > this can be expensive since a vector guarantees contiguous memory storage.


    Why does contiguous memory make sorting and binary search more
    expensive? If anything, it makes them less expensive (because
    of improved locality).

    --
    James Kanze
    James Kanze, Mar 26, 2011
    #8
  9. On 26 mar, 14:27, Leigh Johnston <> wrote:
    > On 26/03/2011 13:17, James Kanze wrote:
    >
    >
    >
    >
    >
    >
    >
    >
    >
    > > On Mar 24, 11:11 am, Angus<>  wrote:
    > >> On Mar 24, 9:08 am, Juha Nieminen<>  wrote:
    > >>> Jeff Flinn<>  wrote:
    > >>>> That only tells you whether the item is contained in a
    > >>>> sorted sequence, it doesn't return an iterator to the
    > >>>> found item as does find or lower_bound.

    >
    > >>> Technically speaking std::lower_bound does not return an
    > >>> iterator to an element in the container that is equal to the
    > >>> searched element. It returns an iterator to the first
    > >>> location where, if you inserted the searched element, the
    > >>> container would still be sorted.

    >
    > > That's not just a technicality.  It's the basic definition of
    > > lower_bound.

    >
    > >>> If the searched element was already in the container, then that
    > >>> location happens to contain the first such element. However, more
    > >>> importantly, if the searched element is not already in the container,
    > >>> the iterator will still just point to somewhere in the container
    > >>> (according to the abovementioned rule). In order to see if the searched
    > >>> element is there you will have to compare the element pointed by the
    > >>> iterator to the searched element explicitly (taking into account that
    > >>> the iterator could point to the end of the container).

    >
    > >> I don't think this is correct.  Because if the item is NOT in the list
    > >> then the iterator returned is the end of the container.  This
    > >> conflicts with your analysis.

    >
    > > I'd suggest you look up the specification of lower_bound.  It
    > > returns an iterator to the first element less than or equal to
    > > the search item.

    >
    > Not true; lower_bound will return an iterator to the first element
    > *greater* than or equal to the search item or an iterator to the end of
    > the range.


    Nitpicking: Formally it returns the iterator to the first element that
    doesn't compare strictly less than the search item (or end of range
    failing that).

    This is of course mathematic
    Michael Doubez, Mar 26, 2011
    #9
  10. Angus

    Angus Guest

    On Mar 24, 2:11 pm, Jeff Flinn <> wrote:
    > Angus wrote:
    > > On Mar 24, 9:08 am, Juha Nieminen <> wrote:
    > >> Jeff Flinn <> wrote:
    > >>> That only tells you whether the item is contained in a sorted sequence,
    > >>> it doesn't return an iterator to the found item as does find or lower_bound.
    > >>   Technically speaking std::lower_bound does not return an iterator to
    > >> an element in the container that is equal to the searched element. It
    > >> returns an iterator to the first location where, if you inserted the
    > >> searched element, the container would still be sorted.

    >
    > >>   If the searched element was already in the container, then that
    > >> location happens to contain the first such element. However, more
    > >> importantly, if the searched element is not already in the container,
    > >> the iterator will still just point to somewhere in the container
    > >> (according to the above mentioned rule). In order to see if the searched
    > >> element is there you will have to compare the element pointed by the
    > >> iterator to the searched element explicitly (taking into account that
    > >> the iterator could point to the end of the container).

    >
    > > I don't think this is correct.  Because if the item is NOT in the list
    > > then the iterator returned is the end of the container.  This
    > > conflicts with your analysis.

    >
    > Juha is correct. Can you provide an example disproving him?
    >
    > In any case, maybe your design would be better implemented with a
    > std::set or std::map which provide find methods to give the behavior you
    > require.
    >
    > Jeff


    Sorry, yes you are correct. You have to also check iterator returned
    is the same value as value searched.
    Angus, Mar 28, 2011
    #10
  11. Angus

    James Kanze Guest

    On Mar 26, 2:27 pm, Leigh Johnston <> wrote:
    > On 26/03/2011 13:17, James Kanze wrote:


    [...]
    > > I'd suggest you look up the specification of lower_bound. It
    > > returns an iterator to the first element less than or equal to
    > > the search item.


    > Not true; lower_bound will return an iterator to the first element
    > *greater* than or equal to the search item or an iterator to the end of
    > the range.


    Oops. Typo on my part. (Formally, the standard words it a
    little different, but what it comes out to is >=.)

    --
    James Kanze
    James Kanze, Mar 28, 2011
    #11
    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. Replies:
    1
    Views:
    1,095
    Roedy Green
    Nov 15, 2005
  2. kjm
    Replies:
    6
    Views:
    734
  3. Replies:
    8
    Views:
    1,894
    Csaba
    Feb 18, 2006
  4. mathieu
    Replies:
    1
    Views:
    308
    David Côme
    Apr 25, 2008
  5. sanborne
    Replies:
    5
    Views:
    1,990
Loading...

Share This Page