The fast sequence container, which behaves like std::vector takes O(log(N)) to insert/delete elements. More...

#include <btree_seq.h>

Classes
class	iterator_base
	Iterator template for const_iterator and iterator. More...

Public Types
typedef A	allocator_type
	The last template parameter, allocator.

typedef A::value_type	value_type
	Value type, T (the first template parameter).

typedef A::reference	reference
	Reference type, T&.

typedef A::const_reference	const_reference
	Constant reference type, const T&.

typedef A::pointer	pointer
	Pointer type, T*.

typedef A::const_pointer	const_pointer
	Constant pointer type, const T*.

typedef A::size_type	size_type
	Unsigned integer type, size_t (unsigned int).

typedef A::difference_type	difference_type
	Signed integer type, ptr_diff_t (int).

typedef A::difference_type	diff_type
	Signed integer type, ptr_diff_t (int).

typedef iterator_base< const T >	const_iterator
	Constant forward random-access iterator.

typedef iterator_base< T >	iterator
	Modifying forward random-access iterator.

typedef std::reverse_iterator < const_iterator >	const_reverse_iterator
	Constant reverse random-access iterator.

typedef std::reverse_iterator < iterator >	reverse_iterator
	Modifying reverse random-access iterator.

Public Member Functions
	btree_seq (const allocator_type &alloc=allocator_type())
	Empty container constructor. More...

	btree_seq (const btree_seq< T, L, M, A > &that)
	Copy constructor. More...

	btree_seq (size_type n, const value_type &val, const allocator_type &alloc=allocator_type())
	Fill constructor. More...

template<typename Iterator >
	btree_seq (Iterator first, Iterator last, const allocator_type &alloc=allocator_type())
	Range constructor. More...

	btree_seq (btree_seq< T, L, M, A > &&that, const allocator_type &alloc=allocator_type())
	Move constructor (C++11) More...

	btree_seq (std::initializer_list< value_type > il, const allocator_type &alloc=allocator_type())
	Initializer list constructor (C++11) More...

	~btree_seq ()
	Destructor. More...

Iterators
const_iterator	begin () const
	Return constant iterator to beginning. More...

const_iterator	end () const
	Return constant iterator to end. More...

const_iterator	cbegin () const
	Return constant iterator to beginning. More...

const_iterator	cend () const
	Return constant iterator to end. More...

iterator	begin ()
	Return iterator to beginning. More...

iterator	end ()
	Return constant iterator to end. More...

const_reverse_iterator	rbegin () const
	Return constant reverse iterator to reverse beginning. More...

const_reverse_iterator	rend () const
	Return constant reverse iterator to reverse end. More...

const_reverse_iterator	crbegin () const
	Return constant reverse iterator to reverse beginning. More...

const_reverse_iterator	crend () const
	Return constant reverse iterator to reverse end. More...

reverse_iterator	rbegin ()
	Return reverse iterator to reverse beginning. More...

reverse_iterator	rend ()
	Return reverse iterator to reverse end. More...

iterator	iterator_at (size_type pos)
	Return iterator to a given index. More...

const_iterator	citerator_at (size_type pos) const
	Return constant iterator to a given index. More...

Access
Access of the contents
reference	operator[] (size_type pos)
	Access to element. More...

const_reference	operator[] (size_type pos) const
	Constant access to element. More...

size_type	size () const
	Number of elements in container.

reference	at (size_type pos)
	Access to element with range check. More...

const_reference	at (size_type pos) const
	Constant access to element with range check. More...

reference	front ()
	Returns a reference to the first element. More...

const_reference	front () const
	Returns a constnt reference to the first element. More...

reference	back ()
	Returns a reference to the last element. More...

const_reference	back () const
	Returns a constant reference to the last element. More...

bool	empty () const
	Returns true if the container contains no elements.

template<typename V >
size_type	visit (size_type first, size_type last, V &v)
	Sequential search/modify operation on the range. More...

Modifying certain elements of the sequence
void	insert (size_type pos, const value_type &val)
	Native function for inserting a single element. More...

template<class InputIterator >
void	insert (size_type pos, InputIterator first, InputIterator last)
	Native function for inserting a range of elements. More...

iterator	insert (const_iterator pos, const value_type &val)
	Compatible function for inserting the single element. More...

