sparrow::run_end_encoded_array Class Reference

A run-end encoded array. More...

#include <run_end_encoded_array.hpp>

Public Types
using	self_type = run_end_encoded_array
using	size_type = std::size_t
using	inner_value_type = array_traits::inner_value_type
using	value_type = array_traits::value_type
using	reference = run_end_encoded_reference
using	const_reference = array_traits::const_reference
using	iterator = run_encoded_array_iterator<false>
using	const_iterator = run_encoded_array_iterator<true>
using	reverse_iterator = std::reverse_iterator<iterator>
using	const_reverse_iterator = std::reverse_iterator<const_iterator>

Public Member Functions
SPARROW_API	run_end_encoded_array (arrow_proxy proxy)
	Constructs run-end encoded array from Arrow proxy.
template<class... Args> requires (mpl::excludes_copy_and_move_ctor_v<run_end_encoded_array, Args...>)
	run_end_encoded_array (Args &&... args)
	Generic constructor for creating run-end encoded array.
SPARROW_API	run_end_encoded_array (const self_type &)
	Copy constructor.
SPARROW_API self_type &	operator= (const self_type &)
	Copy assignment operator.
	~run_end_encoded_array ()=default
	run_end_encoded_array (self_type &&)=default
self_type &	operator= (self_type &&)=default
SPARROW_API reference	operator[] (std::uint64_t i)
	Mutable access operator for updating the logical value at index.
SPARROW_API array_traits::const_reference	operator[] (std::uint64_t i) const
	Constant access operator for getting element at index.
SPARROW_API iterator	begin ()
	Gets an iterator to the beginning of the array.
SPARROW_API iterator	end ()
	Gets an iterator to the end of the array.
SPARROW_API const_iterator	begin () const
	Gets a constant iterator to the beginning of the array.
SPARROW_API const_iterator	end () const
	Gets a constant iterator to the end of the array.
SPARROW_API const_iterator	cbegin () const
	Gets a constant iterator to the beginning of the array.
SPARROW_API const_iterator	cend () const
	Gets a constant iterator to the end of the array.
SPARROW_API reverse_iterator	rbegin ()
	Gets a reverse iterator to the beginning of the reversed array.
SPARROW_API reverse_iterator	rend ()
	Gets a reverse iterator to the end of the reversed array.
SPARROW_API const_reverse_iterator	rbegin () const
	Gets a constant reverse iterator to the beginning of reversed the array.
SPARROW_API const_reverse_iterator	rend () const
	Gets a constant reverse iterator to the end of the reversed array.
SPARROW_API const_reverse_iterator	crbegin () const
	Gets a constant reverse iterator to the beginning of reversed the array.
SPARROW_API const_reverse_iterator	crend () const
	Gets a constant reverse iterator to the end of the reversed array.
SPARROW_API reference	front ()
	Gets a mutable reference to the first element.
SPARROW_API array_traits::const_reference	front () const
	Gets a constant reference to the first element.
SPARROW_API reference	back ()
	Gets a mutable reference to the last element.
SPARROW_API array_traits::const_reference	back () const
	Gets a reference to the last element.
SPARROW_API iterator	insert (const_iterator pos, const value_type &value)
	Inserts a single logical value before pos.
SPARROW_API iterator	insert (const_iterator pos, const value_type &value, size_type count)
	Inserts count copies of value before pos.
template<std::input_iterator InputIt> requires std::constructible_from<value_type, typename std::iterator_traits<InputIt>::value_type>
iterator	insert (const_iterator pos, InputIt first, InputIt last)
template<std::ranges::input_range R> requires std::constructible_from<value_type, std::ranges::range_value_t<R>>
iterator	insert (const_iterator pos, R &&range)
SPARROW_API iterator	erase (const_iterator pos)
	Erases the logical value at pos.
SPARROW_API iterator	erase (const_iterator first, const_iterator last)
	Erases the logical range [first, last).
SPARROW_API void	push_back (const value_type &value)
SPARROW_API void	pop_back ()
SPARROW_API void	resize (size_type new_length, const value_type &value)
SPARROW_API void	clear ()
SPARROW_API bool	empty () const
	Checks if the array is empty.
SPARROW_API size_type	size () const
	Gets the number of elements in the array.
std::optional< std::string_view >	name () const
	Gets the name of the array.
std::optional< key_value_view >	metadata () const
	Gets the metadata of the array.

