TPIE

11a2c2d
tpie::array< T, Allocator > Class Template Reference

A generic array with a fixed size. More...

#include <tpie/array.h>

Inherits tpie::linear_memory_base< array< T > >.

Public Types

typedef array_iter_base< T const, true > const_iterator
 Iterator over a const array. More...
 
typedef array_iter_base< T const, false > const_reverse_iterator
 Reverse iterator over a const array. More...
 
typedef array_iter_base< T, true > iterator
 Iterator over an array. More...
 
typedef array_iter_base< T, false > reverse_iterator
 Reverse iterator over an array. More...
 
typedef T value_type
 Type of values containd in the array. More...
 

Public Member Functions

iterator find (size_t idx) throw ()
 Return an iterator to the i'th element of the array. More...
 
const_iterator find (size_t idx) const throw ()
 Return a const iterator to the i'th element of the array. More...
 
T & at (size_t i) throw ()
 Return the element located at the given index. More...
 
const T & at (size_t i) const throw ()
 Return the element located at the given index. More...
 
arrayoperator= (const array &other)
 Copy elements from another array into this. More...
 
arrayoperator= (array &&other)
 Move elements from another array into this. More...
 
template<typename OtherAllocator >
arrayoperator= (const array< T, OtherAllocator > &other)
 Copy elements from another array with any allocator into this. More...
 
bool empty () const
 Check if the array is empty. More...
 
const T & operator[] (size_t i) const
 Return a const reference to an array entry. More...
 
T & operator[] (size_t i)
 Return a reference to an array entry. More...
 
bool operator== (const array &other) const
 Compare if the other array has the same elements in the same order as this. More...
 
bool operator!= (const array &other) const
 Check if two arrays differ. More...
 
iterator begin ()
 Return an iterator to the beginning of the array. More...
 
const_iterator begin () const
 Return a const iterator to the beginning of the array. More...
 
iterator end ()
 Return an iterator to the end of the array. More...
 
const_iterator end () const
 Return a const iterator to the end of the array. More...
 
const T & front () const
 Return the first element in the array. More...
 
T & front ()
 Return the first element in the array. More...
 
const T & back () const
 Return the last element in the array. More...
 
T & back ()
 Return the last element in the array. More...
 
reverse_iterator rbegin ()
 Reverse iterator to beginning of reverse sequence. More...
 
const_reverse_iterator rbegin () const
 Const reverse iterator to beginning of reverse sequence. More...
 
reverse_iterator rend ()
 Reverse iterator to end of reverse sequence. More...
 
const_reverse_iterator rend () const
 Const reverse iterator to end of reverse sequence. More...
 
 array (size_type s, const T &value, const Allocator &alloc=Allocator())
 Construct array of given size. More...
 
 array (size_type s, memory_bucket_ref bucket)
 
 array (memory_bucket_ref bucket)
 
 array (size_type s=0, const Allocator &alloc=Allocator())
 Construct array of given size. More...
 
 array (const array &other)
 Construct a copy of another array. More...
 
 array (array &&other)
 Move construct from another array. More...
 
 array (const array_view_base< T > &view)
 
 array (const array_view_base< const T > &view)
 
 ~array ()
 Free up all memory used by the array. More...
 
void resize (size_t size, const T &elm)
 Change the size of the array. More...
 
void swap (array &other)
 Swap two arrays. More...
 
void resize (size_t s)
 Change the size of the array. More...
 
size_type size () const
 Return the size of the array. More...
 
T * get ()
 Return a raw pointer to the array content. More...
 
const T * get () const
 Return a raw pointer to the array content. More...
 
Allocator get_allocator () const
 Return copy of the allocator. More...
 

Static Public Member Functions

static constexpr double memory_coefficient () noexcept
 Return the memory coefficient of the structure. More...
 
static constexpr double memory_overhead () noexcept
 Return the memory overhead of the structure. More...
 
static constexpr memory_size_type memory_usage (memory_size_type size) noexcept
 Return the number of bytes required to create a data structure supporting a given number of elements. More...
 
static constexpr linear_memory_usage memory_usage () noexcept
 
static constexpr memory_size_type memory_fits (memory_size_type memory) noexcept
 Return the maximum number of elements that can be contained in in the structure when it is allowed to fill a given number of bytes. More...
 

Friends

struct bits::allocator_usage< T, Allocator >
 

Detailed Description

template<typename T, typename Allocator = allocator<T>>
class tpie::array< T, Allocator >

A generic array with a fixed size.

