fix8  version 1.4.0
Open Source C++ FIX Framework
FIX8::presorted_set< K, T, Comp > Class Template Reference

#include <f8types.hpp>

Public Types

using iterator = T *
 
using const_iterator = const T *
 
using result = std::pair< iterator, bool >
 

Public Member Functions

 presorted_set (const_iterator arr_start, const size_t sz, const size_t reserve=FIX8_RESERVE_PERCENT)
 
 presorted_set (const presorted_set &from)
 
 presorted_set (const size_t sz=0, const size_t reserve=FIX8_RESERVE_PERCENT)
 
 ~presorted_set ()
 dtor More...
 
iterator find (const T what, bool &answer)
 
iterator find (const K key, bool &answer)
 
const_iterator find (const K key) const
 
const_iterator find (const T what) const
 
iterator find (const K key)
 
iterator find (const T what)
 
const_iterator at (const size_t idx) const
 
result insert (const_iterator what)
 
void insert (const_iterator what_begin, const_iterator what_end)
 
void clear ()
 
size_t size () const
 
bool empty () const
 
size_t rsize () const
 
iterator begin ()
 
iterator end ()
 
const_iterator begin () const
 
const_iterator end () const
 

Static Public Member Functions

static size_t distance (const_iterator what_begin, const_iterator what_end)
 

Private Types

using internal_result = std::pair< iterator, iterator >
 
using const_internal_result = std::pair< const_iterator, const_iterator >
 

Static Private Member Functions

static size_t calc_reserve (size_t sz, size_t res)
 

Private Attributes

const size_t _reserve
 
size_t _sz
 
size_t _rsz
 
T * _arr
 

Detailed Description

template<typename K, typename T, typename Comp>
class FIX8::presorted_set< K, T, Comp >

Presorted set designed for infrequent insertions but super fast initialisation from a sorted static array. Search complexity is O(logN), ctor complexity approaches O(1), insert is O(N).

Template Parameters
Kthe key
Tthe value type
Compthe comparitor

Definition at line 186 of file f8types.hpp.

Member Typedef Documentation

template<typename K , typename T , typename Comp >
using FIX8::presorted_set< K, T, Comp >::const_internal_result = std::pair<const_iterator, const_iterator>
private

Definition at line 199 of file f8types.hpp.

template<typename K , typename T , typename Comp >
using FIX8::presorted_set< K, T, Comp >::const_iterator = const T*

Definition at line 190 of file f8types.hpp.

template<typename K , typename T , typename Comp >
using FIX8::presorted_set< K, T, Comp >::internal_result = std::pair<iterator, iterator>
private

Definition at line 198 of file f8types.hpp.

template<typename K , typename T , typename Comp >
using FIX8::presorted_set< K, T, Comp >::iterator = T*

Definition at line 189 of file f8types.hpp.

template<typename K , typename T , typename Comp >
using FIX8::presorted_set< K, T, Comp >::result = std::pair<iterator, bool>

Definition at line 191 of file f8types.hpp.

Constructor & Destructor Documentation

template<typename K , typename T , typename Comp >
FIX8::presorted_set< K, T, Comp >::presorted_set ( const_iterator  arr_start,
const size_t  sz,
const size_t  reserve = FIX8_RESERVE_PERCENT 
)
inline

ctor - initialise from static sorted set

Parameters
arr_startpointer to start of static array to copy elements from
sznumber of elements in set to copy
reservepercentage of sz to keep in reserve

Definition at line 218 of file f8types.hpp.

218  : _reserve(reserve),
219  _sz(sz), _rsz(_sz + calc_reserve(_sz, _reserve)), _arr(new T[_rsz])
220  { memcpy(_arr, arr_start, _sz * sizeof(T)); }
static size_t calc_reserve(size_t sz, size_t res)
Definition: f8types.hpp:205
const size_t _reserve
Definition: f8types.hpp:194
template<typename K , typename T , typename Comp >
FIX8::presorted_set< K, T, Comp >::presorted_set ( const presorted_set< K, T, Comp > &  from)
inline

