ATL / WTL / STL

5-Dec-02 15:50

find_if is no better than running down the collection yourself, comparing items.

is there anything that will do a binary search (with a predicate) on a sorted vector?

please don't say "binary_search" because that is a totally useless P.O.S. that only tells you if an item exists in the collection (it returns bool)- it doesn't actually give you the item. "Q: can you tell me what time it is? A: yes".

-c

There's one easy way to prove the effectiveness of 'letting the market decide' when it comes to environmental protection. It's spelt 'S-U-V'.
--Holgate, from Plastic

Taka Muraoka5-Dec-02 16:07

Taka Muraoka

5-Dec-02 16:07

You might be able to use lower_bound() or equal_range()?

I'd wear a miniskirt and pimp myself for an extra ten grand a year. - David Wulff

Awasu[^]: A free RSS reader with support for Code Project.

C^hris L^osinger5-Dec-02 18:27

5-Dec-02 18:27

close. but lower_bound doesn't really do a search. it just tells you where you could insert a new item. or, from MSDN: "[lower_bound] determines the lowest position before which val can be inserted in the sequence and still preserve its ordering".

i really need it to return the item i'm searching for, not the next-lowest value.

-c

There's one easy way to prove the effectiveness of 'letting the market decide' when it comes to environmental protection. It's spelt 'S-U-V'.
--Holgate, from Plastic

Taka Muraoka5-Dec-02 18:42

Taka Muraoka

5-Dec-02 18:42

Chris Losinger wrote:
but lower_bound doesn't really do a search.

That's right but I was thinking you could check the *next* element to see if it's the one you want.
note to self: but this doesn't work if the item is not present!

[edit] hmmm... may it does. doesn't matter - equal_range() seems to be the ticket anyway.

Isn't equal_range() exactly what you want anyway? A quick test seems to show that it returns (x,x+1) if you're looking for x and find it or (end,end) if it's not present.

he he he. I like it in the kitchen! - Marc Clifton (on being flamed)

Awasu[^]: A free RSS reader with support for Code Project.

C^hris L^osinger5-Dec-02 19:23

5-Dec-02 19:23

nope. equal_range is just like lower_bound, but with a span, instead of a single position:

"the function determines the largest range of positions over which val can be inserted in the sequence and still preserve its ordering"

my vector has X elements. each element has an integer member variable that i'm ordering, and searching by. the less than operator for these elements only looks at the ordering and searching integer, nothing else. in the case i'm testing, these values range from 10 to 170.

if i do an equal_range "search" (or lower_bound) for "0", i get an iterator for the first element in the sequence, the one that contains "10".

i suppose i can test that iterator to see if the element is actually the one i'm searching for. but it seems like a huge hole in the STL, to not provide a binary search on a sorted collection.

oh well. guess i'll write my own.

-c

There's one easy way to prove the effectiveness of 'letting the market decide' when it comes to environmental protection. It's spelt 'S-U-V'.
--Holgate, from Plastic

markkuk7-Dec-02 2:15

markkuk

7-Dec-02 2:15

Then MSDN is misleading. ForwardIterator lower_bound(ForwardIterator beg, ForwardIterator end, const T& value, BinaryPredicate op) returns the position of the first element with value equal or greater than value. Just add a comparision and you have the search function you need.

C^hris L^osinger7-Dec-02 13:28

7-Dec-02 13:28

yeah, that's basically what i ended up doing; i combined the lower_bound code with the equality test into a new function, and named it appropriately: "vector_binary_search".

-c

There's one easy way to prove the effectiveness of 'letting the market decide' when it comes to environmental protection. It's spelt 'S-U-V'.
--Holgate, from Plastic

Nick Parker5-Dec-02 17:12

Nick Parker

5-Dec-02 17:12

Chris Losinger wrote:
please don't say "binary_search"

How about bin_search? Poke tongue | ;-P

This should return the position in the vector if that is any better?

int bin_search(vector<char>&A, char key)
{
	int left = 0;
	int right = A.size() - 1;
	while(left < right)
	{
		int mid = (left + right)/2;
		if(A[mid] == key) return mid;
		else if(A[mid] < key)
			left = mid + 1;
		else
			right = mid + 1;
	}
	return A.size();
}

Nick Parker

Not everything that can be counted counts, and not everything that counts can be counted. - Albert Einstein

C^hris L^osinger5-Dec-02 18:08

5-Dec-02 18:08

close. but it needs to take a predicate, because the elements in the vector are classes and i'm looking an element which has a member variable equal to a certain value.

right now, my code looks like:

class scaneql
{
public:
   scaneql( int lookfor) : i(lookfor) {}
   bool operator()(const scan & a) const
   {
     return a.i == i;
   }
   private:
     int i; 
   };
...
std::vector< scan>::const_iterator curScan = std::find_if(m_rows.begin(), m_rows.end(), scaneql((int)y));

There's one easy way to prove the effectiveness of 'letting the market decide' when it comes to environmental protection. It's spelt 'S-U-V'.
--Holgate, from Plastic

Tim Smith6-Dec-02 2:25

Tim Smith

6-Dec-02 2:25

Are you going to use this predicate in more than one spot? Do you need to search for member variables? If this is a one shot deal, just hack up bin_search and be done with it.

Tim Smith

I'm going to patent thought. I have yet to see any prior art.

Todd Smith12-Dec-02 11:45

Todd Smith

12-Dec-02 11:45

Is a binary search faster than using find_if? Is that the reason you are looking for something else?

Todd Smith

C^hris L^osinger12-Dec-02 12:46

12-Dec-02 12:46

yep. find_if just iterates over all items till it finds one that matches. this is fine, if your collection isn't sorted. but if it is sorted, a binary search is much much faster.

-c

There's one easy way to prove the effectiveness of 'letting the market decide' when it comes to environmental protection. It's spelt 'S-U-V'.
--Holgate, from Plastic