Define smallest possible datatype in c++ that can hold six values

Question

I want to define my own datatype that can hold a single one of six possible values in order to learn more about memory management in c++. In numbers, I want to be able to hold 0 through 5. Binary, It would suffice with three bits (101=5), although some (6 and 7) wont be used. The datatype should also consume as little memory as possible.

Im not sure on how to accomplish this. First, I tried an enum with defined values for all the fields. As far as I know, the values are in hex there, so one "hexbit" should allow me to store 0 through 15. But comparing it to a char (with sizeof) it stated that its 4 times the size of a char, and a char holds 0 through 255 if Im not misstaken.

#include <iostream>

enum Foo
{
    a = 0x0, 
    b = 0x1,
    c = 0x2,
    d = 0x3,
    e = 0x4,
    f = 0x5,
};

int main()
{
    Foo myfoo = a;
    char mychar = 'a';

    std::cout << sizeof(myfoo); // prints 4
    std::cout << sizeof(mychar); // prints 1

    return 1;
}

Ive clearly misunderstood something, but fail to see what, so I turn to SO. :)

Also, when writing this post I realised that I clearly lack some parts of the vocabulary. Ive made this post a community wiki, please edit it so I can learn the correct words for everything.

Answer 1

You can use an unsigned char. Probably typedef it into an BYTE. It will occupy only one byte.

Answer 2

A char is the smallest possible type.

If you happen to know that you need several such 3 bit values in a single place you get use a structure with bitfield syntax:

struct foo {
  unsigned int val1:3;
  unsigned int val2:3;
};

and hence get 2 of them within one byte. In theory you could pack 10 such fields into a 32-bit "int" value.

Answer 3

Minimal size what you can use - 1 byte.

But if you use group of enum values ( writing in file or storing in container, ..), you can pack this group - 3 bits per value.

Answer 4

The best solution is to create your own type implemented using a char. This should have sizeof(MyType) == 1, though this is not guaranteed.

#include <iostream>
using namespace std;

class MyType {

    public:

     MyType( int a ) : val( a ) {
      if ( val < 0 || val > 6 ) {
       throw( "bad value" );
      }
     }

     int Value() const {
      return val;
     }

    private:

     char val;
};

int main() {

    MyType v( 2 );
    cout << sizeof(v) << endl;
    cout << v.Value() << endl;
}

Answer 5

You don't have to enumerate the values of the enum:

enum Foo
{
    a, 
    b,
    c,
    d,
    e,
    f,
};

Foo myfoo = a;

Here Foo is an alias of int, which on your machine takes 4 bytes.

The smallest type is char, which is defined as the smallest addressable data on the target machine. The CHAR_BIT macro yields the number of bits in a char and is defined in limits.h.

[Edit]

Note that generally speaking you shouldn't ask yourself such questions. Always use [unsigned] int if it's sufficient, except when you allocate quite a lot of memory (e.g. int[100*1024] vs char[100*1024], but consider using std::vector instead).

Answer 6

C++ does not express units of memory smaller than bytes. If you're producing them one at a time, That's the best you can do. Your own example works well. If you need to get just a few, You can use bit-fields as Alnitak suggests. If you're planning on allocating them one at a time, then you're even worse off. Most archetectures allocate page-size units, 16 bytes being common.

Another choice might be to wrap std::bitset to do your bidding. This will waste very little space, if you need many such values, only about 1 bit for every 8.

If you think about your problem as a number, expressed in base-6, and convert that number to base two, possibly using an Unlimited precision integer (for example GMP), you won't waste any bits at all.

This assumes, of course, that you're values have a uniform, random distribution. If they follow a different distribution, You're best bet will be general compression of the first example, with something like gzip.

Answer 7

C++ 0x will contain Strongly typed enumerations where you can specify the underlying datatype (in your example char), but current C++ does not support this. The standard is not clear about the use of a char here (the examples are with int, short and long), but they mention the underlying integral type and that would include char as well.

As of today Neil Butterworth's answer to create a class for your problem seems the most elegant, as you can even extend it to contain a nested enumeration if you want symbolical names for the values.

Answer 8

The size of an enumeration is defined to be the same of an int. But depending on your compiler, you may have the option of creating a smaller enum. For example, in GCC, you may declare:

enum Foo {
    a, b, c, d, e, f
}
__attribute__((__packed__));

Now, sizeof(Foo) == 1.

Answer 9

You can store values smaller than 8 or 32 bits. You just need to pack them into a struct (or class) and use bit fields.

For example:

struct example
{
    unsigned int a : 3; //<Three bits, can be 0 through 7.
            bool b : 1; //<One bit, the stores 0 or 1.
    unsigned int c : 10; //<Ten bits, can be 0 through 1023.
    unsigned int d : 19; //<19 bits, can be 0 through 524287.
}

In most cases, your compiler will round up the total size of your structure to 32 bits on a 32 bit platform. The other problem is, like you pointed out, that your values may not have a power of two range. This will make for wasted space. If you read the entire struct as one number, you will find values that will be impossible to set, if your input ranges aren't all powers of 2.

Another feature you may find interesting is a union. They work like a struct, but share memory. So if you write to one field it overwrites the others.

Now, if you are really tight for space, and you want to push each bit to the maximum, there is a simple encoding method. Let's say you want to store 3 numbers, each can be from 0 to 5. Bit fields are wasteful, because if you use 3 bits each, you'll waste some values (i.e. you could never set 6 or 7, even though you have room to store them). So, lets do an example:

//Here are three example values, each can be from 0 to 5:
const int one = 3, two = 4, three = 5;

To pack them together most efficiently, we should think in base 6 (since each value is from 0-5). So packed into the smallest possible space is:

//This packs all the values into one int, from 0 - 215.
//pack could be any value from 0 - 215. There are no 'wasted' numbers.
int pack = one + (6 * two) + (6 * 6 * three);

See how it looks like we're encoding in base six? Each number is multiplied by it's place like 6^n, where n is the place (starting at 0).

Then to decode:

const int one = pack % 6;
pack /= 6;
const int two = pack % 6;
pack /= 6;
const int three = pack;

Theses schemes are extremely handy when you have to encode some fields in a bar code or in an alpha numeric sequence for human typing. Just saying those few partial bits can make a huge difference. Also, the fields don't all have to have the same range. If one field is from 0 through 7, you'd use 8 instead of 6 in the proper place. There is no requirement that all fields have the same range.

Answer 10

It is likely that packing oddly sized values into bitfields will incur a sizable performance penalty due to the architecture not supporting bit-level operations (thus requiring several processor instructions per operation). Before you implement such a type, ask yourself if it is really necessary to use as little space as possible, or if you are committing the cardinal sin of programming that is premature optimization. At most, I would encapsulate the value in a class whose backing store can be changed transparently if you really do need to squeeze every last byte for some reason.