Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   std::binary_search(), iterator to the found element and timecomplexity (http://www.velocityreviews.com/forums/t651627-std-binary_search-iterator-to-the-found-element-and-timecomplexity.html)

Alex Vinokur 01-07-2009 06:49 AM

std::binary_search(), iterator to the found element and timecomplexity
 
Hi,

std::binary_search() takes logarithmic time on (sorted) container, but
returns bool, not iterator to the found element.

std::find() returns iterator to the found element, but takes linear
time.

Is there any way to get iterator to the found element on sorted
container in logarithmic time?

Alex Vinokur


Thomas J. Gritzan 01-07-2009 06:57 AM

Re: std::binary_search(), iterator to the found element and timecomplexity
 
Alex Vinokur schrieb:
> Hi,
>
> std::binary_search() takes logarithmic time on (sorted) container, but
> returns bool, not iterator to the found element.
>
> std::find() returns iterator to the found element, but takes linear
> time.
>
> Is there any way to get iterator to the found element on sorted
> container in logarithmic time?


std::lower_bound, std::upper_bound, std::equal_range

--
Thomas

Maxim Yegorushkin 01-07-2009 10:44 AM

Re: std::binary_search(), iterator to the found element and timecomplexity
 
On Jan 7, 6:49*am, Alex Vinokur <ale...@users.sourceforge.net> wrote:

> std::binary_search() takes logarithmic time on (sorted) container, but
> returns bool, not iterator to the found element.
>
> std::find() returns iterator to the found element, but takes linear
> time.
>
> Is there any way to get iterator to the found element on sorted
> container in logarithmic time?


It is:

template<class Iter, class T>
Iter binary_search_iter(Iter begin, Iter end, T val)
{
Iter i = std::lower_bound(begin, end, val);
return i != end && *i == val
? i // found
: end // not found
;
}

--
Max


All times are GMT. The time now is 07:24 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.