Extension to darray resulting in a sorted darray via insert(). More...

#include <darray_sorted.hpp>

Inheritance diagram for jau::darray_sorted< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >:

Collaboration diagram for jau::darray_sorted< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >:

Public Types
typedef darray< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >	darray_type

enum	order_t { UP , DOWN }

typedef Size_type	size_type

typedef Value_type	value_type

Public Member Functions
	darray_sorted (const darray_sorted &m)

	darray_sorted (order_t order=UP)

bool	contains (const value_type &x) const noexcept

constexpr iterator	erase (const size_type first_idx, const size_type last_idx)
	Similar to std::vector::erase() using indices, removes the elements in the range [first_idx, last_idx). More...

constexpr iterator	erase (const size_type pos_idx)
	Similar to std::vector::erase() using an index, removes the elements at pos_idx. More...

constexpr iterator	erase (const_iterator pos)
	Like std::vector::erase(), removes the elements at pos. More...

constexpr iterator	erase (iterator first, const_iterator last)
	Like std::vector::erase(), removes the elements in the range [first, last). More...

size_type	index_of (const value_type &x) const
	Returns index of given element if found or npos. More...

size_type	insert (const value_type &a)

darray_sorted &	operator= (const darray_sorted &m)

constexpr size_type	size () const noexcept
	Like std::vector::size(). More...

Static Public Attributes
static constexpr const size_type	npos = std::numeric_limits<size_type>::max()
	Special value representing maximal value of size_type, used to denote an invalid index position return value, i.e. More...

Additional Inherited Members
Protected Types inherited from jau::darray< Value_type, jau::nsize_t, jau::callocator< Value_type >, std::is_trivially_copyable_v< Value_type >\|\|is_container_memmove_compliant_v< Value_type >, is_enforcing_secmem_v< Value_type > >
typedef jau::callocator< Value_type >	allocator_type

typedef const value_type *	const_iterator

typedef const value_type *	const_pointer

typedef const value_type &	const_reference

typedef bool	darray_tag
	Used to determine whether this type is a darray or has a darray, see ::is_darray_type<T> More...

typedef std::make_signed< size_type >::type	difference_type

typedef bool(*	equal_comparator) (const value_type &a, const value_type &b)
	Generic value_type equal comparator to be user defined for e.g. More...

typedef value_type *	iterator

typedef value_type *	pointer

typedef value_type &	reference

typedef jau::nsize_t	size_type

typedef Value_type	value_type

Protected Member Functions inherited from jau::darray< Value_type, jau::nsize_t, jau::callocator< Value_type >, std::is_trivially_copyable_v< Value_type >\|\|is_container_memmove_compliant_v< Value_type >, is_enforcing_secmem_v< Value_type > >
constexpr	darray () noexcept
	Default constructor, giving zero capacity and zero memory footprint. More...

constexpr	darray (const darray &x)
	Creates a new instance, copying all elements from the given darray. More...

constexpr	darray (const darray &x, const float growth_factor, const allocator_type &alloc)
	Creates a new instance, copying all elements from the given darray. More...

constexpr	darray (const darray &x, const size_type _capacity, const float growth_factor, const allocator_type &alloc)
	Creates a new instance with custom initial storage capacity, copying all elements from the given darray. More...

constexpr	darray (const size_type _capacity, const_iterator first, const_iterator last, const float growth_factor=DEFAULT_GROWTH_FACTOR, const allocator_type &alloc=allocator_type())
	Creates a new instance with custom initial storage capacity, copying all elements from the given const_iterator value_type range [first, last). More...

constexpr	darray (const size_type _capacity, InputIt first, InputIt last, const float growth_factor=DEFAULT_GROWTH_FACTOR, const allocator_type &alloc=allocator_type())
	Creates a new instance with custom initial storage capacity, copying all elements from the given template input-iterator value_type range [first, last). More...

constexpr	darray (darray &&x) noexcept

constexpr	darray (darray &&x, const float growth_factor, const allocator_type &alloc) noexcept

constexpr	darray (InputIt first, InputIt last, const allocator_type &alloc=allocator_type())
	Creates a new instance, copying all elements from the given template input-iterator value_type range [first, last). More...

constexpr	darray (size_type capacity, const float growth_factor=DEFAULT_GROWTH_FACTOR, const allocator_type &alloc=allocator_type())
	Creating an empty instance with initial capacity and other (default) properties. More...

constexpr	darray (std::initializer_list< value_type > initlist, const allocator_type &alloc=allocator_type())
	Create a new instance from an initializer list. More...

	~darray () noexcept

constexpr void	assign (const_iterator first, const_iterator last)
	Like std::vector::assign(), but non-template overload using const_iterator. More...

constexpr void	assign (InputIt first, InputIt last)
	Like std::vector::assign() More...

