C ++ Container with arbitrary width

Question

I have a large lookup table, which currently requires 12 bits per record. Is there a standard class that will give me a container with memory for storing data with an odd size? I have about a billion elements in the table, so I care more about memory efficiency than speed.

I need to be able to get basic data and read and write it to a file.

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

Answer 2

Have you looked at Boost :: dynamic_bitset ? I am not saying that it will be all, finish all your dreams, but it can help you with some of the characteristics that you described. It is very similar to the bitset of the standard library, only with resizable parameters.

I would not try to use it on my own to solve your problem. Instead, I could combine it with another container class and use it in combination with some sort of matching scheme. I do not know what type of display will depend on the data and the frequency of the cycles. However, thinking more about this:

 std::vector<std::bitset<12> > oneBillionDollars; //Austin Powers, my hero! 

Answer 3

You have a packaging problem. The only idea I can get is that you want to find an LCM N and some power in two. It will not be so easy, but definitely functional.

In addition, you cannot manipulate some data with a large size, so you need to pack it into a larger integer type. The table will contain the data packed, but the "accessor" will provide the unpacked file.

 // General structure template <size_t N> class Pack { public: static size_t const Number = N; static size_t const Density = 0; // number of sets of N bits typedef char UnpackedType; // some integral UnpackedType Get(size_t i) const; // i in [0..Density) void Set(size_t i, UnpackedType t); // i in [0..Density) // arbitrary representation }; // Example, for 12 bits // Note: I assume that all is set, you'll have to pad... // but for a million one or two more should not be too much of an issue I guess // if it is, the table shall need one more data member, which is reasonnable class Pack12 { public: typedef uint16_t UnpackedType; static size_t const Number = 12; static size_t const Density = 4; UnpackedType get(size_t i) const; void set(size_t i, UnpackedType t); private: uint16_t data[3]; }; 

Now we can build this to create a common table that will work for any package:

 template <typename Pack> class Table { public: typedef typename Pack::UnpackedType UnpackedType; bool empty() const; size_t size() const; UnpackedType get(size_t i) const; void set(size_t i, UnpackedType t); private: static size_t const NumberBits = Pack::Number; static size_t const Density = Pack::Density; std::deque<Pack> data; }; template <typename Pack> bool Table<Pack>::empty() const { return data.empty(); } template <typename Pack> size_t Table<Pack>::size() const { return data.size() * Density; } template <typename Pack> typename Table<Pack>::UnpackedType Table<Pack>::get(size_t i) const { Pack const& pack = data.at(i / Density); return pack.get(i % Density); } // Table<Pack>::set is the same 

A smarter way for Pack<N> would be to output getters and views ... but this doesn't seem to be necessary because the Pack interface is minimal and Table can represent a richer interface without asking for more.