[boost] standard implementations of container-like interfaces (was: containers)

From: Reece Dunn (msclrhd_at_[hidden])
Date: 2005-01-19 04:40:44

Jason Hise wrote:
> Pavel Vozenilek wrote:
> 
>> "Jason Hise" wrote:
>>> I was thinking about the simpler standard containers... specifically 
>>> vector, deque, and list, and wondering... would there be any value in 
>>> making a generic linear_container class which uses policies to define 
>>> the allocation and iteration methods?  Specifically, I imagine 
>>> something like this:
>>>
>>> typedef linear_container < contiguous_iterator, alloc_using_new > 
>>> vector;
>>> typedef linear_container < double_linked_iterator, alloc_using_new > 
>>> list;
>>> // etc...
>>>
>>> The iterator itself could probably be broken down into smaller 
>>> traits, but the idea is that this would make it much easier to add 
>>> new types of containers or mix and match existing functionality.  
>>> Through the linear_container it would be easy to ensure that all 
>>> types of containers had the same interface (push_back, pop_back, 
>>> etc...)  Thoughts/opinion?
>>
>> Maybe Boost.Multi Index Container is what you are looking for.
>> /Pavel
>>
> Not quite.  I'm not looking for multiple ways to look at the underlying 
> data.
 > [snip]
> Algorithms would then work with any type of LinearContainer that has 
> traits supporting the operations required.  On further speculation this 
> may not be a useful thing to do, because it just moves the implied 
> interface from between the algorithms and the containers (push_back, 
> insert, etc...) to between the container and its traits.  Oh well, I was 
> just thinking out loud.

I have been thinking about the basic_string interface and have come to 
several conclusions that you might be interested in:
[1] The basic_string interface is *huge*;
[2] There are a group of functions that are required for a basic_string 
implementation to work and others that can be deduced from them;
[3] Supporting other non-standard (but standard conforming) string types 
such as ropes, constant strings and fixed-buffer strings is not easy;
[4] The flex_string structure is non-intuitive for creating new types, 
but masy be useful in different contexts.

This is basically an extension of the iterator_facade concept. Note that 
this has not yet been tested in a larger context to implement a full 
basic_string interface and can be extended to include concepts for 
containers (linear, etc.) as well.

Given:

#define BOOST_CRTP_IMPL(T)\
    T & derived() { return *static_cast< T * >( this ); }\
    const T & derived() const{ return *static_cast< const T * >( this ); }

Then:

template< typename T, typename Traits = T >
struct boost::strings::reverse_iterators
{
    BOOST_CRTP_IMPL(T)

    typedef typename Traits::iterator iterator;
    typedef typename Traits::const_iterator const_iterator;

    iterator begin(){ return derived().begin_(); }
    const_iterator begin() const{ return derived().begin_(); }
    iterator end(){ return derived().end_(); }
    const_iterator end() const{ return derived().end_(); }

    typedef boost::reverse_iterator< iterator > reverse_iterator;
    typedef boost::reverse_iterator< const_iterator > 
const_reverse_iterator;

    reverse_iterator rbegin(){ return reverse_iterator( derived().end()); }
    const_reverse_iterator rbegin() const{ return 
const_reverse_iterator( derived().end()); }
    reverse_iterator rend(){ return reverse_iterator( derived().begin()); }
    const_reverse_iterator rend() const{ return const_reverse_iterator( 
derived().begin()); }
};

means that you only need supply iterator, const_iterator, begin() and 
end() and the above will add reverse iterators. Here, I haven't made 
assumptions about the data, but if it is in linear memory (single 
allocated memory space such as a vector or normal string), then you can use:

template< typename T, typename Traits = T >
struct boost::strings::end_iterator
{
    BOOST_CRTP_IMPL(T)

    typedef typename Traits::iterator        iterator;
    typedef typename Traits::const_iterator  const_iterator;

    iterator end_(){ return derived().begin() + derived().size(); }
    const_iterator end_() const{ return derived().begin() + 
derived().size(); }
};

For example:

struct demo_string: public reverse_iterators< demo_string, 
string_traits< char > >,
    public end_iterator< demo_string, string_traits< char > >
{
    typedef string_traits< char > traits;
    typedef traitsiterator iterator;
    typedef traits::const_iterator const_iterator;

    static char * string;

          iterator begin_(){       return string; }
    const_iterator begin_() const{ return string; }
};

char * demo_string::string = "Hello in there!";

Regards,
Reece