iterator	insert (const_iterator pos, size_type n, const value_type &val)
	Compatible function for inserting n copies of an element. More...

template<class InputIterator >
iterator	insert (const_iterator pos, InputIterator first, InputIterator last)
	Compatible function for inserting a range of elements. More...

void	insert (size_type pos, value_type &&val)
	Native inserting of rvalue (C++11) More...

iterator	insert (const_iterator pos, value_type &&val)
	Compatible insertion of rvalue (C++11) More...

void	insert (size_type pos, std::initializer_list< value_type > il)
	Native inserting of elements using initializer_list (C++11) More...

iterator	insert (const_iterator pos, std::initializer_list< value_type > il)
	Compatible inserting of elements using initializer_list (C++11) More...

void	fill (size_type pos, size_type repetition, const value_type &val)
	Native function for inserting n copies of an element. More...

void	resize (size_type n, const value_type &val=value_type())
	Resize container so that it contains n elements. More...

void	erase (size_type first, size_type last)
	Native function for erasing elements. More...

iterator	erase (const_iterator pos)
	Compatible function for erasing one element. More...

iterator	erase (const_iterator first, const_iterator last)
	Compatible function for erasing elements. More...

void	push_back (const value_type &val)
	Adds element to the end of the sequence. More...

void	push_front (const value_type &val)
	Adds element to the beginning of the sequence. More...

void	pop_back ()
	Removes the last element. More...

void	pop_front ()
	Removes the first element. More...

void	push_back (value_type &&val)
	Creates the element at the end of container and leaves val with undefined state. (C++11)

void	push_front (value_type &&val)
	Creates the element at the beginning of container and leaves val with undefined state. (C++11)

template<class... Args>
void	emplace (size_type pos, Args &&...args)
	Native emplace function (C++11) More...

template<class... Args>
iterator	emplace (const_iterator pos, Args &&...args)
	Constructs an element at the given position (C++11) More...

template<class... Args>
void	emplace_front (Args &&...args)
	Constructs an element at the beginning of the container and passes args to its constructor. (C++11)

template<class... Args>
void	emplace_back (Args &&...args)
	Constructs an element at the end of the container and passes args to its constructor. (C++11)

Modifying the whole contents of the sequence
btree_seq &	operator= (const btree_seq< T, L, M, A > &that)
	Assign content. More...

void	swap (btree_seq< T, L, M, A > &that)
	Swaps contents of two containers. More...

void	clear ()
	Erases all contents of the container. More...

void	assign (size_type n, const value_type &val)
	Replaces the whole contents with n copies of val. More...

template<class InputIterator >
void	assign (InputIterator first, InputIterator last)
	Replaces the whole contents with a range. More...

void	concatenate_right (btree_seq< T, L, M, A > &that)
	Fast concatenate two sequences (that sequence to the right). More...

void	concatenate_left (btree_seq< T, L, M, A > &that)
	Fast concatenate two sequences (that sequence to the left). More...

void	split_right (btree_seq< T, L, M, A > &that, size_type pos)
	Fast split, leaving right piece in that container. More...

void	split_left (btree_seq< T, L, M, A > &that, size_type pos)
	Fast split, leaving left piece in that container. More...

btree_seq &	operator= (btree_seq< T, L, M, A > &&that)
	Move operator= (C++11) More...

btree_seq &	operator= (std::initializer_list< value_type > il)
	Initializer list operator= (C++11) More...

void	assign (std::initializer_list< value_type > il)
	assign with initializer_list (C++11) More...

Others
Functions not used in release version: debug, profile and compatibility.
void	__check_consistency ()
	Checks consistency of the container (debug). More...

template<class output_stream >
void	__output (output_stream &o, const char *comm="")
	Output the contents of container into the stream (debug).

size_type	__children_in_branch ()
	Returns L (second parameter of the template) (profile, RTTI).

size_type	__elements_in_leaf ()
	Returns M (third parameter of the template) (profile, RTTI).

size_type	__branch_size ()
	Returns size of inner node of the tree (profile, RTTI).

size_type	__leaf_size ()
	Returns size of leaf node of the tree (profile, RTTI).

void	reserve (size_type n)
	Function does nothing (compatibility with std::vector).

void	shrink_to_fit ()
	Function does nothing (compatibility with std::vector).

allocator_type	get_allocator () const
	Returns allocator.

