A simple BitSet implementation that mimics a set of indices. More...
#include <bitset.h>
Collaboration diagram for Ponca::BitSet< N, T >:Public Types | |
| using | container_type = std::array< T, N > |
| using | iterator = typename container_type::iterator |
Public Member Functions | |
| void | flip (int i) |
| Toggles the value of a bit. | |
| bool | erase (int value) |
| Tries to insert a value in the set. | |
| std::pair< iterator, bool > | insert (const int &value) |
| Tries to insert a value in the set. | |
| bool | contains (int value) const |
| Search if the value was already inserted or not. | |
| void | clear () |
| Sets all the bits to EMPTY. | |
| iterator | begin () |
| iterator | end () |
Protected Attributes | |
| container_type | m_data = {} |
| An array of bytes. | |
Detailed Description
requires ValidCapacity<N>
class Ponca::BitSet< N, T >
A simple BitSet implementation that mimics a set of indices.
The internal logic of this bitset is similar to std::bitset, but is compatible with CUDA.
Allows to insert and search in O(1) complexity, but is memory expensive, because we allocate a single bit for each possible indices, to flag if it was inserted or not, which is not ideal for large amount of indices.
The memory use of the BitSet depending on N should be in theory :
| BitSet size | Memory used |
|---|---|
| Bitset<10000> | 1.25 KB |
| Bitset<1e6> | 125 KB |
| Bitset<1e7> | 1.25 MB |
- Template Parameters
-
N Maximum number of indices T The data type of the array storing the bits. Default to 'unsigned long long' for 64 bits storage.
- See also
BitSet::erase,BitSet::insertfor set-index-like methods- HashSet For alternative data structure with compatible API
- Warning
- The inserted values must always be smaller than N, because we are using them as indices to store the bits inside the BitSet.
Member Typedef Documentation
◆ container_type
| using Ponca::BitSet< N, T >::container_type = std::array<T, N> |
◆ iterator
| using Ponca::BitSet< N, T >::iterator = typename container_type::iterator |
Member Function Documentation
◆ begin()
requires ValidCapacity<N>
| BitSet< N, T >::iterator Ponca::BitSet< N, T >::begin | ( | ) |
Definition at line 15 of file bitset.hpp.
◆ clear()
requires ValidCapacity<N>
| void Ponca::BitSet< N, T >::clear | ( | ) |
Sets all the bits to EMPTY.
Definition at line 31 of file bitset.hpp.
◆ contains()
requires ValidCapacity<N>
| bool Ponca::BitSet< N, T >::contains | ( | int | value | ) | const |
Search if the value was already inserted or not.
- Parameters
-
value The value to search for (search is O(N) because it corresponds to the index in the BitSet)
- Returns
Definition at line 65 of file bitset.hpp.
◆ end()
requires ValidCapacity<N>
| BitSet< N, T >::iterator Ponca::BitSet< N, T >::end | ( | ) |
Definition at line 22 of file bitset.hpp.
◆ erase()
requires ValidCapacity<N>
| bool Ponca::BitSet< N, T >::erase | ( | int | value | ) |
Tries to insert a value in the set.
- Parameters
-
value The value to be removed in the set. Must always be smaller than N, because we are using the values as indices inside the BitSet.
- Returns
- True if the value was removed successfully, and false if the value was already not inside the Set
Definition at line 38 of file bitset.hpp.
◆ flip()
requires ValidCapacity<N>
| void Ponca::BitSet< N, T >::flip | ( | int | i | ) |
◆ insert()
requires ValidCapacity<N>
| std::pair< typename BitSet< N, T >::iterator, bool > Ponca::BitSet< N, T >::insert | ( | const int & | value | ) |
Tries to insert a value in the set.
- Parameters
-
value The value to be inserted in the HashSet. Must always be smaller than N, because we are using the values as indices inside the BitSet.
- Returns
- An std::pair of
- First : Pointer to the inserted value (not usable, see warning below)
- Second : True if the value was inserted successfully, and false if the value wasn't inserted
- Warning
- The returned pointer cannot be used as several values are packed behind the same pointer location. This value is included for the sake of compatibility with std::set, but cannot be used directly as the bitmask is not exported (unreferencing the pointer will not give access to the value).
Definition at line 52 of file bitset.hpp.
Member Data Documentation
◆ m_data
|
protected |
