v3.1
26 May 2014
minor refactoring: insert() taking count/value now calls insert() taking iterator range rather than other way around; improved function dispatching using SFINAE.
v3.0.5
21 March 2014
container base class was using new to allocate the "nil" tree node rather than using an allocator (thanks to Glen Fernandes for spotting this).
allocators could not be passed to container constructors (thanks to Glen Fernandes for spotting this).
v3.0.4
6 March 2014
fixed some compiler errors raised when compiling with g++ (not raised by VC++).
v3.0.3
5 March 2014
minor optimization.
v3.0.2
5 March 2014
fixed bug in multiple element insert().
v3.0.1
5 March 2014
array_tree shouldn't have been a template (it was for debugging purposes).
v3.0
5 March 2014
Completely rewritten from scratch; data structure is now a combined linked list and red-black tree which allows logarithmic time random access.
v2.6.1
29 September 2011
made iterator_base::position() a protected member function rather than a public member function; an iterator's public interface should not deviate from that which the standard C++ container library provides to remain within the spirit of the container library.
v2.6
15 September 2011
bugfix: fixed some compiler errors that VC++ did not pick up; now builds with g++ v4.5.3 with -std=c++0x compiler option.
v2.5
29 March 2011
bugfix: iterator code handled negative difference_type values incorrectly.
v2.4.1
24 May 2010
internal (minor refactor): iterator and const_iterator classes were not using base class typedef in their constructor initializer lists.
v2.4
24 May 2010
bugfix: iterator_base class was friends without itself instead of friends with a template of itself.
bugfix: missing typename qualifier in do_insert.
v2.3
18 January 2010
bugfix: some iterator member functions were not const.
bugfix: some iterator member functions returned a copy instead of a reference.
v2.2
24 December 2009
constructor which takes a count and value now has a default parameter for value.
v2.1
7 August 2009
bugfix (major): element range insert did not work correctly when inserting at the end of the controlled sequence, this bug did not manifest until now as element range insert was not being used.
bugfix: looped single element insert was being used instead of element range insert when inserting an element range.
bugfix: exception safety improvements.
refactor: segmented_array now uses new unchecked vecarray (possible performance enhancement)
v2.0.1
11 February 2009
bugfix: fixed possible crash when used with VC++ 2008 (cause: invalid dereference of std::list end() iterator in erase() method).
bugfix (minor): #include <tr1/type_traits> changed to #include <type_traits>.
v1.1.10
25 May 2008
bugfix: do_insert incorrectly incremented end() iterator when container was empty (which would mean a crash with non-circular std::list implementations)
refactor: removed end()/begin() wrapping in increment_segment and decrement_segmented. added assertions to check for end().
v1.1.8
11 April 2008
bugfix: do_insert incorrectly decremented end() iterator when container was empty (which would mean a crash with non-circular std::list implementations)
v1.1.7
29 January 2008
iterator comparison operators are now templated so const and non-const iterators can be compared
v1.1.6
22 January 2008
bugfix: difference_type iterator::operator-(iterator) was member function was not const
v1.1.5
20 January 2008
bugfix: iterator_base::add used non-const iterator variable for const iterator type meaning adding to const_iterator would not compile
v1.1.4
7 December 2007
bugfix: iterator_base::operator!=() functioned incorrectly, iterator_base::operator==() and iterator_base::operator-=() now simply use integer position for comparison
bugfix: erase(iterator, iterator) used end() iterator after it became invalid
v1.1.1
20 November 2007
added segmented_array(size_type, parameter_type) constructor
v1.1
18 November 2007
multiple changes, now compiles under g++
now resides under the default namespace "lib"
v1.0.25
17 November 2007
replaced #include <assert.h> with #include <cassert>
added #include <cstddef>
replaced size_t with std::size_t
added references to standard name typedefs in iterator_base
moved iter() method from derived iterator classes to iterator_base
bugfix: iterator_base template copy constructor did not use unique template parameter names (causes compiliation failure)
added standard name typedefs for iterator_base's template parameter types
bugfix: added non-template version of iterator_base copy constructor
v1.0.22
14 November 2007
after some thought re-added push_front() and pop_front() as they are in fact O(1) complexity (in terms of n container elements)
bugfix: integer position was not updated correctly by rewritten iterator_base::add()
optimization: iterator_base::add() rewritten so now "begin() + n" is as fast as locate(n)
optimization (minor): iterator_base::add() now only calculates "seg.end() - iSegmentCurrent" once instead of twice per iteration
v1.0.18
13 November 2007
added template swap() method
(cosmetic) changed "InputIterator" to "Integer" in dispatch_insert(..., std::tr1::true_type)
(cosmetic) changed occurrences of "traited" to "dispatch"
re-added template copy constructor and template assignment operator
made assignment operator and copy constructor non-templated
do_insert() no longer uses now removed vecarray::insert(iterator, const_iterator, size_type) method
copy constructor now takes templated source
bugfix: assignment operator now has scope unique template parameter names (compilation could have failed)
added #includes (<type_traits> and <stdexcept>)
minor optimization: now uses segment::parameter_type
added assignment operator
added assign() methods
added insert(iterator, size_type, parameter_type) method
removed superfluous insert(iterator, const T*, size_type) method
insert(iterator, InputIterator, InputIterator) method now behaves differently depending on is_integral(InputIterator) trait
v1.0.10
12 November 2007
optimization: replaced several calls to postfix increment/decrement operators with calls to prefix increment/decrement operators
bugfix: at() methods didn't compile because checked_iterator and checked_const_iterator referred to the now removed iIndex iterator member
bugfix: at() method didn't compile because checked_const_iterator constructor called incorrect base class constructor (iterator instead of const_iterator)
at(n) methods now throw a std::out_of_range exception if n >= size()
bugfix: const_iterator locate(size_type) didn't pass position to iterator return value constructor (compilation would fail if used)
v1.0.7
11 November 2007
removed push_front() and pop_front() methods as they are not O(1) complexity
optimization: push_back() now calls vecarray::push_back() instead of vecarray::insert() for the most common case resulting in a significant performance gain for push_back() method
added front() and back() element accessor methods
v1.0.5
10 November 2007
optimization: insert(position, const T&) no longer uses locate to obtain iterator return value
v1.0.4
9 November 2007
added segmented_array(InputIterator first, InputIterator last) constructor
added insert(iterator position, InputIterator first, InputIterator last) method
renamed two (now private) insert(...) methods to do_insert(...)
removed superfluous do_insert() method
v1.0.2
8 November 2007
bugfix: erase(iterator) returned invalid iterator (position incorrect)
bugfix: remove() used invalid iterator (causes crash), now uses iterator returned from erase()
changed push_back() return type to void and removed default argument
added allocator_type typedef
pointer, reference, const_pointer, const_reference now typedef'd from allocator
added support for correct iterator::pointer and iterator::reference types to iterator_base
v1.0.1
7 November 2007
bugfix: iterator_base::subtract() now calls decrement_segement() when iterating past beginning of segment
bugfix: iterator_base::subtract() now decrements position when calling decrement_segement()
iterator_nase::add()/subtract() now do nothing if n <= 0
bugfix: iterator_base::increment_segment()/decrement_segment() no longer reset position to 0
bugfix: position is now always updated by iterator_base::increment()/decrement()
bugfix: iterator_base::seg() now returns const segment& if iterator is a const_iterator
copy constructor now copies elements rather than segments saving memory
added insert(iterator, const_iterator, const_iterator) method
added swap(segmented_array&) method
iterator_base, checked_iterator and checked_const_iterator are now private classes
added default segment size (64)
added #includes (<list>, "vecarray.h")
renamed header file from segment.h to segmented_array.h