Detailed Description

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>
class btree_seq< T, L, M, A >

The fast sequence container, which behaves like std::vector takes O(log(N)) to insert/delete elements.

This container implements most of std::vector's members. It inserts/deletes elements much faster than any standart container. However, random access to the element takes O(log(N)) time as well. For sequential access to elements, iterators and visit exist, which require practically constant time per element. The implementation is based on btrees.

Template Parameters

T	the type of the element
L	maximal number of children per branch, default 30 minimum 4. You can change it for better performance.
M	maximal number of elements per leaf, default 60 minimum 4. You can change it for better performance.
A	allocator.

Constructor & Destructor Documentation

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

btree_seq< T, L, M, A >::btree_seq ( const allocator_type & alloc = allocator_type() )

inlineexplicit

Empty container constructor.

Constructs an empty container with no elements. Complexity: constant.

Parameters

alloc allocator

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

btree_seq< T, L, M, A >::btree_seq ( const btree_seq< T, L, M, A > & that )

inline

Copy constructor.

Copies all elements from another container. Complexity: O(N*log(N)), N=that.size().

Parameters

that	another container to be copied

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

btree_seq< T, L, M, A >::btree_seq	(	size_type	n,
		const value_type &	val,
		const allocator_type &	alloc = `allocator_type()`
	)

inlineexplicit

Fill constructor.

Constructs a container with n elements, each of them is copy of val. Complexity: O(n*log(n)).

Parameters

n	number of elements
val	fill value
alloc	allocator

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

template<typename Iterator >

btree_seq< T, L, M, A >::btree_seq	(	Iterator	first,
		Iterator	last,
		const allocator_type &	alloc = `allocator_type()`
	)

inline

Range constructor.

Constructs a container filled with elements from range [first,last). Complexity: O(N*log(N)), N=dist(last,first).

Parameters

first	first position in a range
last	last position in a range
alloc	allocator

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

btree_seq< T, L, M, A >::btree_seq	(	btree_seq< T, L, M, A > &&	that,
		const allocator_type &	alloc = `allocator_type()`
	)

inline

Move constructor (C++11)

Creates a copy of container and leaves that container in valid (empty) state.

Parameters

that	container to copy
alloc	allocator

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

btree_seq< T, L, M, A >::btree_seq	(	std::initializer_list< value_type >	il,
		const allocator_type &	alloc = `allocator_type()`
	)

inline

Initializer list constructor (C++11)

Creates a container with elements in initializer list.

Parameters

il	initializer_list
alloc	allocator to use

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

btree_seq< T, L, M, A >::~btree_seq ( )

inline

Destructor.

Deletes the contents and frees memory. Complexity: O(N*log(N)).

Member Function Documentation

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::__check_consistency ( )

Checks consistency of the container (debug).

Use this function when modifying this code or if you are unsure, if your program corrupts memory of the container.

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::assign	(	size_type	n,
		const value_type &	val
	)

Replaces the whole contents with n copies of val.

Erases contents of the container, then fills it with n copies of val. Complexity: O((n+M)*log(n+M)), M - existing elements, n - new ones

Parameters

n	new size of container
val	element to clone

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

template<class InputIterator >

void btree_seq< T, L, M, A >::assign	(	InputIterator	first,
		InputIterator	last
	)

inline

Replaces the whole contents with a range.

Erases contents of the container, then fills it with a copy of range [first,last). Complexity: O((n+M)*log(n+M)), M - existing elements, n - new ones

Parameters

first	first element to be inserted
last	element behind the last element to be inserted

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::assign ( std::initializer_list< value_type > il )

inline

assign with initializer_list (C++11)

Replaces the contents with the values of initializer_list

Parameters

il	new contents

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

reference btree_seq< T, L, M, A >::at ( size_type pos )

inline

Access to element with range check.

Returns a reference to the element at position pos. Complexity: O(log(N)).

Parameters

pos	index of the element

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

const_reference btree_seq< T, L, M, A >::at ( size_type pos ) const

inline

Constant access to element with range check.

Returns a constant reference to the element at position pos. Complexity: O(log(N)).

Parameters

pos	index of the element

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

reference btree_seq< T, L, M, A >::back ( )

inline

Returns a reference to the last element.

Complexity: O(log(N)).

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

const_reference btree_seq< T, L, M, A >::back ( ) const