This is almost the same as a real C-style T array but the memory management is better.

Template Parameters
TThe type of element to contain.
alloc_tAllocator.

Definition at line 149 of file array.h.

Member Typedef Documentation

◆ const_iterator

template<typename T , typename Allocator = allocator<T>>
typedef array_iter_base<T const, true> tpie::array< T, Allocator >::const_iterator

Iterator over a const array.

Definition at line 152 of file array.h.

◆ const_reverse_iterator

template<typename T , typename Allocator = allocator<T>>
typedef array_iter_base<T const, false> tpie::array< T, Allocator >::const_reverse_iterator

Reverse iterator over a const array.

Definition at line 155 of file array.h.

◆ iterator

template<typename T , typename Allocator = allocator<T>>
typedef array_iter_base<T, true> tpie::array< T, Allocator >::iterator

Iterator over an array.

Definition at line 158 of file array.h.

◆ reverse_iterator

template<typename T , typename Allocator = allocator<T>>
typedef array_iter_base<T, false> tpie::array< T, Allocator >::reverse_iterator

Reverse iterator over an array.

Definition at line 161 of file array.h.

◆ value_type

template<typename T , typename Allocator = allocator<T>>
typedef T tpie::array< T, Allocator >::value_type

Type of values containd in the array.

Definition at line 164 of file array.h.

Constructor & Destructor Documentation

◆ array() [1/4]

template<typename T , typename Allocator = allocator<T>>
tpie::array< T, Allocator >::array ( size_type  s,
const T &  value,
const Allocator &  alloc = Allocator() 
)
inline

Construct array of given size.

Parameters
sThe number of elements in the array.
valueEach entry of the array is initialized with this value.

Definition at line 413 of file array.h.

415  : m_elements(0), m_size(0), m_tss_used(false), m_allocator(alloc)
416  {resize(s, value);}

Referenced by tpie::array< tpie::file_stream< element_type > >::memory_overhead().

◆ array() [2/4]

template<typename T , typename Allocator = allocator<T>>
tpie::array< T, Allocator >::array ( size_type  s = 0,
const Allocator &  alloc = Allocator() 
)
inline

Construct array of given size.

Parameters
sThe number of elements in the array.

Definition at line 430 of file array.h.

431  : m_elements(0), m_size(0), m_tss_used(false),
432  m_allocator(alloc) {resize(s);}

◆ array() [3/4]

template<typename T , typename Allocator = allocator<T>>
tpie::array< T, Allocator >::array ( const array< T, Allocator > &  other)
inline

Construct a copy of another array.

Parameters
otherThe array to copy.

Definition at line 438 of file array.h.

438  : m_elements(0), m_size(other.m_size), m_tss_used(false), m_allocator(other.m_allocator) {
439  if (other.size() == 0) return;
440  alloc_copy(other.m_elements);
441  }

◆ array() [4/4]

template<typename T , typename Allocator = allocator<T>>
tpie::array< T, Allocator >::array ( array< T, Allocator > &&  other)
inline

Move construct from another array.

Parameters
otherThe array to move.

Definition at line 447 of file array.h.

448  : m_elements(other.m_elements)
449  , m_size(other.m_size)
450  , m_tss_used(other.m_tss_used)
451  , m_allocator(other.m_allocator) {
452  other.m_elements = nullptr;
453  other.m_size = 0;
454  other.m_tss_used = false;
455  }

◆ ~array()

template<typename T , typename Allocator = allocator<T>>
tpie::array< T, Allocator >::~array ( )
inline

Free up all memory used by the array.

Definition at line 478 of file array.h.

478 {resize(0);}

Member Function Documentation

◆ at() [1/2]

template<typename T , typename Allocator = allocator<T>>
T& tpie::array< T, Allocator >::at ( size_t  i)
throw (
)
inline

Return the element located at the given index.

Parameters
iThe index of the element returned.

Definition at line 193 of file array.h.

193  {
194  assert(i < size());
195  return m_elements[i];
196  }

Referenced by tpie::array< tpie::file_stream< element_type > >::back(), tpie::array< tpie::file_stream< element_type > >::front(), and tpie::array< tpie::file_stream< element_type > >::operator[]().

◆ at() [2/2]

template<typename T , typename Allocator = allocator<T>>
const T& tpie::array< T, Allocator >::at ( size_t  i) const
throw (
)
inline

Return the element located at the given index.

Parameters
iThe index of the element returned.

Definition at line 201 of file array.h.

201  {
202  assert(i < size());
203  return m_elements[i];
204  }

