From: Pavol Droba (droba_at_[hidden])
Date: 2003-10-21 15:22:23
Following the complaints about some missing information about the string_algo
library, pointed out by Beman, I'd like to explain here in more detail the
concepts used in the library.
Unlike the STL algorithm library, which is iterator-oriented, string_algo library
has adopted a Container as a basic concept used for arguments.
However, STL specification of a container if too strong. On many places, a simplified
version of the Container concept is sufficient.
We use the name InputContainer for it.
typedef ... value_type;
typedef ... size_type;
typedef ... iterator;
typedef ... const_iterator;
typedef ... difference_type;
const_iterator begin() const;
const_iterator end() const;
These properties are exactly the properties the STD Container concept,
except of construction/destuction method, and swap.
This concept allows to access the values contained in the container, without altering
the state of the container itself. It means, the it is not possible to change,
what elemnts are containd by this container.
It is sufficient for those arguments in algorithms with are not altered (i.e. immutable arguments)
container_traits, one of the core facilities defined in theis library, wraps this concept,
and allows to access some of legacy C structure (C-arrays and string) using this interface.
iterator_range also implements this concept for a pair of iterators.
In the string_algo library, a container satifying this concept can be used as any non-result
argument (i.e. the argument, whose type is not used as a result).
All trasformation algorithms in the library comes in three variants. Two "copy" variants
and one inplace, mutating the input.
1. The inplace variant uses the input as a result. In general, the algorithms require,
that this type satisfies the SequenceConcept (Std 23.2). Operations like insert, erase
2. Copy variant, that returns the copy of the modyfied input. This variant also uses the same type
as input for the result. For all algorithms, SeqeuenceConcept is sufficient, however for some
of them, standard ContainerConcept (Std 23.1) is sufficient. In addition to InputContainer,
there is a need for a construction, because the new copy of the container is required.
It has been proposed during this review by Pavel Vozenilek to use sequence trait (another facility for this
library) to optimize behaviour of this variant. Now it seems possible, that this would
also allow, to ease the requierements on the input type and use the additional feature, only when
they will be available.
3. Copy variant, that copies to output to an output iterator. This variant has the least requirements.
Because, the input type is not used for the result, the input need to only satisfy InputContainer
requirements. This variant has the same level of generality as algorithms in STL.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk