| | |
On a higher level the notion of sets remains interesting to developers. Various classes of containers model topological spaces, and thus sets, with different requirements and applications [57]. Since each memory location is distinct, low level containers may include several items with the same value without it being considered as a duplicate, which contradict the notion of a set. If it is required to obtain a set of distinct values, an addition relation (Definition 4) for comparison of the stored values is required to realize such a data structure, since without it, it is impossible to judge two items for equality, thus indicating duplicates. Set containers are available for both, run time as well as compile time, as is illustrated using the C++ std::set, mpl::set, and fusion::set representatives
The run time version taken directly from C++’s STL [38] requires not only a data type, but also the specification of a comparison relation which is used in this implementation to impose an ordering of the inserted elements and uses this mechanism to ensure uniqueness. It also allows to specialize the memory layout via an allocator. The STL further provides several set operations in the form of algorithms such as includes, set_union, set_intersection and set_difference. In contrast to the run time implementation, the featured compile time facility provided by the MPL [58] needs neither an additional relation, since types are inherently required to be distinguishable, nor an allocator, since no memory is required. Finally, a hybrid approach combining a compile time set with run time values is also available in the form of fusion::set available from the Boost Fusion [103] library.
To enable a consistent compile time and run time set interface, the GSSE offers 0D cell complex data types which can be used in multiple application areas, e.g., sparse and dense polynomial containers [104 ] as given in the next Chapter 6.2. The following code snippet demonstrates an application of the internal data layout of a set and implements a data structure equivalent to a std::vector and can be specified as a dense memory arrangement of any data type element, e.g., a double. The set properties are then handled by the C++ standard library, where a free function insert() controls the set property.
Orthogonal properties related to a set definition, in contrast to C++’s standard library, can be clearly observed due to the separation of topological structure, as displayed by tag_dimension, and data storage tag_storage. The availability of such basic generic data structures modelling the concept of a set on a higher semantic level allows to considerably simplify the development of more complex algorithms which require to act on sets.
| | |