Re: [Boost-Users] Boost Array Question

From: Duane Murphy (duanemurphy_at_[hidden])
Date: 2002-01-16 11:48:11

--- At Wed, 16 Jan 2002 07:55:52 -0500, Jeremy Siek wrote:

>On Tue, 15 Jan 2002, Duane Murphy wrote:
>
>> --- At Tue, 15 Jan 2002 21:20:59 -0500, Jeremy Siek wrote:
>>
>> >Why don't you create your associative array-like interface via
>> >free-functions in terms of boost::array itself? Member functions are lame
>> >anyways ;)
>>
>> I'm assuming this was tongue-in-cheek. I can already do everything as
>
>Nope, I was serious. Though since you have not yet posted the interface of
>this associative array there's a good chance I have no idea what you are
>trying to do.

I have recently had the need to use static lookup tables. These tables
typically took the form of:

void (*function_ptr)();
struct lookup_table_t
{
    char key;
    function_ptr function;
};

static const lookup_table_t lookup_table[] =
{
    { 'a', function_a },
    { 'b', function_b },
    { 'c', function_c },
    { 'd', function_d }
};

I would then use equal_range() to search for the function pointer based
on some character input. There are other variations as well where the key
is some other type and there is often additional data in the table; a
function pointer is just a typical example.

Part of what made this messy was that I was taking advantage of the
boost::transform_iterator ( I have trouble getting projection_iterator to
work with const pointers ) to search for the entry:

typedef boost::transform_iterator_generator
    < select_key, const lookup_table_t * >::type iterator;

std::pair< const lookup_table_t*, const lookup_table_t* >
range = equal_range( 
            iterator( boost::begin( lookup_table ) ),
            iterator( boost::end( lookup_table ) ),
            c );

Where select_key is a function object that returns the key field of a
lookup_table_t.

This all felt like a map. In fact all of this could easily be done with a
map but that sacrifices the static nature of the problem and makes it
dynamic, using more memory, time, etc.

After several iterations, I took your suggestion and made free functions
based on boost/array_traits which I have been using (boost::begin() and
boost::end());

I added one constraint (that I would like to remove if I could) that the
table being used has one field specifically named "key". I now have
interfaces for:

template <typename Key, typename T, std::size_t sz>
inline typename boost::array_traits<T const [sz]>::iterator
lower_bound(T const (&a)[sz], Key key );

template <typename Key, typename T, std::size_t sz>
inline typename boost::array_traits<T const [sz]>::iterator
upper_bound(T const (&a)[sz], Key key );

template <typename Key, typename T, std::size_t sz>
inline std::pair< 
        typename boost::array_traits<T const [sz]>::iterator,
        typename boost::array_traits<T const [sz]>::iterator >
equal_range(T const (&a)[sz], Key key );

template <typename T, std::size_t sz >
inline void sort( T(&a)[sz] );

template <typename T, std::size_t sz >
inline void key_sort( T(&a)[sz] );

There are four versions of each of the binary search functions;
variations on const/non-const and with/without an external Compare
function. (These are the const interfaces without the Compare function.)
The Compare function is expected to compare key fields rather than the
structures themselves.

Now the example given above can be simply written as:

std::pair< const lookup_table_t*, const lookup_table_t* >
range = equal_range( lookup_table, c );

The sort() function is just a simple call through to std::sort(). The
key_sort() function assumes that the items in the table have a field
named "key" that can be used to sort the table.

After adding the sort/key_sort functions, I wondered if I shouldn't have
done the same with the other functions. That is separate traditional
array searching from key-based array searching. My thinking right now is
that the syntactical savings of traditional array searching are minimal
with this model and can still be handled "the usual way". I suppose the
same is true of sort. Sort just didn't provide that extra input Key
parameter to show that it was different.

>> free functions, but the code is getting messy and reusability is
>> suffering. Besides how do I do an operator[] as a free function. :-)
>
>Why do you need an operator[]? boost::array already has one.

My original thought was that operator[] in a mapped_array would be
associative instead of indexed. (ie lookup based on a key type rather
than an index). It turns out that operator[] has difficult side affects
that make it pretty unsafe. Basically you cant easily tell that the
result is out of range except by throwing an exception.

I prefer the use of equal_range() that has safe semantics for determining
if the item was located.

This was an interesting exercise. I learned more about templates and the
use of arrays in templates. Very educational, and I will likely be using
this in my project.

 ...Duane