Friends
class	run_encoded_array_iterator< false >
class	run_encoded_array_iterator< true >
class	run_end_encoded_reference
class	detail::array_access

Detailed Description

A run-end encoded array.

To use for data with long runs of identical values

This array is used to store data in a run-length encoded format, where each run is represented by a length and a value. Compresses data by storing run lengths for consecutive identical values.

Performance notes:

• Random access is $O(\log R)$ where $R$ is the number of encoded runs.
• Iterator increment is amortized $O(1)$ because iterators cache the current run.
• Mutating operations work on the encoded run representation rather than the full logical length. Inserting repeated copies of a single value and erasing a contiguous logical range both run in $O(R_t)$, where $R_t$ is the number of encoded runs at or after the splice point.
• Sliced arrays (non-zero offset) are read-only for mutation APIs.

Related Apache Arrow description and specification:

• https://arrow.apache.org/docs/dev/format/Intro.html#run-end-encoded-layout
• https://arrow.apache.org/docs/format/Columnar.html#run-end-encoded-layout

Definition at line 100 of file run_end_encoded_array.hpp.

Member Typedef Documentation

const_iterator

using sparrow::run_end_encoded_array::const_iterator = run_encoded_array_iterator<true>

Definition at line 111 of file run_end_encoded_array.hpp.

const_reference

using sparrow::run_end_encoded_array::const_reference = array_traits::const_reference

Definition at line 109 of file run_end_encoded_array.hpp.

const_reverse_iterator

using sparrow::run_end_encoded_array::const_reverse_iterator = std::reverse_iterator<const_iterator>

Definition at line 113 of file run_end_encoded_array.hpp.

inner_value_type

using sparrow::run_end_encoded_array::inner_value_type = array_traits::inner_value_type

Definition at line 106 of file run_end_encoded_array.hpp.

iterator

using sparrow::run_end_encoded_array::iterator = run_encoded_array_iterator<false>

Definition at line 110 of file run_end_encoded_array.hpp.

reference

using sparrow::run_end_encoded_array::reference = run_end_encoded_reference

Definition at line 108 of file run_end_encoded_array.hpp.

reverse_iterator

using sparrow::run_end_encoded_array::reverse_iterator = std::reverse_iterator<iterator>

Definition at line 112 of file run_end_encoded_array.hpp.

self_type

using sparrow::run_end_encoded_array::self_type = run_end_encoded_array

Definition at line 104 of file run_end_encoded_array.hpp.

size_type

using sparrow::run_end_encoded_array::size_type = std::size_t

Definition at line 105 of file run_end_encoded_array.hpp.

value_type

using sparrow::run_end_encoded_array::value_type = array_traits::value_type

Definition at line 107 of file run_end_encoded_array.hpp.

Constructor & Destructor Documentation

run_end_encoded_array() [1/4]

SPARROW_API sparrow::run_end_encoded_array::run_end_encoded_array ( arrow_proxy proxy )

explicit

Constructs run-end encoded array from Arrow proxy.

Parameters

proxy

Arrow proxy containing run-end encoded array data and schema

Precondition

proxy must contain valid run-end encoded array and schema

proxy format must be "+r"

proxy must have two children arrays

Postcondition

Array is initialized with data from proxy

Here is the call graph for this function:

Here is the caller graph for this function:

run_end_encoded_array() [2/4]

template<class... Args>
requires (mpl::excludes_copy_and_move_ctor_v<run_end_encoded_array, Args...>)

sparrow::run_end_encoded_array::run_end_encoded_array ( Args &&... args )

inlineexplicit

Generic constructor for creating run-end encoded array.

Creates a run-end encoded array from various input types. Arguments are forwarded to compatible create_proxy() functions.

Template Parameters

Args	Parameter pack for constructor arguments

Parameters

args	Constructor arguments (data ranges, validity, metadata, etc.)

Precondition

Arguments must match one of the create_proxy() overload signatures

Postcondition

Array is created the specified data and configuration.

Definition at line 141 of file run_end_encoded_array.hpp.

run_end_encoded_array() [3/4]

SPARROW_API sparrow::run_end_encoded_array::run_end_encoded_array

(

const self_type &

)

Copy constructor.

Parameters

rhs	Source array to copy from

Precondition

rhs must be in a valid state

Postcondition

This array contains a deep copy of rhs data

