CODEWITHSUNDEEP
c++bitarray
vedran
vedran

Reputation: 781

Use bit arrays?

Imagine there's a fixed and constant set of 'options' (e.g. skills). Every object (e.g. human) can either have or not have any of the options.

Should I maintain a member list-of-options for every object and fill it with options?

OR:

Is it more efficient (faster) to use a bitarray where each bit represents the respective option's taken (or not taken) status?

-edited:-

To be more specific, the list of skills is a vector of strings (option names), definitely shorter than 256. The target is for the program to be AS FAST as possible (no memory concerns).

Upvotes: 0

Views: 224

Answers (3)

Fred Foo
Fred Foo

Reputation: 363487

That rather depends. If the number of options is small, then use several bool members to represent them. If the list grows large, then both your options become viable:

  • a bitset (which an appropriate enum to symbolically represent the options) takes a constant, and very small, amount of space, and getting a certain option takes O(1) time;
  • a list of options, or rather an std::set or unordered_set of them, might be more space-efficient, but only if the number of options is huge, and it is expected that a very small number of them will be set per object.

When in doubt, use either a bunch of bool members, or a bitset. Only if profiling shows that storing options becomes a burden, consider a dynamic list or set representation (and even then, you might want to reconsider your design).

Edit: with less than 256 options, a bitset would take at most 64 bytes, which will definitely beat any list or set representation in terms of memory and likely speed. A bunch of bools, or even an array of unsigned char, might still be faster because accessing a byte is commonly faster than accessing a bit. But copying the structure will be slower, so try several options and measure the result. YMMV.

Upvotes: 2

Qwertie
Qwertie

Reputation: 17176

The bitarray will be generally faster to edit and faster to search. As for space required, just do the math. A list of options requires a dynamically sized array (which suffers some overhead over the set of options itself); but if there are a large number of options, it may be smaller if (typically) only a small number of options are set.

Upvotes: 0

Pepe
Pepe

Reputation: 6480

Using a bit array is faster when testing for the presence of multiple skills in a person in a single operation.

If you use a list of options then you'll have to go over the list one item at a time to find if a skill set exits which would obviously take more time and require many comparison operations.

Upvotes: 1

Related Questions