sux::bits::SimpleSelect< AT > Class Template Reference

#include <SimpleSelect.hpp>

Inheritance diagram for sux::bits::SimpleSelect< AT >:

Public Member Functions
	SimpleSelect ()
	SimpleSelect (const uint64_t *const bits, const uint64_t num_bits, const int max_log2_longwords_per_subinventory)
size_t	select (const uint64_t rank)
size_t	bitCount () const
Public Member Functions inherited from sux::Select
virtual	~Select ()=default

Detailed Description

template<util::AllocType AT = util::AllocType::MALLOC>
class sux::bits::SimpleSelect< AT >

A simple Select implementation based on a two-level inventory, a spill list and broadword bit search.

This implementation uses around 13.75% additional space on evenly distributed bit arrays, and, under the same conditions, provide very fast selects. For very unevenly distributed arrays the space occupancy will grow significantly, and access time might vary wildly.

The constructors of this class only store a reference to a provided bit vector. Should the content of the bit vector change, the results will be unpredictable.

Template Parameters

AT	a type of memory allocation out of sux::util::AllocType.

Constructor & Destructor Documentation

SimpleSelect() [1/2]

template<util::AllocType AT = util::AllocType::MALLOC>

sux::bits::SimpleSelect< AT >::SimpleSelect ( )

inline

SimpleSelect() [2/2]

template<util::AllocType AT = util::AllocType::MALLOC>

sux::bits::SimpleSelect< AT >::SimpleSelect ( const uint64_t *const  bits, const uint64_t  num_bits, const int  max_log2_longwords_per_subinventory  )

inline

Creates a new instance using a given bit vector.

Parameters

bits	a bit vector of 64-bit words.
num_bits	the length (in bits) of the bit vector.
max_log2_longwords_per_subinventory	the number of words per subinventory: a larger value yields a faster map that uses more space; typical values are between 0 and 3.

Member Function Documentation

bitCount()

template<util::AllocType AT = util::AllocType::MALLOC>

size_t sux::bits::SimpleSelect< AT >::bitCount ( ) const

inline

Returns an estimate of the size (in bits) of this structure.

select()

template<util::AllocType AT = util::AllocType::MALLOC>

size_t sux::bits::SimpleSelect< AT >::select ( const uint64_t  rank )

inlinevirtual

Returns the position of the one with given rank.

Parameters

rank	the desired rank (index) of a one in the bit vector.

Returns

the position of the zero with given rank; the result is undefined if no zero of the given rank exists.

Implements sux::Select.

---

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

• sux/bits/SimpleSelect.hpp