[boost] Re: string_algo Formal Review

From: David Abrahams (dave_at_[hidden])
Date: 2003-10-21 16:48:27

Pavol Droba <droba_at_[hidden]> writes:

> Hi,
>
> 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.
>
> InputContainerConcepts
> ----------------------
>
> 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.
>
> Definition:
>
> InputContainerConcept:
> {
>
> /////// types
>
> 	 typedef ... value_type;
> 	 typedef ... size_type;
> 	 typedef ... iterator;
> 	 typedef ... const_iterator;
> 	 typedef ... difference_type;
>
> ////// operations
>
> 	 iterator begin();
> 	 const_iterator begin() const;
> 	 iterator end();
> 	 const_iterator end() const;
> 	 
>  	 size_type size();
> 	 bool empty();
> };
>
> These properties are exactly the properties the STD Container
> concept, except of construction/destuction method, and swap.

I wonder if swap ought to be included, despite the fact that you
don't need it.

> 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.

Whoa.  You'll never get a C array to have a begin() member function.
This statement needs to be tightened up.  If your algorithms can
actually operate on C arrays directly, your need to change your
description of InputContainerConcept so that it's phrased in terms of
container traits.  Regardless, you should also be as specific as the
standard is about the requirements on nested types and return types
of begin/end, etc.

> 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).

Really, "any?"  You have no char or integral non-result arguments?  I
see that you have output iterator non-result arguments.

> Algorithm variants
> ------------------
>
> 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 are required.
>
> 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.

You need to be specific about which algorithms need Sequence and
which need Container.

> 	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.
>
>
> Pavol
>
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com