Container Manipulations

All constructions described on this page are similar in that they take one or more container objects and produce a new object which behaves like a container too, but is not a container in the strict sense: it does not own any data. We will call them pseudo-container throughout this documentation.

The pseudo-containers can be divided in three categories according to their functionality:

An alias pseudo-container forwards all element access operation to the original data container(s). It can hide some elements away or let them appear in other order, in any case its elements are at the same times elements of the original container. This implies that assigning new values to the elements of a mutable alias container in fact changes the elements in the original container.
A lazy pseudo-container computes its elements on the fly, just at the moment they are accessed to. Thus the elements are temporary objects returned by container access methods (front(), back(), or operator[]) or reside in the iterator. Traversing a lazy container object multiple times object incurs repeating computations, which should be kept in mind when sticking it into a multi-pass algorithm template.
When you write an algorithm template, you can make it safe from multiple evaluation of lazy objects using the following construction:
```
typename prevent_lazy<Object>::type X=prevent_lazy<Object>::get(x); 
```
where x is an input parameter and Object its type. If Object is really lazy, it performs the evaluation exactly once and stores the results in an appropriate persistent object; if not, it does nothing.
A masquerade pseudo-container is just another view on the original object. Unlike the first two kinds, masquerade objects are never created: the original object address is reinterpreted instead; they even can't be created, since their constructors and destructors are purposely declared protected and left undefined.

To make the classification complete, let's call the standard containers, whose lifetime is the same as of their elements, persistent. This notion is traditionally used in the context of data base query languages, where it describes objects that can outlive the programs creating them. This is also applicable to objects in Polymake Template Library, since they can be stored in and retrieved from the data file via the client-server communication interface without any loss in structure or contents.

Reference or copy?

For instantiatable pseudo-containers (alias and lazy) it is important to know how to find the original data containers. Generally, the latter have a lifetime much longer than a pseudo-container object, which in the most cases exists during exactly one expression. Thus an internal reference to the original object would be sufficient.

On the other hand, the pseudo-containers are easy to combine and nest (it was, after all, the main design aim to made them interchangeable building blocks!) For example, one can first select a subset of elements and then apply an operation to it. In this case, the first operand of the outer pseudo-container will be the inner pseudo-container, which in its turn is a temporary object. It doesn't comprise a problem until the entire construction is copied outside the scope the components are confined to.

The best example is a return statement: if a function has to return the outer pseudo-container object, it may not contain a reference to the inner object, since it was created in the function's scope and will be destroyed after the return completion. Therefore the inner object must be copied into the outer object.

All pseudo-container objects in the Polymake Template Library can be configured for both scenarios. The template parameters describing the data sources are optional references: they can be specified as references as well as reference-free data types. Note that the convenience functions always create pseudo-containers with internal references, as a more efficient and more often occuring variant; the referenceless variant should be used only when it's really necessary, like in the return context explained above.

Either a reference to a container whose lifetime is not shorter than that of the pseudo-container object, or a "bare" container type for a temporary object. See also the detailed discussion.

This is a convenience function, which allows to embed a temporary object into an expression without writing down its exact type. The result is identical to a direct call to the constructor of the corresponding class with the same arguments.

Please note that this and similar convenience functions always create an object parameterized with references to the input data (containers.) Sometimes, especially in a function return statement, you will need a reference-less variant; then you have to use the constructor.

Either a functor class satisfying the extended requirements for unary operations, or a "naked" template of such a class wrapped into BuildUnary or BuildUnaryIt.

Either a functor class satisfying the extended requirements for binary operations, or a "naked" template of such a class wrapped into BuildBinary or BuildBinaryIt.

Element selection

This class is defined in <IndexedSubset.h> It is automatically included together with all top-level data structures.

This class is defined in <SelectedSubset.h>

The template parameter inherits the const attribute from the corresponding function argument. A pseudo-container with a const reference to the source data is in its turn immutable.

The constructions in this section select a subset from a data container (real or pseudo) according to some choice criterion. All they belong to the alias type. Assigning a new value to an element effectively changes the contents in the original data container. Pseudo-containers with first argument having const attribute are immutable.

template <typename DataContainerRef, typename IndexContainerRef> class IndexedSubset;

template <typename DataContainerRef, typename IndexContainerRef> class IndexedSlice;

IndexedSubset<DataContainer&, const IndexContainer&> select (DataContainer&, const IndexContainer&);

Select elements based on their indices (subsequent numbers in the original container; the first element has, as usual, the index 0.) IndexContainer should be a container with integer non-negative elements.

If it is a GenericSet or a complement thereof, the selected elements keep their order in the data container, and thus preserve the GenericSet property of the DataContainer, if any. On the other hand, the index sequence may be not increasing, not monotonic, or even contain repeating indices, which would let the corresponding data element appear multiple times.

Despite of the index terminology, the data container need not be of random-access type, although if the latter holds, the jumps between the selected elements are obviously made more efficiently. If the index sequence is not monotonically increasing, the data container must be at least reversible.

The difference between IndexedSubset and IndexedSlice is in the handling of sparse containers: the elements in the former preserve their indices from the original data container, while in the latter they are renumbered to the index positions in IndexContainer.

template <typename DataContainerRef, typename Predicate> class SelectedSubset;

SelectedSubset<DataContainer&, Predicate> attach_selector (DataContainer&, Predicate);

Select elements based on the output of a functor Predicate. The result type of the predicate must be bool or convertible to it. Only elements evaluated to true show up in the pseudo-container, the rest is hidden. The selected elements preserve their order from the the data container.

Note that size() method runs thru entire container, while empty() until the first true hit.

template <typename DataContainerRef, typename Predicate> class TruncatedContainer;

TruncatedContainer<DataContainer&, Predicate> attach_truncator (const DataContainer&, Predicate);