inline

Returns a constant reference to the last element.

Complexity: O(log(N)).

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

const_iterator btree_seq< T, L, M, A >::begin ( ) const

inline

Return constant iterator to beginning.

Complexity: constant.

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

iterator btree_seq< T, L, M, A >::begin ( )

inline

Return iterator to beginning.

Complexity: constant.

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

const_iterator btree_seq< T, L, M, A >::cbegin ( ) const

inline

Return constant iterator to beginning.

Complexity: constant.

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

const_iterator btree_seq< T, L, M, A >::cend ( ) const

inline

Return constant iterator to end.

Complexity: constant.

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

const_iterator btree_seq< T, L, M, A >::citerator_at ( size_type pos ) const

inline

Return constant iterator to a given index.

Complexity: constant.

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::clear ( )

inline

Erases all contents of the container.

Complexity: O(N*log(N))

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::concatenate_left ( btree_seq< T, L, M, A > & that )

Fast concatenate two sequences (that sequence to the left).

Concatenate two sequences (that sequence to the left), put result into this sequence and leave that sequence empty. Concatenation is done without copying all elements. Example: if sequence A contains {0,1,2} and sequeance B contains {3,4,5}, after a call 'A.concatenate_left(B)' A contains {3,4,5,0,1,2} and B is empty. Complexity: O(log(N+M))

Parameters

that	container to concatenate

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::concatenate_right ( btree_seq< T, L, M, A > & that )

Fast concatenate two sequences (that sequence to the right).

Concatenate two sequences (that sequence to the right), put result into this sequence and leave that sequence empty. Concatenation is done without copying all elements. Example: if sequence A contains {0,1,2} and sequeance B contains {3,4,5}, after a call 'A.concatenate_right(B)' A contains {0,1,2,3,4,5} and B is empty. Complexity: O(log(N+M))

Parameters

that	container to concatenate

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

const_reverse_iterator btree_seq< T, L, M, A >::crbegin ( ) const

inline

Return constant reverse iterator to reverse beginning.

Complexity: constant.

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

const_reverse_iterator btree_seq< T, L, M, A >::crend ( ) const

inline

Return constant reverse iterator to reverse end.

Complexity: constant.

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

template<class... Args>

void btree_seq< T, L, M, A >::emplace	(	size_type	pos,
		Args &&...	args
	)

inline

Native emplace function (C++11)

Constructs an element using args and places it to the given position

Parameters

pos	position to create element
args	parameters passed to element's constructor

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

template<class... Args>

iterator btree_seq< T, L, M, A >::emplace	(	const_iterator	pos,
		Args &&...	args
	)

inline

Constructs an element at the given position (C++11)

Parameters

pos	position to place new element
args	arguments passed to the element's constructor

Returns: iterator pointing to the new element

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

const_iterator btree_seq< T, L, M, A >::end ( ) const

inline

Return constant iterator to end.

Complexity: constant.

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

iterator btree_seq< T, L, M, A >::end ( )

inline

Return constant iterator to end.

Complexity: constant.

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::erase	(	size_type	first,
		size_type	last
	)

Native function for erasing elements.

Erase the range of [first,last) elements. Complexity: O(M*log(N)), M-erased elements, N - all elements.

Parameters

first	index of the first element to erase
last	index of the last element to erase + 1

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

iterator btree_seq< T, L, M, A >::erase ( const_iterator pos )

inline

Compatible function for erasing one element.

Erase the element at position pos. Complexity: O(log(N)). Hint: native 'erase(size_type, size_type)' might be faster.

Parameters

pos	index of the element to erase

Returns: iterator pointing to the next position after erased element

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

iterator btree_seq< T, L, M, A >::erase	(	const_iterator	first,
		const_iterator	last
	)

inline

Compatible function for erasing elements.

Erase the range of [first,last) elements. Complexity: O(M*log(N)), M-erased elements, N - all elements. Hint: native 'erase(size_type, size_type)' might be faster.

Parameters

first	index of the first element to erase
last	index of the last element to erase + 1

Returns: iterator pointing to the next position after erased elements

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::fill	(	size_type	pos,
		size_type	repetition,
		const value_type &	val
	)

inline

Native function for inserting n copies of an element.

Inserts n copiesof an element at a given position. Complexity: O((n+M)*log(n+M)), M - existing elements, n - new ones.

