Polymake Template Library (PTL) 4.13
|
PTL is based on STL and makes exhaustive use of the three main concepts of the latter: containers, iterators, and functors. There is a subtle difference, however, in the implementation of algorithms: in STL, they are designed to work with iterators, while in PTL the most of them accept containers as arguments. PTL containers are more than pure data structures, they bear some additional semantics, in that they belong to one of the generic families. See http://www.cplusplus.com/reference/stl/ for a description of STL's container concept.
Besides real containers, which own their data as prescribed by the standard, PTL makes heavy use of Container Manipulations. The latter implement though the standard container interface, but do not possess any data at all; instead, they refer to other container objects supplying the data items. There are three kinds of pseudo-containers in PTL: alias_sec alias, masquerade_sec masquerade, and lazycontainers". @subsection lazy_sec Lazy evaluation Many operators defined for PTL container classes, such as vector and matrix arithmetic, set-theoretical %operations, etc., don't perform the computations immediately, but rather create a temporary object which "remembers" the operands and the operation and evaluates it later, on demand. This is a well-known technique called <em>lazy evaluation</em>, sometimes also referred to as <em>expression templates</em>. It helps to spare unnecessary computations and copying of objects. The lazy objects fit well in the container concept of PTL, as they always belong to the same generic family and implement the same container interface as the result of the real operation would do. @see - @ref refcounting "Reference Counting" - @ref generic "Generic and Persistent Types" @section container_sec Container Classes @subsection set_sec Set Types - Bitset is a container class for dense sets of integers. Data representation is a bit string as implemented in the GNU Multiprecision Library (mpz_t). - Set is a container class for sparse sets of ordered elements. Data representation as a modified kind of AVL tree. @subsection vector_sec Vector Types The vector class family implement vectors in the usual algebraic notion. It contains three @ref generic "persistent" vector types with different data storage organization. These implementations result in @ref vector_performance "performance differences" for various functions on vectors. - Vector holds the elements in a contiguous array. - SparseVector is an associative container with element indices (coordinates) as keys; elements equal to the default value (@c ElementType(), which is 0 for most numerical types) are not stored, but implicitly encoded by the gaps in the key set. It is based on an AVL tree. @subsection matrix_sec Matrix Types The matrix class family implement matrices in the usual algebraic notion. It contains three @ref generic "persistent" matrix types with different data storage organization. - Matrix holds the elements in a contiguous array. - SparseMatrix is a two-dimensional associative array with row and column indices as keys; elements equal to the default value (@c ElementType(), which is 0 for most numerical types) are not stored, but implicitly encoded by the gaps in the key set. Each row and column is organized as an AVL::tree. - ListMatrix is a list of row vectors. Based on @c std::list. Can be parameterized with any \ref generic "persistent" \ref vector_sec "vector type". @subsection other_sec Other Container Types - Array class with @ref refcounting "smart pointers". - Map - an associative container class based on an AVL tree structure. - The AVL::tree class implements balanced binary search trees. @section generic_sec Generic Class Families - GenericVector - an abstract vector class - GenericMatrix - an abstract matrix class - GenericSet - an abstract set class @section gmp_sec Number Types These are borrowed from @ref GMP "GMP" and wrapped.