Child arrays and offset pointers are reconstructed

~run_end_encoded_array()

sparrow::run_end_encoded_array::~run_end_encoded_array ( )

default

run_end_encoded_array() [4/4]

sparrow::run_end_encoded_array::run_end_encoded_array ( self_type && )

default

Member Function Documentation

back() [1/2]

SPARROW_API reference sparrow::run_end_encoded_array::back ( )

nodiscard

Gets a mutable reference to the last element.

Returns

Mutable proxy reference to the last element.

back() [2/2]

SPARROW_API array_traits::const_reference sparrow::run_end_encoded_array::back ( ) const

nodiscard

Gets a reference to the last element.

Returns

Constant reference to the last element.

begin() [1/2]

SPARROW_API iterator sparrow::run_end_encoded_array::begin ( )

nodiscard

Gets an iterator to the beginning of the array.

Returns

Iterator to the beginning.

Here is the caller graph for this function:

begin() [2/2]

SPARROW_API const_iterator sparrow::run_end_encoded_array::begin ( ) const

nodiscard

Gets a constant iterator to the beginning of the array.

Returns

Constant iterator to the beginning.

cbegin()

SPARROW_API const_iterator sparrow::run_end_encoded_array::cbegin ( ) const

nodiscard

Gets a constant iterator to the beginning of the array.

Returns

Constant iterator to the beginning.

Here is the caller graph for this function:

cend()

SPARROW_API const_iterator sparrow::run_end_encoded_array::cend ( ) const

nodiscard

Gets a constant iterator to the end of the array.

Returns

Constant iterator to the end.

clear()

SPARROW_API void sparrow::run_end_encoded_array::clear

(

)

crbegin()

SPARROW_API const_reverse_iterator sparrow::run_end_encoded_array::crbegin ( ) const

nodiscard

Gets a constant reverse iterator to the beginning of reversed the array.

Returns

Constant reverse iterator to the beginning.

crend()

SPARROW_API const_reverse_iterator sparrow::run_end_encoded_array::crend ( ) const

nodiscard

Gets a constant reverse iterator to the end of the reversed array.

Returns

Constant reverse iterator to the end.

empty()

SPARROW_API bool sparrow::run_end_encoded_array::empty ( ) const

nodiscard

Checks if the array is empty.

Returns

true if the array is empty, false otherwise.

end() [1/2]

SPARROW_API iterator sparrow::run_end_encoded_array::end ( )

nodiscard

Gets an iterator to the end of the array.

Returns

Iterator to the end.

end() [2/2]

SPARROW_API const_iterator sparrow::run_end_encoded_array::end ( ) const

nodiscard

Gets a constant iterator to the end of the array.

Returns

Constant iterator to the end.

erase() [1/2]

SPARROW_API iterator sparrow::run_end_encoded_array::erase	(	const_iterator	first,
		const_iterator	last )

Erases the logical range [first, last).

This is implemented as a single structural mutation on the encoded runs, rather than repeating single-element erases.

Complexity: $O(R_t)$ where $R_t$ is the number of encoded runs touched by, or after, the erased range.

erase() [2/2]

SPARROW_API iterator sparrow::run_end_encoded_array::erase

(

const_iterator

pos

)

Erases the logical value at pos.

Complexity: $O(R_t)$ where $R_t$ is the number of encoded runs touched by, or after, pos.

front() [1/2]

SPARROW_API reference sparrow::run_end_encoded_array::front ( )

nodiscard

Gets a mutable reference to the first element.

Returns

Mutable proxy reference to the first element.

front() [2/2]

SPARROW_API array_traits::const_reference sparrow::run_end_encoded_array::front ( ) const

nodiscard

Gets a constant reference to the first element.

Returns

Constant reference to the first element.

insert() [1/4]

SPARROW_API iterator sparrow::run_end_encoded_array::insert	(	const_iterator	pos,
		const value_type &	value )

Inserts a single logical value before pos.

Complexity: $O(R_t)$ where $R_t$ is the number of encoded runs at or after pos.

Here is the caller graph for this function:

insert() [2/4]

SPARROW_API iterator sparrow::run_end_encoded_array::insert	(	const_iterator	pos,
		const value_type &	value,
		size_type	count )

Inserts count copies of value before pos.

This is implemented as a single structural mutation on the encoded runs, rather than repeating single-element inserts.

