By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,233 Members | 1,806 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,233 IT Pros & Developers. It's quick & easy.

lower_bound

P: n/a
=============================
Windows 2000
MinGW 2.0.0.-2
GNU gcc/g++ version 3.2
=============================

I have some question concerning the lower_bound algorithm.

========= C++ code : File t.cpp : BEGIN =========
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
using namespace std;

int main ()
{
typedef vector<int>::iterator iterator;

int d1[] = {0, 1, 2, 1, 3, 4, 2, 2, 2, 6, 7};
int d2[] = {0, 1, 2, 1, 3, 2, 4, 2, 2, 6, 7};

const int test_value = 3;

vector<int> v1(d1, d1 + sizeof(d1)/sizeof(d1[0]));
vector<int> v2(d2, d2 + sizeof(d2)/sizeof(d2[0]));

iterator pos1 = lower_bound(v1.begin(), v1.end(), test_value);
iterator pos2 = lower_bound(v2.begin(), v2.end(), test_value);

cout << "pos1 = " << distance (v1.begin(), pos1)
<< ", value1 = " << *pos1 << endl;

cout << "pos2 = " << distance (v2.begin(), pos2)
<< ", value2 = " << *pos2 << endl;
return 0;
}
========= C++ code : File t.cpp : END ===========
========= Compilation & Run : BEGIN =========

$ g++ t.cpp

$ a

pos1 = 4, value1 = 3
pos2 = 9, value2 = 6

========= Compilation & Run : END ===========
The lower_bound algorithm returns an iterator i
in the range [first, last) such
that for any iterator j in the range [first, i)
the following corresponding conditions hold :
*j < test_value.
For vector v1 and test_value = 3 :
Returned range = [v1.begin(), v1.begin() + 4)
{0, 1, 2, 1};
It seems to be OK.
For vector v2 and test_value = 3
Returned range = [v2.begin(), v2.begin() + 9);
{0, 1, 2, 1, 3, 2, 4, 2, 2};
However the range contains two values (3 and 4)
which the *j < test_value condition is not true for.

What is wrong?

Thanks,
==========================================
Alex Vinokur
mailto:al****@connect.to
http://sourceforge.net/users/alexvn
http://www.simtel.net/search.php?act...e=Alex+Vinokur
==========================================

Jul 19 '05 #1
Share this Question
Share on Google+
4 Replies


P: n/a
"Alex Vinokur" <al****@bigfoot.com> wrote in message
news:bg************@ID-79865.news.uni-berlin.de...
=============================
Windows 2000
MinGW 2.0.0.-2
GNU gcc/g++ version 3.2
=============================

I have some question concerning the lower_bound algorithm.

========= C++ code : File t.cpp : BEGIN =========
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
using namespace std;

int main ()
{
typedef vector<int>::iterator iterator;

int d1[] = {0, 1, 2, 1, 3, 4, 2, 2, 2, 6, 7};
int d2[] = {0, 1, 2, 1, 3, 2, 4, 2, 2, 6, 7};

const int test_value = 3;

vector<int> v1(d1, d1 + sizeof(d1)/sizeof(d1[0]));
vector<int> v2(d2, d2 + sizeof(d2)/sizeof(d2[0]));

iterator pos1 = lower_bound(v1.begin(), v1.end(), test_value);
iterator pos2 = lower_bound(v2.begin(), v2.end(), test_value);

cout << "pos1 = " << distance (v1.begin(), pos1)
<< ", value1 = " << *pos1 << endl;

cout << "pos2 = " << distance (v2.begin(), pos2)
<< ", value2 = " << *pos2 << endl;
return 0;
}
========= C++ code : File t.cpp : END ===========
========= Compilation & Run : BEGIN =========

$ g++ t.cpp

$ a

pos1 = 4, value1 = 3
pos2 = 9, value2 = 6

========= Compilation & Run : END ===========
The lower_bound algorithm returns an iterator i
in the range [first, last) such
that for any iterator j in the range [first, i)
the following corresponding conditions hold :
*j < test_value.
For vector v1 and test_value = 3 :
Returned range = [v1.begin(), v1.begin() + 4)
{0, 1, 2, 1};
It seems to be OK.
For vector v2 and test_value = 3
Returned range = [v2.begin(), v2.begin() + 9);
{0, 1, 2, 1, 3, 2, 4, 2, 2};
However the range contains two values (3 and 4)
which the *j < test_value condition is not true for.

What is wrong?

Thanks,
==========================================
Alex Vinokur
mailto:al****@connect.to
http://sourceforge.net/users/alexvn
http://www.simtel.net/search.php?act...e=Alex+Vinokur
==========================================


lower_bound() assumes a sequence is sorted.
Sort the vectors before you call lower_bound().

--
ES Kim

Jul 19 '05 #2

P: n/a

"ES Kim" <es***@svd.co.kr> wrote in message news:bg**********@news1.kornet.net...
[snip]

lower_bound() assumes a sequence is sorted.
Sort the vectors before you call lower_bound().

[snip]

Thanks.

Is there any function/method which detects if a vector is sorted?

=====================================
Alex Vinokur
mailto:al****@connect.to
http://mathforum.org/library/view/10978.html
=====================================
Jul 19 '05 #3

P: n/a
"Alex Vinokur" <al****@bigfoot.com> wrote in message
news:bg************@ID-79865.news.uni-berlin.de...

"ES Kim" <es***@svd.co.kr> wrote in message news:bg**********@news1.kornet.net... [snip]

lower_bound() assumes a sequence is sorted.
Sort the vectors before you call lower_bound().

[snip]

Thanks.

Is there any function/method which detects if a vector is sorted?


None that I know of, but you can write your own function easily.

--
ES Kim
Jul 19 '05 #4

P: n/a
On Thu, 31 Jul 2003 12:35:31 +0900, ES Kim <es***@svd.co.kr> wrote:
"Alex Vinokur" <al****@bigfoot.com> wrote in message
news:bg************@ID-79865.news.uni-berlin.de...

"ES Kim" <es***@svd.co.kr> wrote in message

news:bg**********@news1.kornet.net...
[snip]
>
> lower_bound() assumes a sequence is sorted.
> Sort the vectors before you call lower_bound().

[snip]

Thanks.

Is there any function/method which detects if a vector is sorted?


None that I know of, but you can write your own function easily.


Or you could use existing STL features:

if(std::adjacent_find(v.begin(),v.end(),std::great er<value_type>())==v.end()){
//v is sorted
}

--
Sam Holden

Jul 19 '05 #5

This discussion thread is closed

Replies have been disabled for this discussion.