Keeping track of boolean data

I need to keep track of n samples. The information I am keeping track of is of boolean type, i.e. something is true or false. As soon as I am on sample n+1, i basically want to ignore the oldest sample and record information about the newest one.

So say I keep track of samples, I may have something like

OLDEST 0 0 1 1 0 NEWEST

If the next sample is 1, this will become

OLDEST 0 1 1 0 1 NEWEST

if the next one is 0, this will become...

OLDEST 1 1 0 1 0 NEWEST

So what is the best way to implement this in terms of simplicity and memory?

Some ideas I had:

Vector of bool (this would require shifting elements so seems expensive) Storing it as bits...and using bit shifting (memorywise --cheap? but is there a limit on the number of samples?) Linked lists? (might be an overkill for the task)

Thanks for the ideas and suggestions :)

You want a set of bits. Maybe you can look into a std::bitset

http://www.sgi.com/tech/stl/bitset.html

Very straightfoward to use, optimal memory consumption and probably the best performance

The only limitation is that you need to know at compile-time the value of n. If you want to set it on runtime, have a look at boost http://www.boost.org/doc/libs/1_36_0/libs/dynamic_bitset/dynamic_bitset.html

Sounds like a perfect use of a ring buffer. Unfortunately there isn't one in the standard library, but you could use boost.

Alternately roll your own using a fixed-length std::list and splice the head node to the tail when you need to overwrite an old element.

It really depends on how many samples you want to keep. vector<bool> could be a valid option; I would expect an erase() on the first element to be reasonably efficient. Otherwise, there's deque<bool>. If you know how many elements you want to keep at compile time, bitset<N> is probably better than either.

In any case, you'll have to wrap the standard container in some additional logic; none have the actual logic you need (that of a ring buffer).

If you only need 8 bits... then use a char and do logical shifts "<<, >>" and do a mask to look at the one you need.

• 16 Bits - short
• 32 Bits - int
• 64 Bits - long
• etc...

Example:

Oldest 00110010 Newest -> Oldest 1001100101 Newest

Done by:

char c = 0x32; // 50 decimal or 00110010 in binary
c<<1; // Logical shift left once.
c++; // Add one, sense LSB is the newest.

//Now look at the 3rd newest bit
print("The 3rd newest bit is: %d\n", (c & 0x4));

Simple and EXTREMELY cheap on resources. Will be VERY VERY high performance.

From your question, it's not clear what you intend to do with the samples. If all you care about is storing the N most recent samples, you could try the following. I'll do it for "chars" and let you figure out how to optimize for "bool" should you need that.

char buffer[N];
int samples = 0;

void record_sample( char value )
{
  buffer[samples%N] = value;
  samples = samples + 1;
}

Once you've stored N samples (once you've called record_sample N times) you can read the oldest and newest samples like so:

char oldest_sample()
{
  return buffer[samples%N];
}

char newest_sample()
{
  return buffer[(samples+N-1)%N];
}

Things get a little trickier if you intend to read the oldest sample before you've already stored N samples - but not that much trickier. For that, you want a "ring buffer" which you can find in boost and on wikipedia.