Complexity: $O(R_t)$ where $R_t$ is the number of encoded runs at or after pos.

insert() [3/4]

template<std::input_iterator InputIt>
requires std::constructible_from<value_type, typename std::iterator_traits<InputIt>::value_type>

iterator sparrow::run_end_encoded_array::insert ( const_iterator pos, InputIt first, InputIt last )

inline

Definition at line 322 of file run_end_encoded_array.hpp.

Here is the call graph for this function:

insert() [4/4]

template<std::ranges::input_range R>
requires std::constructible_from<value_type, std::ranges::range_value_t<R>>

iterator sparrow::run_end_encoded_array::insert ( const_iterator pos, R && range )

inline

Definition at line 338 of file run_end_encoded_array.hpp.

Here is the call graph for this function:

metadata()

std::optional< key_value_view > sparrow::run_end_encoded_array::metadata ( ) const

nodiscard

Gets the metadata of the array.

Returns

Optional metadata of the array.

Here is the call graph for this function:

Here is the caller graph for this function:

name()

std::optional< std::string_view > sparrow::run_end_encoded_array::name ( ) const

nodiscard

Gets the name of the array.

Returns

Optional name of the array.

Here is the caller graph for this function:

operator=() [1/2]

SPARROW_API self_type & sparrow::run_end_encoded_array::operator=

(

const self_type &

)

Copy assignment operator.

Parameters

rhs	Source array to copy from

Returns

Reference to this array

Precondition

rhs must be in a valid state

Postcondition

This array contains a deep copy of rhs data

Previous data is properly released

Child arrays and offset pointers are reconstructed

operator=() [2/2]

self_type & sparrow::run_end_encoded_array::operator= ( self_type && )

default

operator[]() [1/2]

SPARROW_API reference sparrow::run_end_encoded_array::operator[] ( std::uint64_t i )

nodiscard

Mutable access operator for updating the logical value at index.

Parameters

i	The index of the element to access.

Returns

Mutable proxy reference to the element at the specified index.

operator[]() [2/2]

SPARROW_API array_traits::const_reference sparrow::run_end_encoded_array::operator[] ( std::uint64_t i ) const

nodiscard

Constant access operator for getting element at index.

Parameters

i	The index of the element to access.

Returns

Constant reference to the element at the specified index.

pop_back()

SPARROW_API void sparrow::run_end_encoded_array::pop_back

(

)

push_back()

SPARROW_API void sparrow::run_end_encoded_array::push_back

(

const value_type &

value

)

rbegin() [1/2]

SPARROW_API reverse_iterator sparrow::run_end_encoded_array::rbegin ( )

nodiscard

Gets a reverse iterator to the beginning of the reversed array.

Returns

Reverse iterator to the beginning.

rbegin() [2/2]

SPARROW_API const_reverse_iterator sparrow::run_end_encoded_array::rbegin ( ) const

nodiscard

Gets a constant reverse iterator to the beginning of reversed the array.

Returns

Constant reverse iterator to the beginning.

rend() [1/2]

SPARROW_API reverse_iterator sparrow::run_end_encoded_array::rend ( )

nodiscard

Gets a reverse iterator to the end of the reversed array.

Returns

Reverse iterator to the end.

rend() [2/2]

SPARROW_API const_reverse_iterator sparrow::run_end_encoded_array::rend ( ) const

nodiscard

Gets a constant reverse iterator to the end of the reversed array.

Returns

Constant reverse iterator to the end.

resize()

SPARROW_API void sparrow::run_end_encoded_array::resize	(	size_type	new_length,
		const value_type &	value )

size()

SPARROW_API size_type sparrow::run_end_encoded_array::size ( ) const

nodiscard

Gets the number of elements in the array.

Returns

The number of elements.

Friends And Related Symbol Documentation

detail::array_access

friend class detail::array_access

friend

Definition at line 533 of file run_end_encoded_array.hpp.

run_encoded_array_iterator< false >

friend class run_encoded_array_iterator< false >

friend

Definition at line 527 of file run_end_encoded_array.hpp.

run_encoded_array_iterator< true >

friend class run_encoded_array_iterator< true >

friend

Definition at line 527 of file run_end_encoded_array.hpp.

run_end_encoded_reference

friend class run_end_encoded_reference

friend

Definition at line 532 of file run_end_encoded_array.hpp.

---

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

• sparrow/run_end_encoded_array.hpp