◆ back() [1/2]

template<typename T , typename Allocator = allocator<T>>
T& tpie::array< T, Allocator >::back ( )
inline

Return the last element in the array.

Definition at line 353 of file array.h.

353 {return at(size()-1);}

◆ back() [2/2]

template<typename T , typename Allocator = allocator<T>>
const T& tpie::array< T, Allocator >::back ( ) const
inline

Return the last element in the array.

Definition at line 348 of file array.h.

348 {return at(size()-1);}

◆ begin() [1/2]

◆ begin() [2/2]

template<typename T , typename Allocator = allocator<T>>
const_iterator tpie::array< T, Allocator >::begin ( ) const
inline

Return a const iterator to the beginning of the array.

Returns
A const iterator to the beginning of the array.

Definition at line 319 of file array.h.

319 {return get_iter(0);}

◆ empty()

template<typename T , typename Allocator = allocator<T>>
bool tpie::array< T, Allocator >::empty ( ) const
inline

Check if the array is empty.

Returns
True if and only if size is 0.

Definition at line 258 of file array.h.

258 {return size() == 0;}

◆ end() [1/2]

template<typename T , typename Allocator = allocator<T>>
iterator tpie::array< T, Allocator >::end ( )
inline

Return an iterator to the end of the array.

Returns
An iterator to the end of the array.

Definition at line 326 of file array.h.

326 {return get_iter(size());}

Referenced by tpie::disjoint_sets< value_t >::clear(), tpie::serialize(), and tpie::unserialize().

◆ end() [2/2]

template<typename T , typename Allocator = allocator<T>>
const_iterator tpie::array< T, Allocator >::end ( ) const
inline

Return a const iterator to the end of the array.

Returns
A const iterator to the end of the array.

Definition at line 333 of file array.h.

333 {return get_iter(size());}

◆ find() [1/2]

template<typename T , typename Allocator = allocator<T>>
iterator tpie::array< T, Allocator >::find ( size_t  idx)
throw (
)
inline

Return an iterator to the i'th element of the array.

Parameters
idxThe index of the element we want an iterator to.
Returns
An iterator to the i'th element.

Definition at line 172 of file array.h.

172  {
173  assert(idx <= size());
174  return get_iter(idx);
175  }

Referenced by tpie::internal_vector< T >::end(), tpie::internal_priority_queue< tpie::ami::heap_ptr< REC >, comp >::insert(), tpie::internal_priority_queue< tpie::ami::heap_ptr< REC >, comp >::make_safe(), tpie::internal_priority_queue< tpie::ami::heap_ptr< REC >, comp >::pop(), tpie::internal_priority_queue< tpie::ami::heap_ptr< REC >, comp >::pop_and_push(), and tpie::internal_priority_queue< tpie::ami::heap_ptr< REC >, comp >::push().

◆ find() [2/2]

template<typename T , typename Allocator = allocator<T>>
const_iterator tpie::array< T, Allocator >::find ( size_t  idx) const
throw (
)
inline

Return a const iterator to the i'th element of the array.

Parameters
idxThe index of the element we want an iterator to.
Returns
A const iterator to the i'th element.

Definition at line 183 of file array.h.

183  {
184  assert(idx <= size());
185  return get_iter(idx);
186  }

◆ front() [1/2]

template<typename T , typename Allocator = allocator<T>>
T& tpie::array< T, Allocator >::front ( )
inline

Return the first element in the array.

Definition at line 343 of file array.h.

343 {return at(0);}

◆ front() [2/2]

template<typename T , typename Allocator = allocator<T>>
const T& tpie::array< T, Allocator >::front ( ) const
inline

Return the first element in the array.

Definition at line 338 of file array.h.

338 {return at(0);}

◆ get() [1/2]

template<typename T , typename Allocator = allocator<T>>
T* tpie::array< T, Allocator >::get ( )
inline

Return a raw pointer to the array content.

Definition at line 536 of file array.h.

536 {return m_elements;}

Referenced by tpie::compressor_buffer::get(), and tpie::bits::serialization_reader_base::read().

◆ get() [2/2]

template<typename T , typename Allocator = allocator<T>>
const T* tpie::array< T, Allocator >::get ( ) const
inline

Return a raw pointer to the array content.

Definition at line 541 of file array.h.

541 {return m_elements;}

◆ get_allocator()

template<typename T , typename Allocator = allocator<T>>
Allocator tpie::array< T, Allocator >::get_allocator ( ) const
inline

Return copy of the allocator.

