c++ - 如何使用位数组在 C/C++ 中实现集合？

Question

我在很多地方读到 set data structure可以使用 bit array 在 C++ 中实现，但我并不完全理解这一点，也无法找到代码示例。有没有人有例子或详细解释？

Answer 1

只有当集合中只有少数可能的元素时，使用位域来实现集合才有效，因为每个元素都需要一个位。例如，所有 32 位整数的位集将需要 2^32 位，或大约 500 兆字节。

好消息是，如果可能的元素足够少，那么空间就不是问题，它真的非常非常快。

本质上，您所做的是定义一个位数组，使每个位对应一个可能的元素。与集合中的元素对应的每个位都是 1；其他为0。

稍后将发布示例 C 代码(无双关语)。我认为 C++ 可能会为位集提供直接的库支持，但不幸的是我不会说。

编辑:我刚刚编写的以下示例代码适用于可以包含数字 0 到 31 的位集。允许支持任意数量的元素会复杂得多，但肯定有用。

#include <stdint.h>
#include <stdio.h>

const BS_SIZE = 32;
typedef uint32_t bitset32;

/* Takes a pointer to a bit set and an int from 0 to 31,
 * and adds the int to the bit set.
 */
void add_element(bitset32 *bs, int elt)
{
    *bs |= (1 << elt);
}

/* Takes a pointer to a bit set and an int from 0 to 31,
 * and removes the int from the bit set.
 */
void remove_element(bitset32 *bs, int elt)
{
    *bs &= ~(1 << elt);
}

/* Takes a pointer to a bit set and an int from 0 to 31,
 * and returns 1 if the int is in the bit set, 0 otherwise.
 */
int has_element(bitset32 *bs, int elt)
{
    return (*bs >> elt) & 1;
}

/* Takes a pointer to a bit set and prints each element in it. */
void print_all_elements(bitset32 *bs)
{
    bitset32 bits = *bs;
    int i;
    for (i = 0; i < BS_SIZE; i++) {
        if (bits & 1) {
            printf("%d\n", i);
        }
        bits >>= 1;
    }
}

/* Some test code. Prints:
 * 0 in test
 * 0
 * 20
 * 31
 */
int main()
{
    bitset32 test = 0;
    add_element(&test, 0);
    add_element(&test, 13);
    add_element(&test, 13);
    add_element(&test, 20);
    add_element(&test, 28);
    remove_element(&test, 13);
    remove_element(&test, 20);
    remove_element(&test, 28);
    if (has_element(&test, 0)) {
        printf("0 in test\n");
    }
    if (has_element(&test, 20)) {
        printf("20 in test\n");
    }
    add_element(&test, 20);
    add_element(&test, 31);
    print_all_elements(&test);
    return 0;
}