如何使用位数组在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; 
}