Similar to SelectedSubset described above, but the predicate evaluation stops at the first false result. With other words, the visible element subrange starts always at the beginning of the data container and ends before the first element mapped to false.

template <typename DataContainerRef, typename Container2Ref, typename Predicate>

class SelectedContainerPairSubset;

SelectedContainerPairSubset<DataContainer&, const Container2& Predicate>

attach_selector (DataContainer&, const Container2&, Predicate);

Similar to SelectedSubset described above, but with a binary functor as a predicate. The second container argument serves solely as the predicate second operand source, the visible elements are those from DataContainer. The elements of both containers are taken pairwise for the evaluation, therefore their sizes must be equal.

Note that size() method runs thru entire container, while empty() until the first true hit.

SelectedContainerPairSubset<DataContainer&, const BooleanContainer&, BuildBinaryIt<second_deref_accessor> >

attach_mask (DataContainer&, const BooleanContainer&);

A special case of binary selection where no predicate is needed. The elements of the second container (which should be bool or convertible to it) serve as visibility mask bits for the corresponding elements of the data container. Both containers must be of equal size.

The random subset selection would fit in this category too.

Element transformation

This class is defined in <TransformedContainer.h> It is automatically included together with all top-level data structures.

The exact return type is

TransformedContainerPair<const Container&, const unlimited_constant_container<Scalar>&,
                         BuildBinary<operations::add> >

The exact return type is

TransformedContainerPair<const Container&, const unlimited_constant_container<Scalar>&,
                         BuildBinary<operations::mul> >

The constructions in this section perform an operation encoded as a unary or binary functor on the elements of the given input data container(s) and show the results as apparent elements. They are lazy containers.

template <typename ContainerRef, typename Operation> class TransformedContainer;

TransformedContainer<const Container&, Operation> attach_operation (const Container&, const Operation&);

Apply a unary operation to each element of the input container.

TransformedContainer<Container&, operations::member<Class&,Member> >

attach_member_accessor (Container&, Member Class::*);

Special case of element transformation: provided the elements of Container are of type Class or derived thereof, this pseudo-container consists of corresponding member fields pointed to by the given member pointer. This is the only tranforming construction that can be mutable.

TransformedContainer<const Container&, conv<typename Container::value_type, Result> >

attach_converter<Result> (const Container&);

Convert the container elements to the given type. The conversion must be either a built-in one (e.g. int -> double), user-defined (constructor without explicit attribute, conversion operator), or encoded as a specialization of conv class.

Note the explicit specification of the Result type parameter, as it can't be deduced from the function parameters.

template <typename Container1Ref, typename Container2Ref, typename Operation>

class TransformedContainerPair;

TransformedContainerPair<const Container1&, const Container2&, Operation>

attach_operation (const Container1&, const Container2&, const Operation&);

Apply a binary operation to the elements of two input containers.

If both input containers are dense, they must have equal size, and this will be also the size of the resulting pseudo-container. If at least one of the inputs is sparse, the resulting size depends on the index overlapping in the input sequences, and whether the operation gains non-trivial results with partially defined operands.

LazyContainer translate (const Container&, const Scalar&);

LazyContainer scale (const Container&, const Scalar&);

Add or multiply each element of a container with a given constant.

template <typename Container1Ref, typename Container2Ref, typename Operation>

class ContainerProduct;

ContainerProduct<const Container1&, const Container2&, Operation>

product (const Container1&, const Container2&, const Operation&);

Build a cartesian product of two containers and apply a binary operation to each pair of elements. The second element in the pair changes first.

If both containers are dense, the result has exactly size₁*size₂ elements. If at least one input container is sparse, the result will also have gaps, depending on whether the operation gains non-trivial results with partially defined operands.

Element rearrangement

This class is defined in <CascadedContainer.h> It is automatically included together with all matrix classes.

This class is defined in <ContainerChain.h> It is automatically included together with all matrix and vector classes.

The template parameter inherits the const attribute from the corresponding function argument. A pseudo-container with at least one const reference to the source data is in its turn immutable.

template <typename Container> class construct_reversed;

construct_reversed<Container>& reversed (Container&);

Reverse the container. In fact, no data elements are moved; this masquerade class simply swaps the definition of begin() and end() with rbegin() and rend() and so on. Clearly, the input container must be reversible.

template <typename ContainerRef, int depth=object_traits<typename deref<ContainerRef>::type>::nesting_level>

class CascadedContainer;

CascadedContainer<Container&> cascade (Container&);

Make a nested container (that is, whose elements are in turn containers) look like a plain container of elements from the deepest level. The boundaries between the intermediate containers become invisible.

How deep the "plaining" goes is controlled by the parameter depth. By default this construction descends until a non-container data type is found (as recognized by object_traits.)

Note that size() need to traverse all intermediate layers in order to count all elements.

CascadedContainer<Container&, depth> cascade (Container&, int2type<depth>*);

Specifies a descending limit different from the default. depth==1 corresponds to the input container itself, and is therefore pointless.

depth must be a compile-time constant, therefore it can't be passed as an usual function argument. This function could have a more elegant spelling cascade<depth>(Container), but this is currently not applicable due to a obscure compiler bug. Thus we must put up with int2type wrapper.

template <typename Container1Ref, typename Container2Ref> class ContainerChain;

ContainerChain<Container1&, Container2&> concatenate (Container1&, Container2&);

Glues two container together. The boundary between them become invisible. This construction can be arbitrarily deep nested, making the chain longer and longer.

If you build an inhomogeneous chain, that is, the element types of the component containers are different, the element type of the chain is determined according to the same rules as for the ContainerUnion. You might need to wrap one component in a converting TransformedContainer, if you find this more suitable than handling with type_union objects.

The random permutation would fit in this category too.