Marcel Müller
10/26/2008 3:05:00 PM
Thomas J. Gritzan wrote:
> Marcel Müller wrote:
>> Is the following code valid?
>
> g++ warns about antique headers, so I replaced the includes with this:
For testing purpose I didn't care about that.
>> // compare *l to *r
>> template <class T>
>> int comparer(const T* l, const T* r)
>> { if (*l < *r)
>> return -1;
>> return *l == *r;
>> }
>
> Prefer references oder pointers. They are safer to use:
>
> template <typename T>
> int comparer(const T& l, const T& r);
I think that makes mo much difference. const T* is pretty much the same
that const T&, except for the syntax.
> Also, your comparer might not return the right results. It returns 1 on
> equality and 0 and greater-than.
Your are right. Again I only did it for testing. It is not called in the
example anyway.
> For a binary search algorithm, it might be faster and easier just to use
> a less-than comparator. Almost all of the standard library works just
> with std::less.
>
>> // Returns true on match, pos receives the lower bound.
>
> If the return values can be true and false, the type should be a bool.
Don't know where the int came from. I think from a test with another
very old compiler that does not know about bool. In the original coding
it is bool.
>> template <class T>
>> int binary_search(const T* data, size_t len, int (*fcmp)(const T* elem,
>> const T* key), const T* key, size_t& pos)
>
> Consider using a iterator pair instead of a begin pointer and a length.
The real coding passes an array class with T** and size_t internally.
(All T are reference types here.) But that requires a bunch of
additional types and do not belong to the question.
> key should be passed by value or by const reference.
It is a wrapper to a C library, so I have no choice.
> There might be no easy way to get the actual position of the lower
> bound, if this function calls itself recursivly.
The common implementation of binary search in a random access container
does not use recursion.
>> int foo(int key)
>> { const int arr[] = {1,2,3,4};
>> size_t pos;
>> return binary_search(&*arr, sizeof arr/sizeof *arr, &comparer<int>,
>> &key, pos)
>> ^
>> ? pos : ~pos;
>> }
>>
>> One of my compilers says
>> test2.cpp(24:68) : error EDC3090: Syntax error - expected "(" and
>> found ">".
>> at the marked position.
>
> Both Comeau and g++ (with -Wall -ansi -pedantic) compiles it fine.
>
> How old is your compiler?
Too old on the face of it. The executables are from '97.
I use a work around for now:
template <class T>
struct interface_comparer
{ static int cmp(const T* elem, const T* key);
{ return elem->compareTo(*key);
}
};
Marcel