C++ binary search

You might take a look at std::lower_bound() (and, similarly, std::upper_bound()).

Also, depending on what you're doing, it may be that another container (such as std::set) might be more appropriate.

1: Use std::lower_bound and a couple of checks instead.

2: middle = low + std::distance(low, high) / 2;

Interesting - I did not know about lower_bound and upper_bound. Those seem very promising. I think i will still finish the algorithm just for my own education.

Do you know if the std::distance iterates through on its own to find the distance?
That would negate the benefits of using it..

Thanks for the help

Quote:

Original post by trixs Do you know if the std::distance iterates through on its own to find the distance? That would negate the benefits of using it..

Perhaps you should read the documentation for the function. It includes that information.

Not to be rude as you where but..

I did read the documentation in:

Microsoft Visual Studio 2008

Guess what?

It says what it does but does not say how it goes about it. I also did a Google search with: std::distance efficiency and a few others.. did not find much.

Please just don't assume someone doesn't try to find the information.

Google search for "std::distance".

2nd result.

Quote:

Original post by trixs Not to be rude as you where but.. I did read the documentation in: Microsoft Visual Studio 2008 Guess what? It says what it does but does not say how it goes about it. I also did a Google search with: std::distance efficiency and a few others.. did not find much. Please just don't assume someone doesn't try to find the information.

From the documentation:

Quote:

The distance function has constant complexity when InputIterator satisfies the requirements for a random-access iterator; otherwise, it has linear complexity and so is potentially expensive.

I dont know where you see that then because heres what mine say:

"This function returns the distance between two iterators by determining how many times the first iterator would need to be incremented until it was equal to the last iterator."


Regardless it is pointless as it needs to be cast to ::difference_type which means you cant make it equal to an iterator later on. Also lower_bound wont work as at as it does not look through an object for the specific numbers you are comparing.

So I guess the answers to my questions are:

#1 binary_search - pointless

#2 impossible to do math with iterators...

So how does one search through a vector of object efficiently? Would hate to use for()...

Quote:

Also lower_bound wont work as at as it does not look through an object for the specific numbers you are comparing.

You can perform a search using lower_bound(), and then if the returned iterator is not equal to end(), you can compare the value it refers to with the query value to see if the exact value was found.

Quote:

#1 binary_search - pointless

Well, it's not pointless; it just doesn't do what you're wanting.

Quote:

#2 impossible to do math with iterators...

The 'math' that you can do with iterators is very limited, and that is at it should be.

Quote:

So how does one search through a vector of object efficiently? Would hate to use for()...

If you're only option is a linear search, you can us find() or find_if() rather than writing out a loop.

If on the other hand the array is sorted, you can use lower_bound() as described previously.

So what are these objects exactly? As I mentioned earlier, there might be a better way to go about storing and accessing them...

Quote:

I dont know where you see that then because heres what mine say: "This function returns the distance between two iterators by determining how many times the first iterator would need to be incremented until it was equal to the last iterator."

The function is written in such a way that it has different implementations for different iterator types (random-access, bidirectional, ...). For random-access iterators, it's complexity is constant.

Quote:

#2 impossible to do math with iterators...

vectors have random-access iterators. As such, you can advance them by a number. For example, you can do this:

std::vector<char> vec(5, '*');std::vector<char>::iterator it = vec.begin();    // it points to first elementit += 3;    // Now it points to the fourth element

therefor writing:

middle = low + std::distance(low, high) / 2;

will give you just what you need. It's true that the return value of distance() is difference_type, but you don't need to cast it, it will work just as written (not sure why, though).

By the way, the following is the implementation for std::binary_search in VS 2005:

Quote:

Original post by trixs Regardless it is pointless as it needs to be cast to ::difference_type which means you cant make it equal to an iterator later on. Also lower_bound wont work as at as it does not look through an object for the specific numbers you are comparing. So I guess the answers to my questions are: #1 binary_search - pointless #2 impossible to do math with iterators... So how does one search through a vector of object efficiently? Would hate to use for()...