Definition at line 546 of file array.h.

546 {return m_allocator;}

◆ memory_coefficient()

template<typename T , typename Allocator = allocator<T>>
static constexpr double tpie::array< T, Allocator >::memory_coefficient ( )
inlinestaticconstexprnoexcept

Return the memory coefficient of the structure.

Allocating a structure with n elements will use at most \( \lfloor \mathrm{memory\_coefficient} \cdot n + \mathrm{memory\_overhead} \rfloor \) bytes. This does not include memory overhead incurred if the structure is allocated using new.

Returns
The memory coefficient of the structure.

Definition at line 398 of file array.h.

398  {
399  return (double)sizeof(T);
400  }

Referenced by tpie::internal_queue< item_type >::memory_coefficient(), tpie::internal_stack_vector_base< T, internal_stack< T > >::memory_coefficient(), tpie::disjoint_sets< value_t >::memory_coefficient(), and tpie::internal_priority_queue< tpie::ami::heap_ptr< REC >, comp >::memory_coefficient().

◆ memory_fits()

static constexpr memory_size_type tpie::linear_memory_base< array< T > >::memory_fits ( memory_size_type  memory)
inlinestaticconstexprnoexceptinherited

Return the maximum number of elements that can be contained in in the structure when it is allowed to fill a given number of bytes.

Parameters
memoryThe number of bytes the structure is allowed to occupy
Returns
The number of elements that will fit in the structure

Definition at line 118 of file util.h.

118  {
119  return static_cast<memory_size_type>(
120  floor((memory - child_t::memory_overhead()) / child_t::memory_coefficient()));
121  }

◆ memory_overhead()

template<typename T , typename Allocator = allocator<T>>
static constexpr double tpie::array< T, Allocator >::memory_overhead ( )
inlinestaticconstexprnoexcept

◆ memory_usage()

static constexpr memory_size_type tpie::linear_memory_base< array< T > >::memory_usage ( memory_size_type  size)
inlinestaticconstexprnoexceptinherited

Return the number of bytes required to create a data structure supporting a given number of elements.

Parameters
sizeThe number of elements to support
Returns
The amount of memory required in bytes

Definition at line 106 of file util.h.

106  {
107  return static_cast<memory_size_type>(
108  floor(static_cast<double>(size) * child_t::memory_coefficient() + child_t::memory_overhead()));
109  }

◆ operator!=()

template<typename T , typename Allocator = allocator<T>>
bool tpie::array< T, Allocator >::operator!= ( const array< T, Allocator > &  other) const
inline

Check if two arrays differ.

Parameters
otherThe array to compare against.
Returns
False if they are equal; otherwise true.

Definition at line 301 of file array.h.

301  {
302  if (size() != other.size()) return true;
303  for (size_t i=0; i<size(); ++i) if (*get_iter(i) != *other.get_iter(i)) return true;
304  return false;
305  }

◆ operator=() [1/3]

template<typename T , typename Allocator = allocator<T>>
array& tpie::array< T, Allocator >::operator= ( array< T, Allocator > &&  other)
inline

Move elements from another array into this.

Note: This array is resized to the size of other.

Parameters
otherThe array to copy from.
Returns
A reference to this array.

Definition at line 228 of file array.h.

228  {
229  resize(0);
230  std::swap(m_allocator, other.m_allocator);
231  std::swap(m_elements, other.m_elements);
232  std::swap(m_size, other.m_size);
233  std::swap(m_tss_used, other.m_tss_used);
234  return *this;
235  }

◆ operator=() [2/3]

template<typename T , typename Allocator = allocator<T>>
array& tpie::array< T, Allocator >::operator= ( const array< T, Allocator > &  other)
inline

Copy elements from another array into this.

Note: This array is resized to the size of other.

Parameters
otherThe array to copy from.
Returns
A reference to this array.

Definition at line 214 of file array.h.

214  {
215  resize(other.size());
216  for (size_t i=0; i < size(); ++i) m_elements[i] = other[i];
217  return *this;
218  }

◆ operator=() [3/3]

template<typename T , typename Allocator = allocator<T>>
template<typename OtherAllocator >
array& tpie::array< T, Allocator >::operator= ( const array< T, OtherAllocator > &  other)
inline

Copy elements from another array with any allocator into this.

Note: This array is resized to the size of other.

Parameters
otherThe array to copy from.
Template Parameters
OtherAllocatorThe allocator used by the other array.
Returns
A reference to this array.

Definition at line 247 of file array.h.

