Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Question on find on a vector - is it just a linear search?

Reply
Thread Tools

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

 
 
Angus
Guest
Posts: n/a
 
      03-22-2011
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.

 
Reply With Quote
 
 
 
 
Noah Roberts
Guest
Posts: n/a
 
      03-22-2011
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
 
Reply With Quote
 
 
 
 
Jeff Flinn
Guest
Posts: n/a
 
      03-23-2011
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
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      03-24-2011
Jeff Flinn <(E-Mail Removed)> 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).
 
Reply With Quote
 
Angus
Guest
Posts: n/a
 
      03-24-2011
On Mar 24, 9:08*am, Juha Nieminen <(E-Mail Removed)> wrote:
> Jeff Flinn <(E-Mail Removed)> 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.
 
Reply With Quote
 
Jeff Flinn
Guest
Posts: n/a
 
      03-24-2011
Angus wrote:
> On Mar 24, 9:08 am, Juha Nieminen <(E-Mail Removed)> wrote:
>> Jeff Flinn <(E-Mail Removed)> 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



 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      03-26-2011
On Mar 24, 11:11 am, Angus <(E-Mail Removed)> wrote:
> On Mar 24, 9:08 am, Juha Nieminen <(E-Mail Removed)> wrote:
> > Jeff Flinn <(E-Mail Removed)> 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
 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      03-26-2011
On Mar 22, 4:53 pm, cg_chas <(E-Mail Removed)> wrote:
> On Tue, 22 Mar 2011 07:52:05 -0700 (PDT), Angus <(E-Mail Removed)> 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
 
Reply With Quote
 
Michael Doubez
Guest
Posts: n/a
 
      03-26-2011
On 26 mar, 14:27, Leigh Johnston <(E-Mail Removed)> wrote:
> On 26/03/2011 13:17, James Kanze wrote:
>
>
>
>
>
>
>
>
>
> > On Mar 24, 11:11 am, Angus<(E-Mail Removed)> *wrote:
> >> On Mar 24, 9:08 am, Juha Nieminen<(E-Mail Removed)> *wrote:
> >>> Jeff Flinn<(E-Mail Removed)> *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
 
Reply With Quote
 
Angus
Guest
Posts: n/a
 
      03-28-2011
On Mar 24, 2:11*pm, Jeff Flinn <(E-Mail Removed)> wrote:
> Angus wrote:
> > On Mar 24, 9:08 am, Juha Nieminen <(E-Mail Removed)> wrote:
> >> Jeff Flinn <(E-Mail Removed)> 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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Applying a linear transform to a std::vector<T> mathieu C++ 1 04-25-2008 03:11 PM
Initializing vector<vector<int> > and other vector questions... pmatos C++ 6 04-26-2007 05:39 PM
Free memory allocate by a STL vector, vector of vector, map of vector Allerdyce.John@gmail.com C++ 8 02-18-2006 12:48 AM
Code for linear congruences, diophantine linear equations alessandra_cabrini@virgilio.it Java 1 11-15-2005 12:23 PM
Create linear spaced vector? kjm Python 6 12-17-2004 08:29 PM



Advertisments