Parameters

pos	position to insert
repetition	number of copies to insert
val	value to insert

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

reference btree_seq< T, L, M, A >::front ( )

inline

Returns a reference to the first element.

Complexity: O(log(N)).

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

const_reference btree_seq< T, L, M, A >::front ( ) const

inline

Returns a constnt reference to the first element.

Complexity: O(log(N)).

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::insert	(	size_type	pos,
		const value_type &	val
	)

inline

Native function for inserting a single element.

Inserts the element at given position. Hint: inserting the range is faster then multiple insertions of one element. Complexity: O(log(N)).

Parameters

pos	position to insert
val	element to insert

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

template<class InputIterator >

void btree_seq< T, L, M, A >::insert	(	size_type	pos,
		InputIterator	first,
		InputIterator	last
	)

Native function for inserting a range of elements.

Inserts the range [first,last) of elements into the given position. Complexity: O((N+M)*log(N+M)), N-existing elements, M - new ones.

Parameters

pos	position to insert
first	first element to insert
last	element behind the last element to insert

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

iterator btree_seq< T, L, M, A >::insert	(	const_iterator	pos,
		const value_type &	val
	)

inline

Compatible function for inserting the single element.

Inserts a single element at a given position. Complexity: O((N+M)*log(N+M)), N-existing elements, M - new ones. Hint: native 'insert(size_type, const value_type& t)' might be faster.

Parameters

pos	position to insert
val	value to insert

Returns: iterator pointing to the newly inserted element

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

iterator btree_seq< T, L, M, A >::insert	(	const_iterator	pos,
		size_type	n,
		const value_type &	val
	)

inline

Compatible function for inserting n copies of an element.

Inserts n copiesof an element at a given position. Complexity: O((n+M)*log(n+M)), M - existing elements, n - new ones. Hint: native 'fill(size_type, size_type, const value_type& val)' might be faster.

Parameters

pos	position to insert
n	number of copies to insert
val	value to insert

Returns: iterator pointing to the first of newly inserted elements

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

template<class InputIterator >

iterator btree_seq< T, L, M, A >::insert	(	const_iterator	pos,
		InputIterator	first,
		InputIterator	last
	)

inline

Compatible function for inserting a range of elements.

Inserts the range [first,last) of elements into the given position. Complexity: O((N+M)*log(N+M)), N-existing elements, M - new ones. Hint: native 'insert(size_type, InputIterator, InputIterator)' might be faster.

Parameters

pos	position to insert
first	first element to insert
last	element behind the last element to insert

Returns: iterator pointing to the first of newly inserted elements

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::insert	(	size_type	pos,
		value_type &&	val
	)

inline

Native inserting of rvalue (C++11)

Moves the value into the given position and leaves old value undefined but valid.

Parameters

pos	position where the value is inserted
val	the object to be moved

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

iterator btree_seq< T, L, M, A >::insert	(	const_iterator	pos,
		value_type &&	val
	)

inline

Compatible insertion of rvalue (C++11)

Moves the value into the given position and leaves old value undefined, but valid.

Parameters

pos	position where the value is inserted
val	the object to be moved

Returns: iterator pointing to the new inserted value

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::insert	(	size_type	pos,
		std::initializer_list< value_type >	il
	)

inline

Native inserting of elements using initializer_list (C++11)

Parameters

pos	place to insert
il	elements to insert

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

iterator btree_seq< T, L, M, A >::insert	(	const_iterator	pos,
		std::initializer_list< value_type >	il
	)

inline

Compatible inserting of elements using initializer_list (C++11)

Parameters

pos	place to insert
il	elements to insert

Returns: iterator pointing to the first of new inserted values

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

iterator btree_seq< T, L, M, A >::iterator_at ( size_type pos )

inline

Return iterator to a given index.

Complexity: constant.

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

btree_seq& btree_seq< T, L, M, A >::operator= ( const btree_seq< T, L, M, A > & that )

inline

Assign content.

Deletes old contents and replaces it with copy of contents of that. Complexity: O(N*log(N))+O(M*log(M)), N=this->size(), M=that.size().

Parameters

that	container to be assigned

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

btree_seq& btree_seq< T, L, M, A >::operator= ( btree_seq< T, L, M, A > && that )

inline

Move operator= (C++11)

Creates a copy and leaves that container in empty state.