247  {
248  resize(other.size());
249  for (size_t i=0; i < size(); ++i) m_elements[i] = other[i];
250  return *this;
251  }

◆ operator==()

template<typename T , typename Allocator = allocator<T>>
bool tpie::array< T, Allocator >::operator== ( const array< T, Allocator > &  other) const
inline

Compare if the other array has the same elements in the same order as this.

Parameters
otherThe array to compare against.
Returns
True if they are equal otherwise false.

Definition at line 289 of file array.h.

289  {
290  if (size() != other.size()) return false;
291  for (size_t i=0;i<size();++i) if (*get_iter(i) != *other.get_iter(i)) return false;
292  return true;
293  }

◆ operator[]() [1/2]

template<typename T , typename Allocator = allocator<T>>
T& tpie::array< T, Allocator >::operator[] ( size_t  i)
inline

Return a reference to an array entry.

Parameters
iThe index of the entry to return.
Returns
Reference to the entry.

Definition at line 277 of file array.h.

277  {
278  assert(i < size());
279  return at(i);
280  }

◆ operator[]() [2/2]

template<typename T , typename Allocator = allocator<T>>
const T& tpie::array< T, Allocator >::operator[] ( size_t  i) const
inline

Return a const reference to an array entry.

Parameters
iThe index of the entry to return.
Returns
Const reference to the entry.

Definition at line 266 of file array.h.

266  {
267  assert(i < size());
268  return at(i);
269  }

◆ rbegin() [1/2]

template<typename T , typename Allocator = allocator<T>>
reverse_iterator tpie::array< T, Allocator >::rbegin ( )
inline

Reverse iterator to beginning of reverse sequence.

Definition at line 358 of file array.h.

358 {return get_rev_iter(0);}

◆ rbegin() [2/2]

template<typename T , typename Allocator = allocator<T>>
const_reverse_iterator tpie::array< T, Allocator >::rbegin ( ) const
inline

Const reverse iterator to beginning of reverse sequence.

Definition at line 363 of file array.h.

363 {return get_rev_iter(0);}

◆ rend() [1/2]

template<typename T , typename Allocator = allocator<T>>
reverse_iterator tpie::array< T, Allocator >::rend ( )
inline

Reverse iterator to end of reverse sequence.

Definition at line 368 of file array.h.

368 {return get_rev_iter(size());}

◆ rend() [2/2]

template<typename T , typename Allocator = allocator<T>>
const_reverse_iterator tpie::array< T, Allocator >::rend ( ) const
inline

Const reverse iterator to end of reverse sequence.

Definition at line 373 of file array.h.

373 {return get_rev_iter(size());}

◆ resize() [1/2]

template<typename T , typename Allocator = allocator<T>>
void tpie::array< T, Allocator >::resize ( size_t  s)
inline

Change the size of the array.

All elements are lost.

Memory manager MUST be initialized at this point unless s == 0.

Parameters
sThe new size of the array.

Definition at line 520 of file array.h.

520  {
521  destruct_and_dealloc();
522  m_size = s;
523  alloc_dfl();
524  }

◆ resize() [2/2]

template<typename T , typename Allocator = allocator<T>>
void tpie::array< T, Allocator >::resize ( size_t  size,
const T &  elm 
)
inline

◆ size()

◆ swap()

template<typename T , typename Allocator = allocator<T>>
void tpie::array< T, Allocator >::swap ( array< T, Allocator > &  other)
inline

Swap two arrays.

Definition at line 504 of file array.h.

504  {
505  std::swap(m_allocator, other.m_allocator);
506  std::swap(m_elements, other.m_elements);
507  std::swap(m_size, other.m_size);
508  std::swap(m_tss_used, other.m_tss_used);
509  }

Referenced by tpie::merge_sorter< T, UseProgress, pred_t, store_t >::end(), and std::swap().


The documentation for this class was generated from the following file:
tpie::array::array
array(size_type s, const T &value, const Allocator &alloc=Allocator())
Construct array of given size.
Definition: array.h:413
tpie::array::at
T & at(size_t i)
Return the element located at the given index.
Definition: array.h:193
tpie::array::resize
void resize(size_t size, const T &elm)
Change the size of the array.
Definition: array.h:490
std::swap
void swap(tpie::uncompressed_stream< T > &a, tpie::uncompressed_stream< T > &b)
Enable std::swapping two tpie::file_streams.
Definition: uncompressed_stream.h:182
tpie::array::size
size_type size() const
Return the size of the array.
Definition: array.h:531