Just to completely hammer the point home - just because you can't see how to do it doesn't mean it doesn't work, is pointless or is impossible. In fact common implementations of binary_search work out whether an element is in a given range by calling lower_bound (which you claim doesn't work) which in turn commonly uses distance and iterator math (which you reject as impossible).

Σnigma

jyk,

The vectors contain objects that are holding packets that have been received and are awaiting to be processed and those that are waiting to be sent out. So the data would look something like this:

class packet {
public:
int number;
int account;
int x;
int y;
int z;
int a;
}

std::lower_bound is useful for certain aspects when I am searching through a simply vector or whatever that is based on: vector. In this case I am searching through the vector for a specific number in the packet.

Gage64,

I couldn't get it to compile as you have it written. Had to change it around abit and make it equal difference_type - I wonder if this is a compiler difference.


Dalleboy,

Good example. IN that case it would be easy. It makes me want to completely redo the data and use multiple containers for the data. put number in one, x in another ect.. Or just use a damn array lol

Enigma,

Thanks for humbling me. I know the various templates are not pointless in there own right. They where just pointless for what I need :)

Quote:

Original post by trixs jyk, The vectors contain objects that are holding packets that have been received and are awaiting to be processed and those that are waiting to be sent out. So the data would look something like this: class packet { public: int number; int account; int x; int y; int z; int a; } std::lower_bound is useful for certain aspects when I am searching through a simply vector or whatever that is based on: vector. In this case I am searching through the vector for a specific number in the packet.

Quote:

Dalleboy, Good example. IN that case it would be easy. It makes me want to completely redo the data and use multiple containers for the data. put number in one, x in another ect.. Or just use a damn array lol

By using a custom comparator, you can store your packet objects in the container of your choice and keep them sorted however you want (for example, according to the value of number).

An ordered container would probably be a better option, but, for reference, an example of how you could so this with lower_bound:

Σnigma

Well looks like std::equal_range will do what I want.

Enigma,

I did not know about boost - That seems to be an extremely useful library!

EDIT: Heres what I eventually came up with that searches for the value needed:

int position; //   Player_Movement* move;   std::vector<Player_Movement*>::size_type sz = Net->Player_Movement_Receive.size();   int value = a->accountnum;   int low = 0, high = sz - 1, middle = 0;   while (low  <= high)   {      middle = (low + high) / 2;      move = Net->Player_Movement_Receive[middle];      if ( value == move->accountnumber) {         position = middle;         low = high + 1;      }      else if ( value < move->accountnumber)         high = middle - 1;      else         low = middle + 1;   } 

[Edited by - trixs on January 17, 2008 5:46:02 PM]

Quote:

Original post by Gage64 vectors have random-access iterators. As such, you can advance them by a number. For example, you can do this: std::vector<char> vec(5, '*');std::vector<char>::iterator it = vec.begin(); // it points to first elementit += 3; // Now it points to the fourth element therefor writing: middle = low + std::distance(low, high) / 2; will give you just what you need. It's true that the return value of distance() is difference_type, but you don't need to cast it, it will work just as written (not sure why, though).

difference_type is a typedef for some kind of integral type. Anyway, why shouldn't you expect adding a type that "represents the distance between two iterators" to an iterator to give you another iterator? :)

Anyway, you can make this kind of arithmetic work with other sorts of iterators:

middle = std::advance(low, std::distance(low, high) / 2);

But of course, this will mask performance issues with doing this sort of thing on a non-random-access iterator. But anyway, it doesn't make sense to binary search a linked list, since it will take as long, on average (at least in the big-O sense - probably longer in practice), as linear searching (because of what's involved in finding midpoints).

incidentally, since binary_search didn't do what you want, did you keep looking? I think the function you are looking for is called find_if. It finds with a predicate and returns an iterator.

There's std::lower_bound, std::upper_bound, std::equal_range. If you know its in the range you've found, you can use std::find_if with a predicate to search that range of iterators.