|
|
Rather than spending any more time discussing abstract design philosophy, let's look at a concrete example: the implementation of a set class. Rather than specifying our own set operations, we will simply adopt the existing functional specification of Set(C++). Whereas the current implementation of Set(C++) uses a relatively complicated data structure, our implementation, which we call Array_set, uses a Block(C++) as the underlying Array_set representation and Array_alg(C++) to implement the Array_set operations. After choosing a representation and formalizing the representation invariant, we will look at several Array_set operations whose implementations are interesting from an Array Algorithms perspective.
As you follow the development, please have the relevant manpages handy. Be forewarned that, to help elucidate key points about Array Algorithms, we will be making some intentional false starts; in general, you should follow each discussion to its conclusion to discover the correct (or most efficient) implementation. A complete Array_set implementation can be found at the end of this tutorial.