copy ctor

Parameters
frompresorted_set object to copy

Definition at line 224 of file f8types.hpp.

References FIX8::presorted_set< K, T, Comp >::_arr.

224  : _reserve(from._reserve),
225  _sz(from._sz), _rsz(from._rsz), _arr(from._arr ? new T[_rsz] : 0)
226  { if (_arr) memcpy(_arr, from._arr, _sz * sizeof(T)); }
const size_t _reserve
Definition: f8types.hpp:194
template<typename K , typename T , typename Comp >
FIX8::presorted_set< K, T, Comp >::presorted_set ( const size_t  sz = 0,
const size_t  reserve = FIX8_RESERVE_PERCENT 
)
inlineexplicit

ctor - initialise an empty set; defer memory allocation;

Parameters
sznumber of elements to initially allocate
reservepercentage of sz to keep in reserve

Definition at line 231 of file f8types.hpp.

231  : _reserve(reserve),
232  _sz(sz), _rsz(_sz + calc_reserve(_sz, _reserve)), _arr() {}
static size_t calc_reserve(size_t sz, size_t res)
Definition: f8types.hpp:205
const size_t _reserve
Definition: f8types.hpp:194
template<typename K , typename T , typename Comp >
FIX8::presorted_set< K, T, Comp >::~presorted_set ( )
inline

dtor

Definition at line 235 of file f8types.hpp.

References FIX8::presorted_set< K, T, Comp >::_arr.

235 { delete[] _arr; }

Member Function Documentation

template<typename K , typename T , typename Comp >
const_iterator FIX8::presorted_set< K, T, Comp >::at ( const size_t  idx) const
inline

Get the element at index location

Parameters
idxof the pair to retrieve
Returns
const_iterator to element or end() if not found

Definition at line 285 of file f8types.hpp.

References FIX8::presorted_set< K, T, Comp >::end().

285 { return idx < _sz ? _arr + idx : end(); }
iterator end()
Definition: f8types.hpp:363
template<typename K , typename T , typename Comp >
iterator FIX8::presorted_set< K, T, Comp >::begin ( )
inline

Get a pointer to the first element

Returns
the first element

Definition at line 359 of file f8types.hpp.

References FIX8::presorted_set< K, T, Comp >::_arr.

359 { return _arr; }
template<typename K , typename T , typename Comp >
const_iterator FIX8::presorted_set< K, T, Comp >::begin ( ) const
inline

Get a const pointer to the first element

Returns
the first element

Definition at line 367 of file f8types.hpp.

References FIX8::presorted_set< K, T, Comp >::_arr.

367 { return _arr; }
template<typename K , typename T , typename Comp >
static size_t FIX8::presorted_set< K, T, Comp >::calc_reserve ( size_t  sz,
size_t  res 
)
inlinestaticprivate

Calculate the amount of space to reserve in set

Parameters
sznumber of elements currently in set; if 0 retun reserve elements as size to reserve
respercentage of sz to keep in reserve
Returns
number of elements to additionally reserve (at least 1)

Definition at line 205 of file f8types.hpp.

Referenced by FIX8::presorted_set< K, T, Comp >::insert(), and FIX8::presorted_set< unsigned short, FieldTrait, FieldTrait::Compare >::insert().

206  {
207  if (!sz) // special case - reserve means number to reserve, not %
208  return res;
209  const size_t val(sz * res / 100);
210  return val ? val : 1;
211  }
template<typename K , typename T , typename Comp >
void FIX8::presorted_set< K, T, Comp >::clear ( )
inline

Clear the set (does not delete)

Definition at line 343 of file f8types.hpp.

343 { _sz = 0; }
template<typename K , typename T , typename Comp >
static size_t FIX8::presorted_set< K, T, Comp >::distance ( const_iterator  what_begin,
const_iterator  what_end 
)
inlinestatic

Find the distance between two iterators