reference	at (size_type i)
	Like std::vector::at(size_type), mutable reference. More...

const_reference	at (size_type i) const
	Like std::vector::at(size_type), immutable reference. More...

constexpr reference	back ()
	Like std::vector::back(), mutable access. More...

constexpr const_reference	back () const
	Like std::vector::back(), immutable access. More...

constexpr const_iterator	begin () const noexcept

constexpr iterator	begin () noexcept

constexpr size_type	capacity () const noexcept
	Return the current capacity. More...

constexpr bool	capacity_reached () const noexcept
	Returns true if capacity has been reached and the next push_back() will grow the storage and invalidates all iterators and references. More...

constexpr const_iterator	cbegin () const noexcept

constexpr const_iterator	cend () const noexcept

constexpr void	clear () noexcept
	Like std::vector::clear(), but ending with zero capacity. More...

constexpr const_pointer	data () const noexcept
	Like std::vector::data(), const immutable pointer. More...

constexpr pointer	data () noexcept
	Like std::vector::data(), mutable pointer. More...

constexpr iterator	emplace (const_iterator pos, Args &&... args)
	Like std::vector::emplace(), construct a new element in place. More...

constexpr reference	emplace_back (Args &&... args)
	Like std::vector::emplace_back(), construct a new element in place at the end(). More...

constexpr bool	empty () const noexcept
	Like std::vector::empty(). More...

constexpr const_iterator	end () const noexcept

constexpr iterator	end () noexcept

constexpr iterator	erase (const size_type first_idx, const size_type last_idx)
	Similar to std::vector::erase() using indices, removes the elements in the range [first_idx, last_idx). More...

constexpr iterator	erase (const size_type pos_idx)
	Similar to std::vector::erase() using an index, removes the elements at pos_idx. More...

constexpr iterator	erase (const_iterator pos)
	Like std::vector::erase(), removes the elements at pos. More...

constexpr iterator	erase (iterator first, const_iterator last)
	Like std::vector::erase(), removes the elements in the range [first, last). More...

constexpr size_type	erase_matching (const value_type &x, const bool all_matching, equal_comparator comparator)
	Erase either the first matching element or all matching elements. More...

constexpr reference	front ()
	Like std::vector::front(), mutable access. More...

constexpr const_reference	front () const
	Like std::vector::front(), immutable access. More...

allocator_type	get_allocator () const noexcept

const allocator_type &	get_allocator_ref () const noexcept

constexpr size_type	get_grown_capacity () const noexcept
	Return the current capacity() multiplied by the growth factor, minimum is max(capacity()+1, 10). More...

std::string	get_info () const noexcept

constexpr float	growth_factor () const noexcept

constexpr iterator	insert (const size_type pos_idx, const value_type &x)
	Similar to std::vector::insert() using an index, copy. More...

constexpr iterator	insert (const_iterator pos, const value_type &x)
	Like std::vector::insert(), copy. More...

constexpr iterator	insert (const_iterator pos, InputIt first, InputIt last)
	Like std::vector::insert(), inserting the value_type range [first, last). More...

constexpr iterator	insert (const_iterator pos, value_type &&x)
	Like std::vector::insert(), move. More...

constexpr size_type	max_size () const noexcept
	Returns `std::numeric_limits<difference_type>::max()` as the maximum array size. More...

constexpr darray &	operator= (const darray &x)
	Like std::vector::operator=(&), assignment. More...

constexpr darray &	operator= (darray &&x) noexcept
	Like std::vector::operator=(&&), move. More...

const_reference	operator[] (size_type i) const noexcept
	Like std::vector::operator[](size_type), immutable reference. More...

reference	operator[] (size_type i) noexcept
	Like std::vector::operator[](size_type), mutable reference. More...

constexpr void	pop_back () noexcept
	Like std::vector::pop_back(). More...

constexpr void	push_back (const value_type &x)
	Like std::vector::push_back(), copy. More...

constexpr void	push_back (InputIt first, InputIt last)
	Like std::vector::push_back(), but appends the value_type range [first, last). More...

constexpr void	push_back (value_type &&x)
	Like std::vector::push_back(), move. More...

constexpr void	push_back_list (Args &&... args)
	Like push_back(), but for more multiple r-value references to move. More...

constexpr void	push_back_list (const Args &... args)
	Like push_back(), but for more multiple const r-value to copy. More...

constexpr bool	push_back_unique (const value_type &x, equal_comparator comparator)
	Like std::vector::push_back(), but only if the newly added element does not yet exist. More...

constexpr void	push_front (const value_type &x)
	Like std::vector::push_front(), copy. More...

constexpr void	push_front (value_type &&x)
	Like std::vector::push_front(), move. More...

void	reserve (size_type new_capacity)
	Like std::vector::reserve(), increases this instance's capacity to `new_capacity`. More...

constexpr void	shrink_to_fit ()
	Like std::vector::shrink_to_fit(), but ensured `constexpr`. More...

constexpr size_type	size () const noexcept
	Like std::vector::size(). More...

constexpr void	swap (darray &x) noexcept
	Like std::vector::swap(). More...

std::string	toString () const noexcept

Static Protected Attributes inherited from jau::darray< Value_type, jau::nsize_t, jau::callocator< Value_type >, std::is_trivially_copyable_v< Value_type >\|\|is_container_memmove_compliant_v< Value_type >, is_enforcing_secmem_v< Value_type > >
static constexpr const float	DEFAULT_GROWTH_FACTOR
	Default growth factor using the golden ratio 1.618. More...

static constexpr const bool	uses_memmove

static constexpr const bool	uses_realloc

static constexpr const bool	uses_secmem

Detailed Description

template<typename Value_type, typename Size_type = jau::nsize_t, typename Alloc_type = jau::callocator<Value_type>, bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>, bool use_secmem = is_enforcing_secmem_v<Value_type>>
class jau::darray_sorted< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >

Extension to darray resulting in a sorted darray via insert().

In der hier deklarierten Template-Klasse 'darray_sorted' werden die einzelnen Listen Elemente sofort beim Einfuegen der Groesse nach sortiert ( In aufsteigender(UP)/absteigender(DOWN) Reihenfolge ). D.h. die Methode 'fuegeEin' fuegt die Listenelemente mittels Bisektionierung gleich sortiert ein.

fuegeEin liefert nun den Index zurueck, den das eingefuegte Element besitzt, ansonsten npos. die Listenelemente gleich sortiert eingefuegt werden, mittel Bisektionierung.

Neu ist die Methode findeElement, welche ebenfalls nach der MEthode der Bisektionierung arbeitet.

Template Parameters

Value_type
Alloc_type
Size_type
use_memmove
use_secmem

Definition at line 63 of file darray_sorted.hpp.

Member Typedef Documentation

◆ darray_type

template<typename Value_type , typename Size_type = jau::nsize_t, typename Alloc_type = jau::callocator<Value_type>, bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>, bool use_secmem = is_enforcing_secmem_v<Value_type>>

typedef darray<Value_type, Size_type, Alloc_type, use_memmove, use_secmem> jau::darray_sorted< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >::darray_type

Definition at line 65 of file darray_sorted.hpp.

◆ value_type

template<typename Value_type , typename Size_type = jau::nsize_t, typename Alloc_type = jau::callocator<Value_type>, bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>, bool use_secmem = is_enforcing_secmem_v<Value_type>>

typedef Value_type jau::darray< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >::value_type

Definition at line 159 of file darray.hpp.

◆ size_type

template<typename Value_type , typename Size_type = jau::nsize_t, typename Alloc_type = jau::callocator<Value_type>, bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>, bool use_secmem = is_enforcing_secmem_v<Value_type>>

typedef Size_type jau::darray< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >::size_type

Definition at line 166 of file darray.hpp.

Member Enumeration Documentation

◆ order_t

template<typename Value_type , typename Size_type = jau::nsize_t, typename Alloc_type = jau::callocator<Value_type>, bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>, bool use_secmem = is_enforcing_secmem_v<Value_type>>

enum jau::darray_sorted::order_t

Enumerator
UP
DOWN

Definition at line 78 of file darray_sorted.hpp.

Constructor & Destructor Documentation

◆ darray_sorted() [1/2]

template<typename Value_type , typename Size_type = jau::nsize_t, typename Alloc_type = jau::callocator<Value_type>, bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>, bool use_secmem = is_enforcing_secmem_v<Value_type>>

jau::darray_sorted< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >::darray_sorted ( order_t order = UP )

inline

Definition at line 80 of file darray_sorted.hpp.

◆ darray_sorted() [2/2]

template<typename Value_type , typename Size_type = jau::nsize_t, typename Alloc_type = jau::callocator<Value_type>, bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>, bool use_secmem = is_enforcing_secmem_v<Value_type>>

jau::darray_sorted< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >::darray_sorted ( const darray_sorted< Value_type, Size_type, Alloc_type, use_memmove, use_secmem > & m )

inline

Definition at line 81 of file darray_sorted.hpp.

Member Function Documentation

◆ operator=()

template<typename Value_type , typename Size_type = jau::nsize_t, typename Alloc_type = jau::callocator<Value_type>, bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>, bool use_secmem = is_enforcing_secmem_v<Value_type>>

darray_sorted & jau::darray_sorted< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >::operator= ( const darray_sorted< Value_type, Size_type, Alloc_type, use_memmove, use_secmem > & m )

inline

