--- 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