473,320 Members | 2,097 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

lower_bound

=============================
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
4 4284
"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

"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
"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
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
by: Jim West | last post by:
The following code does what I want it to do on two different compilers (g++ and Intel icc under Linux), but I'm not sure if it is undefined and just happens to work: class A { public: int...
3
by: Jaap | last post by:
Hi all, I'm looking for functionality very similar to std::map::lower_bound: I'd like to find the first element whose key is equal to or smaller than the key I pass. In a map filled like...
3
by: Allerdyce.John | last post by:
On page 181 of Effective STL, it said 'It 's knowning when equal_range is a better way to search than lower_bound, knowing when lower bound is preferable to find..." My question is understand...
3
by: Diego Martins | last post by:
Andrew Koenig wrote:
3
by: could.net | last post by:
I have a class board, like this: struct board { int x1, x2, h; int time1, time2; void calculate_time(); void assign(int x1__,int x2__,int h__); }; And I have n boards stored in an array...
1
by: phdscholar80 | last post by:
I am using the following code: #include <vector> #include <algorithm> class A { }; bool comparator( A * b, const char * a )
0
by: mathieu | last post by:
hi there, I do not understand why the following piece of code is not working for me. I have a set of cstrings, where I am trying to find one 'UT'. If I search from "AE" to "OB or OW" everything...
4
by: qlin88 | last post by:
Hi, In STL multi-map, the lower_bound, upper_bound,equal_range all return an iterator. Now ifone wants to iterate from an upper bound towards a lower bound, what would be the best way to do it?...
4
by: RiderOfGiraffes | last post by:
Hi, I'm trying to compile (someone else's) code on SuSE 11.0. It worked fine on SuSE 10.3, but now it's telling me that lower_bound is not a member of std. I'm assuming something has changed...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.