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

K	the key
T	the value type
Comp	the 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_start	pointer to start of static array to copy elements from
sz	number of elements in set to copy
reserve	percentage of sz to keep in reserve

Definition at line 218 of file f8types.hpp.

                                                                                                       : _reserve(reserve),
      _sz(sz), _rsz(_sz + calc_reserve(_sz, _reserve)), _arr(new T[_rsz])
         { memcpy(_arr, arr_start, _sz * sizeof(T)); }

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

from	presorted_set object to copy

Definition at line 224 of file f8types.hpp.

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

                                            : _reserve(from._reserve),
      _sz(from._sz), _rsz(from._rsz), _arr(from._arr ? new T[_rsz] : 0)
         { if (_arr) memcpy(_arr, from._arr, _sz * sizeof(T)); }

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

sz	number of elements to initially allocate
reserve	percentage of sz to keep in reserve

Definition at line 231 of file f8types.hpp.

                                                                                        : _reserve(reserve),
      _sz(sz), _rsz(_sz + calc_reserve(_sz, _reserve)), _arr() {}

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.

{ 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

idx	of 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().

{ return idx < _sz ? _arr + idx : end(); }

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.

{ 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.

{ 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

sz	number of elements currently in set; if 0 retun reserve elements as size to reserve
res	percentage 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().

   {
      if (!sz)  // special case - reserve means number to reserve, not %
         return res;
      const size_t val(sz * res / 100);
      return val ? val : 1;
   }

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.

{ _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_begin	start iterator
what_end	end iterator (must be >= to what_begin

Returns

distance in elements

Definition at line 329 of file f8types.hpp.

      { 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.

{ return _sz == 0; }

template<typename K , typename T , typename Comp >

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

inline

Get a pointer to the last element + 1

Returns

the last element + 1

Definition at line 363 of file f8types.hpp.

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

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

{ return _arr + _sz; }

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.

{ 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

what	element to find
answer	true 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().

   {
      const internal_result res(std::equal_range (_arr, _arr + _sz, what, Comp()));
      answer = res.first != res.second;
      return res.first;
   }

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

key	to find
answer	true 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().

{ return find(T(key), answer); }

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

key

to 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().

{ return find(T(key)); }

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

what	element 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().

   {
      const const_internal_result res(std::equal_range (_arr, _arr + _sz, what, Comp()));
      return res.first != res.second ? res.first : end();
   }

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

key

to 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().

{ return find(T(key)); }

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

what	value 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().

   {
      internal_result res(std::equal_range (_arr, _arr + _sz, what, Comp()));
      return res.first != res.second ? res.first : end();
   }

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

what	pointer 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().

   {
      if (!_sz)
      {
         _arr = new T[_rsz];
         memcpy(_arr, what, sizeof(T));
         ++_sz;
         return result(_arr, true);
      }

      bool answer;
      iterator where(find(*what, answer));
      if (answer)
         return result(end(), false);

      if (_sz < _rsz)
      {
         memmove(where + 1, where, (end() - where) * sizeof(T));
         memcpy(where, what, sizeof(T));
      }
      else
      {
         iterator new_arr(new T[_rsz = _sz + calc_reserve(_sz, _reserve)]);
         const size_t wptr(where - _arr);
         if (wptr > 0)
            memcpy(new_arr, _arr, sizeof(T) * wptr);
         memcpy(new_arr + wptr, what, sizeof(T));
         memcpy(new_arr + wptr + 1, where, (end() - where) * sizeof(T));
         delete[] _arr;
         _arr = new_arr;
      }
      ++_sz;
      return result(where, true);
   }

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_begin	pointer to 1st element to insert
what_end	pointer to nth element + 1 to insert

Definition at line 335 of file f8types.hpp.

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

   {
      for (const_iterator ptr(what_begin); ptr < what_end; ++ptr)
         if (!insert(ptr).second)
            break;
   }

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.

{ 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.

{ return _sz; }

Member Data Documentation

template<typename K , typename T , typename Comp >

T* FIX8::presorted_set< K, T, Comp >::_arr

private

Definition at line 196 of file f8types.hpp.

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

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.

template<typename K , typename T , typename Comp >

size_t FIX8::presorted_set< K, T, Comp >::_rsz

private

Definition at line 195 of file f8types.hpp.

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

template<typename K , typename T , typename Comp >

size_t FIX8::presorted_set< K, T, Comp >::_sz

private

Definition at line 195 of file f8types.hpp.

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

---

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

• f8types.hpp