Re: [boost] sequence_array contribution

From: Toon Knapen (toon.knapen_at_[hidden])
Date: 2003-05-28 05:59:17

On Thursday 22 May 2003 12:51, Maarten Hilferink wrote:
> template<typename T> struct sequence_array<T>;
> which has an interface that is almost compatible with
> std::vector<std::vector<T> >;
> but faster.

and more compact I presume. AFAICT the drawback will
be that the sequece is not as dynamic anymore as a 
vector-of-vectors (vov)

> template<typename T> struct sequence_array<T>;
> that uses an internal
>     std::vector<T> m_Data;
> for sequencial storage of sequences of T
> and an additional
>     std::vector<std::pair<T*, T*> > m_Seqs;
> for identifying allocated sequences.

But isn't always gauranteed : m_seqs[i].second == m_seqs[i+1].first ?
In this case you could shrink the memory footprrint with another pointer
per innter vector.

> sequence_array offers typedef iterator, const_iterator, reference, and
> const_reference
> with interfaces nearly compatibe with
> std::vector<T>*, const std::vector<T>*, vector<T>&, resp. const vector<T>&.
> (the sequences however don't have a reserve() member function,
Why not ? I have something similar as you and definitly need reserve.
But my reserve takes two arguments : the number of internal vectors
(will reserve m_seqs) and the storage consumed by all internal vectors
(will reserve m_data).

> For the discussion, I have made my pre-boost facilities library available
> at:
> http://www.objectvision.nl/dms/downloads/rtc-src-2003-05-21.zip
> It contains the file GeoSequence.h, which contains the
> template <typename Field> struct SequenceArray;
> I specifically would like to hear from you on the following design issues:
> - I am considering to change the definition of the above mentioned m_Seqs
> to:
>     std::vector<std::pair<size_t, size_t> > m_Seqs;
> where m_Seqs[i].first and second are offsets of the start and end of
> sequence i relative to m_Data.begin().
> This avoids adjustment when m_Data grows, for a small const access-time
> penalty.
In my implementation, I allways recalculate m_seqs when m_data grows.
But you would need to perform profiling to know what's best actually.

> 1. Arye you interested in such contribution?
I am but need to make sure it provides enough performance for my 
specific case.

> 3. Do you know of other solutions for efficient management of
> sequence_arrays?
vector-of-vectors with your home-brewn allocaters (using a pool for instance).

> 4. Is my assumtion true that the above described behaviour could not have
> been created
> by using a smart allocator as a second template argument to std::vector?
> (I assumed this since allocators cannot have a vector instance specific
> state)
oops, see question 3