C++ Arbitrary width container

Question

I have a large lookup table that currently needs 12 bits per entry. Is there a standard class that will give me a memory efficient container for storing odd-sized data? I have about a billion items in the table, so I care more about memory efficiency than speed.

I need to be able to get the underlying data and read/write it to a file as well.

Answer 1

How about this:

#include <stdio.h>

typedef unsigned char byte;
typedef unsigned short word;
typedef unsigned int uint;
typedef unsigned long long int qword;

enum {
  bits_per_cell = 12, cellmask = (1<<bits_per_cell)-1,
  N_cells = 1000000,
  bufsize = (N_cells*bits_per_cell+7)/8,
};

byte* buf;

byte* Alloc( void ) {
  buf = new byte[bufsize];
  return buf;
};

// little-endian only
void put( uint i, uint c ) {
  qword x = qword(i)*bits_per_cell;
  uint  y = x&15, z = (x>>4)<<1;
  uint& a = (uint&)buf[z];
  uint mask = ~(cellmask<<y);
  a = a & mask | ((c&cellmask)<<y);
}

uint get( uint i ) {
  qword x = qword(i)*bits_per_cell;
  uint  y = x&15, z = (x>>4)<<1;
  uint& a = (uint&)buf[z];
  return (a>>y)&cellmask;
}

/* 

// bigendian/universal
void put( uint i, uint c ) {
  qword x = qword(i)*bits_per_cell;
  uint y = x&7, z = (x>>3);
  uint a = buf[z] + (buf[z+1]<<8) + (buf[z+2]<<16);
  uint mask = ~(cellmask<<y);
  a = a & mask | ((c&cellmask)<<y);
  buf[z] = byte(a); buf[z+1]=byte(a>>8); buf[z+2]=byte(a>>16);
}

uint get( uint i ) {
  qword x = qword(i)*bits_per_cell;
  uint  y = x&7, z = (x>>3);
  uint a = buf[z] + (buf[z+1]<<8) + (buf[z+2]<<16);
  return (a>>y)&cellmask;
}
*/

int main( void ) {

  if( Alloc()==0 ) return 1;

  uint i;

  for( i=0; i<N_cells; i++ ) put( i^1, i );

  for( i=0; i<N_cells; i++ ) {
    uint j = i^1, c, d; 
    c = get(j); d = i & cellmask;
    if( c!=d ) printf( "x[%08X]=%04X, not %04X\n", j,c,d );
  }

}