Parameters
what_beginstart iterator
what_endend iterator (must be >= to what_begin
Returns
distance in elements

Definition at line 329 of file f8types.hpp.

330  { return what_end - what_begin; }
template<typename K , typename T , typename Comp >
bool FIX8::presorted_set< K, T, Comp >::empty ( ) const
inline

Check if the set is empty

Returns
true if empty

Definition at line 351 of file f8types.hpp.

351 { return _sz == 0; }
template<typename K , typename T , typename Comp >
const_iterator FIX8::presorted_set< K, T, Comp >::end ( ) const
inline

Get a const pointer to the last element + 1

Returns
the last element + 1

Definition at line 371 of file f8types.hpp.

References FIX8::presorted_set< K, T, Comp >::_sz.

371 { return _arr + _sz; }
template<typename K , typename T , typename Comp >
iterator FIX8::presorted_set< K, T, Comp >::find ( const T  what,
bool &  answer 
)
inline

Find an element with the given value

Parameters
whatelement to find
answertrue if element is found
Returns
pointer to found element or pointer to location where element would be inserted

Definition at line 241 of file f8types.hpp.

Referenced by FIX8::presorted_set< K, T, Comp >::insert(), and FIX8::presorted_set< unsigned short, FieldTrait, FieldTrait::Compare >::insert().

242  {
243  const internal_result res(std::equal_range (_arr, _arr + _sz, what, Comp()));
244  answer = res.first != res.second;
245  return res.first;
246  }
std::pair< iterator, iterator > internal_result
Definition: f8types.hpp:198
template<typename K , typename T , typename Comp >
iterator FIX8::presorted_set< K, T, Comp >::find ( const K  key,
bool &  answer 
)
inline

Find an element with the given key

Parameters
keyto find
answertrue if element is found
Returns
pointer to found element or pointer to location where element would be inserted

Definition at line 252 of file f8types.hpp.

References FIX8::presorted_set< K, T, Comp >::find().

Referenced by FIX8::presorted_set< K, T, Comp >::find().

252 { return find(T(key), answer); }
iterator find(const T what, bool &answer)
Definition: f8types.hpp:241
template<typename K , typename T , typename Comp >
const_iterator FIX8::presorted_set< K, T, Comp >::find ( const K  key) const
inline

Find an element with the given key (const version)

Parameters
keyto find
Returns
pointer to found element or end()

Definition at line 257 of file f8types.hpp.

References FIX8::presorted_set< K, T, Comp >::find().

Referenced by FIX8::presorted_set< K, T, Comp >::find().

257 { return find(T(key)); }
iterator find(const T what, bool &answer)
Definition: f8types.hpp:241
template<typename K , typename T , typename Comp >
const_iterator FIX8::presorted_set< K, T, Comp >::find ( const T  what) const
inline

Find an element with the given value (const version)

Parameters
whatelement to find
Returns
pointer to found element or end()

Definition at line 262 of file f8types.hpp.

References FIX8::presorted_set< K, T, Comp >::end().

263  {
264  const const_internal_result res(std::equal_range (_arr, _arr + _sz, what, Comp()));
265  return res.first != res.second ? res.first : end();
266  }
std::pair< const_iterator, const_iterator > const_internal_result
Definition: f8types.hpp:199
iterator end()
Definition: f8types.hpp:363
template<typename K , typename T , typename Comp >
iterator FIX8::presorted_set< K, T, Comp >::find ( const K  key)
inline

Find an element with the given key

Parameters
keyto find
Returns
pointer to found element or end()

Definition at line 271 of file f8types.hpp.

References FIX8::presorted_set< K, T, Comp >::find().

Referenced by FIX8::presorted_set< K, T, Comp >::find().

271 { return find(T(key)); }
iterator find(const T what, bool &answer)
Definition: f8types.hpp:241
template<typename K , typename T , typename Comp >
iterator FIX8::presorted_set< K, T, Comp >::find ( const T  what)
inline

Find an element with the given value

Parameters
whatvalue to find
Returns
pointer to found element or end()

Definition at line 276 of file f8types.hpp.

References FIX8::presorted_set< K, T, Comp >::end().

277  {
278  internal_result res(std::equal_range (_arr, _arr + _sz, what, Comp()));
279  return res.first != res.second ? res.first : end();
280  }
std::pair< iterator, iterator > internal_result
Definition: f8types.hpp:198
iterator end()
Definition: f8types.hpp:363
template<typename K , typename T , typename Comp >
result FIX8::presorted_set< K, T, Comp >::insert ( const_iterator  what)
inline

Insert an element into the set

Parameters
whatpointer to element to insert
Returns
result with iterator to insert location and true or end() and false

Definition at line 290 of file f8types.hpp.

References FIX8::presorted_set< K, T, Comp >::_arr, FIX8::presorted_set< K, T, Comp >::_rsz, FIX8::presorted_set< K, T, Comp >::_sz, FIX8::presorted_set< K, T, Comp >::calc_reserve(), FIX8::presorted_set< K, T, Comp >::end(), and FIX8::presorted_set< K, T, Comp >::find().

Referenced by FIX8::presorted_set< K, T, Comp >::insert(), and FIX8::presorted_set< unsigned short, FieldTrait, FieldTrait::Compare >::insert().

291  {
292  if (!_sz)
293  {
294  _arr = new T[_rsz];
295  memcpy(_arr, what, sizeof(T));
296  ++_sz;
297  return result(_arr, true);
298  }
299 
300  bool answer;
301  iterator where(find(*what, answer));
302  if (answer)
303  return result(end(), false);
304 
305  if (_sz < _rsz)
306  {
307  memmove(where + 1, where, (end() - where) * sizeof(T));
308  memcpy(where, what, sizeof(T));
309  }
310  else
311  {
312  iterator new_arr(new T[_rsz = _sz + calc_reserve(_sz, _reserve)]);
313  const size_t wptr(where - _arr);
314  if (wptr > 0)
315  memcpy(new_arr, _arr, sizeof(T) * wptr);
316  memcpy(new_arr + wptr, what, sizeof(T));
317  memcpy(new_arr + wptr + 1, where, (end() - where) * sizeof(T));
318  delete[] _arr;
319  _arr = new_arr;
320  }
321  ++_sz;
322  return result(where, true);
323  }
static size_t calc_reserve(size_t sz, size_t res)
Definition: f8types.hpp:205
const size_t _reserve
Definition: f8types.hpp:194
std::pair< iterator, bool > result
Definition: f8types.hpp:191
iterator find(const T what, bool &answer)
Definition: f8types.hpp:241
iterator end()
Definition: f8types.hpp:363
template<typename K , typename T , typename Comp >
void FIX8::presorted_set< K, T, Comp >::insert ( const_iterator  what_begin,
const_iterator  what_end 
)
inline

Insert a range of elements into the set

Parameters
what_beginpointer to 1st element to insert
what_endpointer to nth element + 1 to insert

Definition at line 335 of file f8types.hpp.

References FIX8::presorted_set< K, T, Comp >::insert().

336  {
337  for (const_iterator ptr(what_begin); ptr < what_end; ++ptr)
338  if (!insert(ptr).second)
339  break;
340  }
const T * const_iterator
Definition: f8types.hpp:190
result insert(const_iterator what)
Definition: f8types.hpp:290
template<typename K , typename T , typename Comp >
size_t FIX8::presorted_set< K, T, Comp >::rsize ( ) const
inline

Obtain the number of elements that can be inserted before reallocating

Returns
reserved + sz

Definition at line 355 of file f8types.hpp.

References FIX8::presorted_set< K, T, Comp >::_rsz.

355 { return _rsz; }
template<typename K , typename T , typename Comp >
size_t FIX8::presorted_set< K, T, Comp >::size ( ) const
inline

Obtain the number of elements in the set

Returns
the number of elements

Definition at line 347 of file f8types.hpp.

References FIX8::presorted_set< K, T, Comp >::_sz.

347 { return _sz; }

Member Data Documentation

template<typename K , typename T , typename Comp >
const size_t FIX8::presorted_set< K, T, Comp >::_reserve
private

Definition at line 194 of file f8types.hpp.


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