Re: [boost] string_algo Formal Review

From: Beman Dawes (bdawes_at_[hidden])
Date: 2003-10-21 20:08:05

At 04:22 PM 10/21/2003, Pavol Droba wrote:

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

OK, good. This is starting to fill in the missing pieces. Presumably you 
will change the name of template parameters to InputContainerConcept where 
applicable?

Other comments:

Specifying the types and operations as member signatures is precise, but is 
really overspecification. The Standard Library approach of specifying a 
requirements table is precise, yet leaves the implementor a bit of wiggle 
room to meet the specification. I don't think it matters at this stage, but 
others may have stronger opinions.

The Standard Library clause 23.1 has five or so requirements tables 
(Container, Reversible Container, Sequence, etc). Where the docs talk about 
"the Std Container concept", it would be clearer if they said "the Standard 
Library Container requirements table 65 in section 23.1" or something 
similar. That's a bit pedantic, but more precise.

 >This concept allows to access the values contained in the container,
 >without altering the state of the container itself. It means, [that] it
 >is not possible to change, what elements are contained by this container.
 >It is sufficient for those arguments in algorithms with are not altered
 >(i.e. immutable arguments)

Presumably you will then have a similar concepts for algorithms needed 
erase or other members? That will resolve the current confusion caused by 
using the same name (ContainerT) for template parameters with different 
requirements.

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

OK, as soon as it is known exactly what algorithms require this concept 
(rather than EraseableContainer (or whatever), then it becomes possible to 
understand which algorithms would work with C style arrays or other 
almost-containers, and as many other gradations of functionality as there 
are requirement concepts.

--Beman