here's something about sitting down to write a Brew application in C that makes me go back to basics: the very basics, like writing my own linked list each time instead of leveraging one of the hundreds of implementations I have laying around, or not re-using any of the data structures I've written for various projects. This is especially maddening when targeting the large number of legacy Brew handsets, because without things like IVectorModel
, you end up worrying about your data collections instead of the algorithm you're trying to implement.
In this article and the next, I'll give you two popular collections, the vector and the dictionary, implemented as Brew interfaces that you can use in your applications. Both require nothing more than rudimentary Brew standard library calls, making them suitable for legacy handsets that are the vast majority of handsets in the hands of consumers today. Both support not just item insertion and access, but enumeration and mapping as well, giving you an additional layer of abstraction when working with your data. This month, I'll focus on the vector, and next time I add the dictionary to the mix. You can download the implementation of these collections here.
Introducing the Vector
A vector, as I'm sure you know, is a data structure containing a group of elements that you access by an index. Unlike a traditional array in C, a vector implementation usually has two key features that make it more convenient to use:
- They provide dynamic storage, resizing as needed when additional elements are inserted.
- They provide bounds checking to prevent out-of-bounds access errors.
In addition, many vector implementations provide additional facilities, including:
- The ability to insert an element at an arbitrary location, shifting elements down to accommodate the new element.
- The ability to delete an element at an arbitrary location, shifting elements back to close the gap.
- An enumerator to access each element of the vector in turn.
The vector presented here has all of these features, plus one idea borrowed from higher-level languages like Python and Haskell: list comprehensions. This vector implementation includes a ForEach
method that lets you invoke a function for each element of the vector, as well as a Comprehend
method that applies a test function to each element in turn, invoking a second function only on those items for which the test function returns true
. Finally, the implementation lets you specify an item destructor for the vector's contents, so that the vector is suitable for storing both pointers to data structures and interfaces.
This vector implementation stores its elements in an array allocated at runtime that periodically grows as additional items are insertedspecifically, you can specify an initial capacity and an increment to the capacity; once the vector is full it automatically increments its capacity by the size you specify, preserving its initial contents and reporting an error if the reallocation fails. It does not, however, shrink when items are removed; in my experience, most vectors go through a life cycle in which many items are initially added, then the vector is used for item access with little mutation to its contents for a prolonged period, and then the vector is released. As with many vector implementations, once an item is inserted in the vector, the vector owns the item; deleting or replacing an item results in the vector calling the destructor you supply to destroy any element at the location you indicate.
Obviously, this implementation poses trade-offs. If raw speed for item access is your primary goal, you may not want the overhead of function calls for item access or bounds checking. Similarly, its behavior is somewhat non-deterministic when adding or inserting elements, as you do not directly control its reallocation behavior. Finally, if memory is at a premium, the fact that the vector doesn’t shrink may be an issue. However, for many applications, a simple implementation such as this suffices.