Parameters

that	container to copy

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

btree_seq& btree_seq< T, L, M, A >::operator= ( std::initializer_list< value_type > il )

inline

Initializer list operator= (C++11)

Replaces the contents with the values of initializer_list

Parameters

il	new contents

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

reference btree_seq< T, L, M, A >::operator[] ( size_type pos )

inline

Access to element.

Returns a reference to the element at position pos. No range check is done. Complexity: O(log(N)).

Parameters

pos	index of the element

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

const_reference btree_seq< T, L, M, A >::operator[] ( size_type pos ) const

inline

Constant access to element.

Returns a constant reference to the element at position pos. No range check is done. Complexity: O(log(N)).

Parameters

pos	index of the element

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::pop_back ( )

inline

Removes the last element.

Complexity: O(log(N))

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::pop_front ( )

inline

Removes the first element.

Complexity: O(log(N))

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::push_back ( const value_type & val )

inline

Adds element to the end of the sequence.

Complexity: O(log(N))

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::push_front ( const value_type & val )

inline

Adds element to the beginning of the sequence.

Complexity: O(log(N))

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

const_reverse_iterator btree_seq< T, L, M, A >::rbegin ( ) const

inline

Return constant reverse iterator to reverse beginning.

Complexity: constant.

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

reverse_iterator btree_seq< T, L, M, A >::rbegin ( )

inline

Return reverse iterator to reverse beginning.

Complexity: constant.

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

const_reverse_iterator btree_seq< T, L, M, A >::rend ( ) const

inline

Return constant reverse iterator to reverse end.

Complexity: constant.

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

reverse_iterator btree_seq< T, L, M, A >::rend ( )

inline

Return reverse iterator to reverse end.

Complexity: constant.

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::resize	(	size_type	n,
		const value_type &	val = `value_type()`
	)

Resize container so that it contains n elements.

If n is greater than container size, copies of the val are added to the end. If n is less than container size, some elements at the end of container are deleted.

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::split_left	(	btree_seq< T, L, M, A > &	that,
		size_type	pos
	)

Fast split, leaving left piece in that container.

Split sequence into two parts: [pos,size) is left in this container, [0,pos) is moved to that container. That container is cleaned before operation. Example if A contained {0,1,2,3,4}, after A.split_left(B,3) A contains {3,4} and B contains {0,1,2}. The operation is done without moving all elements. Complexity: O(log(N)), if the second container is initially empty.

Parameters

that	container for leftt part of split operation (old contents removed)
pos	place to split

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::split_right	(	btree_seq< T, L, M, A > &	that,
		size_type	pos
	)

Fast split, leaving right piece in that container.

Split sequence into two parts: [0,pos) is left in this container, [pos,size) is moved to that container. That container is cleaned before operation. Example if A contained {0,1,2,3,4}, after A.split_right(B,3) A contains {0,1,2} and B contains {3,4}. The operation is done without moving all elements. Complexity: O(log(N)), if the second container is initially empty.

Parameters

that	container for right part of split operation (old contents removed)
pos	place to split

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

void btree_seq< T, L, M, A >::swap ( btree_seq< T, L, M, A > & that )

Swaps contents of two containers.

Complexity: constant.

Parameters

that	container to swap with

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>

template<typename V >

size_type btree_seq< T, L, M, A >::visit	(	size_type	first,
		size_type	last,
		V &	v
	)

Sequential search/modify operation on the range.

Implements visitor pattern. The function 'visit' calls v() on the elements in the given range sequentially, until the end of range is reached or v() returns true (whichever happens earlier). This function allows to implement patterns like find_if, for_each and so on, but it behaves significantly (roughly twice) faster than standard implementation and iterator access. Complexity: O(log(N)*(end-start))

Parameters

first	the first element on which visitor should be called
last	the element beyond the last element on which visitor should be called
v	the visitor class, which must have 'bool operator(element&)'

Returns: the index of the first element when v() returned true, or end if v() never returned true

The documentation for this class was generated from the following file:

btree_seq.h

Classes

Public Types

Public Member Functions

Detailed Description

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>> class btree_seq< T, L, M, A >

Constructor & Destructor Documentation

Member Function Documentation

template<typename T, int L = 30, int M = 60, typename A = std::allocator<T>>
class btree_seq< T, L, M, A >