Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
segmented_array et al now on GitHub
49 views
Skip to first unread message
Mr Flibble
Jan 18, 2016, 6:12:54 PM1/18/16
to
All your favourite sausages can now be found on GitHub including
segmented_array.
https://github.com/FlibbleMr/neolib
"A segmented_array is a container implemented as both a linked list and
a red-black tree of fixed sized segments (vecarray arrays). Being a
segmented array (as opposed to a normal flat array) its elements are not
stored contiguously in memory but are contiguous within a segment.
Compared to a std::vector or std::deque it performs considerably better
at inserting/erasing elements at any point in the controlled sequence.
Random access performs well being O(lg N) complexity so performs
considerably better than std::list. push_back() and pop_back() are O(lg
N) complexity. Single element insert() and erase(), push_front() and
pop_front() are also O(lg N) complexity (an example which illustrates
this). The performance of multiple element insert() and erase() is
linear in the number of items inserted/erased."
/Flibble
segmented_array.
https://github.com/FlibbleMr/neolib
"A segmented_array is a container implemented as both a linked list and
a red-black tree of fixed sized segments (vecarray arrays). Being a
segmented array (as opposed to a normal flat array) its elements are not
stored contiguously in memory but are contiguous within a segment.
Compared to a std::vector or std::deque it performs considerably better
at inserting/erasing elements at any point in the controlled sequence.
Random access performs well being O(lg N) complexity so performs
considerably better than std::list. push_back() and pop_back() are O(lg
N) complexity. Single element insert() and erase(), push_front() and
pop_front() are also O(lg N) complexity (an example which illustrates
this). The performance of multiple element insert() and erase() is
linear in the number of items inserted/erased."
/Flibble
Daniel
Jan 19, 2016, 11:29:36 PM1/19/16
to
On Monday, January 18, 2016 at 6:12:54 PM UTC-5, Mr Flibble wrote:
> All your favourite sausages can now be found on GitHub including
> segmented_array.
>
> https://github.com/FlibbleMr/neolib
>
Thanks for posting this.
> All your favourite sausages can now be found on GitHub including
> segmented_array.
>
> https://github.com/FlibbleMr/neolib
>
I note that while array_tree has a stateful allocator, the swap method does not swap the allocator, but does swap pointers to data that were allocated with the allocator.
Is this safe?
Thanks,
Daniel
Mr Flibble
Jan 20, 2016, 2:41:40 PM1/20/16
to
/Flibble
Mr Flibble
Jan 20, 2016, 3:00:56 PM1/20/16
to
On 20/01/2016 04:29, Daniel wrote:
/Flibble
Daniel
Jan 20, 2016, 6:45:02 PM1/20/16
to
On Tuesday, January 19, 2016 at 11:29:36 PM UTC-5, Daniel wrote:
> On Monday, January 18, 2016 at 6:12:54 PM UTC-5, Mr Flibble wrote:
> > All your favourite sausages can now be found on GitHub including
> > segmented_array.
> >
> > https://github.com/FlibbleMr/neolib
> >
> Thanks for posting this.
>
Two other comments.
> On Monday, January 18, 2016 at 6:12:54 PM UTC-5, Mr Flibble wrote:
> > All your favourite sausages can now be found on GitHub including
> > segmented_array.
> >
> > https://github.com/FlibbleMr/neolib
> >
> Thanks for posting this.
>
First, you have a lot of occurrences of allocate followed by construct. I think you should wrap construct in a try/catch, or use an RAI artifice, to ensure that deallocate is called if construct throws.
Second, you call construct and destroy directly on the allocator. In C++ 11, these calls should go through std::allocator_traits, as allocators are not required to provide construct and destroy.
Daniel
Mr Flibble
Jan 21, 2016, 2:09:38 PM1/21/16
to
/Flibble
0 new messages