Definition at line 83 of file darray_sorted.hpp.

◆ insert()

template<typename Value_type , typename Size_type = jau::nsize_t, typename Alloc_type = jau::callocator<Value_type>, bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>, bool use_secmem = is_enforcing_secmem_v<Value_type>>

size_type jau::darray_sorted< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >::insert ( const value_type & a )

inline

Definition at line 90 of file darray_sorted.hpp.

◆ contains()

template<typename Value_type , typename Size_type = jau::nsize_t, typename Alloc_type = jau::callocator<Value_type>, bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>, bool use_secmem = is_enforcing_secmem_v<Value_type>>

bool jau::darray_sorted< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >::contains ( const value_type & x ) const

inlinenoexcept

Definition at line 102 of file darray_sorted.hpp.

◆ index_of()

template<typename Value_type , typename Size_type = jau::nsize_t, typename Alloc_type = jau::callocator<Value_type>, bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>, bool use_secmem = is_enforcing_secmem_v<Value_type>>

size_type jau::darray_sorted< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >::index_of ( const value_type & x ) const

inline

Returns index of given element if found or npos.

Parameters

x

Returns

Definition at line 111 of file darray_sorted.hpp.

Here is the caller graph for this function:

◆ erase() [1/4]

template<typename Value_type , typename Size_type = jau::nsize_t, typename Alloc_type = jau::callocator<Value_type>, bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>, bool use_secmem = is_enforcing_secmem_v<Value_type>>

constexpr iterator jau::darray< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >::erase ( const_iterator pos )

inlineconstexpr

Like std::vector::erase(), removes the elements at pos.

Returns: iterator following the last removed element.

Definition at line 940 of file darray.hpp.

◆ erase() [2/4]

template<typename Value_type , typename Size_type = jau::nsize_t, typename Alloc_type = jau::callocator<Value_type>, bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>, bool use_secmem = is_enforcing_secmem_v<Value_type>>

constexpr iterator jau::darray< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >::erase	(	iterator	first,
		const_iterator	last
	)

inlineconstexpr

Like std::vector::erase(), removes the elements in the range [first, last).

Returns: iterator following the last removed element.

Definition at line 956 of file darray.hpp.

◆ erase() [3/4]

template<typename Value_type , typename Size_type = jau::nsize_t, typename Alloc_type = jau::callocator<Value_type>, bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>, bool use_secmem = is_enforcing_secmem_v<Value_type>>

constexpr iterator jau::darray< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >::erase ( const size_type pos_idx )

inlineconstexpr

Similar to std::vector::erase() using an index, removes the elements at pos_idx.

Returns: iterator following the last removed element.

Definition at line 972 of file darray.hpp.

◆ erase() [4/4]

template<typename Value_type , typename Size_type = jau::nsize_t, typename Alloc_type = jau::callocator<Value_type>, bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>, bool use_secmem = is_enforcing_secmem_v<Value_type>>

constexpr iterator jau::darray< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >::erase	(	const size_type	first_idx,
		const size_type	last_idx
	)

inlineconstexpr

Similar to std::vector::erase() using indices, removes the elements in the range [first_idx, last_idx).

Returns: iterator following the last removed element.

Definition at line 980 of file darray.hpp.

◆ size()

template<typename Value_type , typename Size_type = jau::nsize_t, typename Alloc_type = jau::callocator<Value_type>, bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>, bool use_secmem = is_enforcing_secmem_v<Value_type>>

constexpr size_type jau::darray< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >::size ( ) const

inlineconstexprnoexcept

Like std::vector::size().

Definition at line 763 of file darray.hpp.

Here is the caller graph for this function:

Member Data Documentation

◆ npos

template<typename Value_type , typename Size_type = jau::nsize_t, typename Alloc_type = jau::callocator<Value_type>, bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>, bool use_secmem = is_enforcing_secmem_v<Value_type>>

constexpr const size_type jau::darray_sorted< Value_type, Size_type, Alloc_type, use_memmove, use_secmem >::npos = std::numeric_limits<size_type>::max()

staticconstexpr

Special value representing maximal value of size_type, used to denote an invalid index position return value, i.e.

no position.

Definition at line 76 of file darray_sorted.hpp.

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

include/jau/darray_sorted.hpp

Public Types

Public Member Functions

Static Public Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ darray_type

◆ value_type

◆ size_type

Member Enumeration Documentation

◆ order_t

Constructor & Destructor Documentation

◆ darray_sorted() [1/2]

◆ darray_sorted() [2/2]

Member Function Documentation

◆ operator=()

◆ insert()

◆ contains()

◆ index_of()

◆ erase() [1/4]

◆ erase() [2/4]

◆ erase() [3/4]

◆ erase() [4/4]

◆ size()

Member Data Documentation

◆ npos