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 lazy containers".
Many
operators defined for PTL container classes, such as vector and matrix arithmetic, set-theoretical operations, etc., do not 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
lazy evaluation, sometimes also referred to as
expression templates. 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 also:
- Reference Counting
- 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.
The vector class family implement vectors in the usual algebraic notion. It contains three
persistent vector types with different data storage organization. These implementations result in
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 (
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.
- FixedVector is a built-in array of a fixed dimension decorated with the common vector interface.
The matrix class family implement matrices in the usual algebraic notion. It contains three
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 (
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
std::list. Can be parameterized with any persistent vector type".
- The AVL::tree class implements balanced binary search trees.
These are borrowed from
GMP and wrapped.
1.5.6