File BoolSet.h

↰ Parent directory (ADS/set)

The SET of the integers in [ 0 , N ) as a boolean vector of section 8.1: contains(), insert() and remove() in O( 1 ), min(), max() and forEach() in O( N ), union, intersection, difference and symmetric difference in :math:` Theta( N ) ` (the first is called setUnion(), union being a keyword of C++, and so the others are setIntersection(), setDifference() and setSymmetricDifference()).

Definition (ADS/set/BoolSet.h)

Detailed Description

The vector is kept as words of 64 bits, and the operations of two sets and the scans of min(), max() and forEach() go a word at a time: the same loops on the N booleans, 64 of them in one operation of the processor, which leaves the bounds unchanged and divides the time by up to 64 ( :math:` lceil N / 64 rceil ` operations on words for a set of dimension N); the size of a result is the count of its bits, in the same pass as the operation, with AVX2 by the method of Muła, Kurz and Lemire (a shuffle of bytes looks up the bits of each half byte, and a sum of absolute differences adds the bytes), 4 words at a time, and the words of a result are written once, not filled with zeros before.

The contracts [see File Contract.h]: N >= 0, an item inserted is in [ 0 , N ), and each operation of two sets gives, item by item, what its name says; the invariant is that the size counts the bits set. The operations are defined in BoolSet.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 8.1, https://algoritmicamente.it/materiali/libro/capitoli/cap08.pdf

  1. Muła, N. Kurz, D. Lemire, Faster population counts using AVX2 instructions, The Computer Journal 61(1), 2018, doi:10.1093/comjnl/bxx046

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions