C++任意宽度容器

Question

我有一个大的查找表,目前每个条目需要12位.是否有一个标准类将为我提供一个内存有效的容器来存储奇数大小的数据？表中有大约10亿个项目,所以我更关心内存效率而不是速度.

我需要能够获取底层数据并将其读/写到文件中.

Answer 1

这个怎么样：

#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 );
  }

}