2013-03-11 45 views
5

Tôi cần thực hiện kích thước tối thiểu của một loạt các bool. Kích thước của mảng được biết tại thời gian biên dịch.Thực hiện kích thước tối thiểu đối với mảng bool

Tôi đã kiểm tra std::bitsetboost::array, nhưng cả hai đều phải chịu chi phí cao cho các mảng nhỏ. Ví dụ: nếu kích thước mảng là , vùng chứa chỉ nên sử dụng 1 byte bộ nhớ (giả sử kiến ​​trúc CPU chung).

Điều này có tồn tại hay tôi cần phải cuộn của riêng mình?

EDIT: Đây là lần triển khai cuối cùng của tôi dựa trên bài đăng của Tom Knapen. Tôi đã thêm giá trị mặc định cho hàm tạo và thêm vào trường hợp chỉ số vượt quá giới hạn. Rất cám ơn Tom và mọi người khác.

#include <stdexcept> 
#include <climits> 

/// Minimum size container for bool-arrays 
/** 
* TODO: may want to add to_uint32_t accessor and the like 
* for sufficently small arrays 
*/ 
template<int SIZE> 
class bitarray 
{ 
public: 
    bitarray(bool initial_value = false); 

    bool get(int index) const; 
    void set(int index, bool value); 

private: 
    static const int ARRAY_SIZE = (SIZE + CHAR_BIT - 1)/8; 
    unsigned char mBits[ARRAY_SIZE]; 
}; 

// ---------------------------------------------------- 
//  Definitions 
// ---------------------------------------------------- 

template<int SIZE> 
inline bitarray<SIZE>::bitarray(bool initial_value) 
{ 
    for(int i = 0; i < ARRAY_SIZE; ++i) 
     mBits[i] = initial_value ? -1 : 0; 
} 

template<int SIZE> 
inline bool bitarray<SIZE>::get(int index) const 
{ 
    if (index >= SIZE) 
     throw std::out_of_range("index out of range"); 
    return (mBits[index/CHAR_BIT] & (1 << (index % CHAR_BIT))); 
} 

template<int SIZE> 
inline void bitarray<SIZE>::set(int index, bool value) 
{ 
    if (index >= SIZE) 
     throw std::out_of_range("index out of range"); 
    if (value) 
     mBits[index/CHAR_BIT] |= (1 << (index % CHAR_BIT)); 
    else 
     mBits[index/CHAR_BIT] &= ~(1 << (index % CHAR_BIT)); 
} 
+0

'std: bitset' chỉ nên sử dụng một bit cho mỗi phần tử (là 'std :: vector ' làm trong một số triển khai). Làm cách nào bạn kiểm tra xem nó có sử dụng nhiều hơn không? –

+0

@ FrédéricHamidi nếu bạn làm 'sizeof (std :: vector )' nó trả về 40 –

+0

@ Frédéric Hamidi: Sử dụng toán tử sizeof. Đây là một phần của quá trình triển khai, nó sử dụng phân bổ động: \t _WordT * _M_wp; \t size_t _M_bpos; Có thể khác nhau cho việc triển khai std khác –

Trả lời

2

Đây là một ví dụ đơn giản. Xin lưu ý rằng nó chỉ làm những gì nó cần, vì vậy bạn sẽ không thể lặp nó như một std :: bitset.

#include <climits> 
#include <iostream> 
#include <cassert> 

template<int S> struct boolset { 
    static int const SIZE = ((S/CHAR_BIT) + (0 != (S % CHAR_BIT))); 
    unsigned char m_bits[SIZE]; 
public: 
    boolset() : m_bits() { for(int i = 0; i < SIZE; ++i) m_bits[i] = 0; } 

    bool get(int i) const { 
     assert(i < S); 
     return (m_bits[i/CHAR_BIT] & (1 << (i % CHAR_BIT))); 
    } 

    void set(int i, bool v) { 
     assert(i < S); 
     if(v) { m_bits[i/CHAR_BIT] |= (1 << (i % CHAR_BIT)); } 
     else { m_bits[i/CHAR_BIT] &= ~(1 << (i % CHAR_BIT)); } 
    } 

    void print(std::ostream & s) const { 
     for(int i = 0; i < S; ++i) { 
      s << get(i); 
     } 
    } 
}; 

int main(int argc, char ** argv) { 
    std::cout << sizeof(boolset<1>) << std::endl; 
    std::cout << sizeof(boolset<8>) << std::endl; 
    std::cout << sizeof(boolset<9>) << std::endl; 
    std::cout << sizeof(boolset<16>) << std::endl; 
    std::cout << sizeof(boolset<17>) << std::endl; 
    std::cout << sizeof(boolset<32>) << std::endl; 
    std::cout << sizeof(boolset<33>) << std::endl; 
    std::cout << sizeof(boolset<64>) << std::endl; 
    std::cout << sizeof(boolset<129>) << std::endl; 
    std::cout << std::endl; 
    boolset<31> bs; 
    bs.set(0, true); 
    bs.set(28, true); 
    bs.set(2, true); 
    std::cout << bs.get(28) << std::endl; 
    bs.print(std::cout); std::cout << std::endl; 
    bs.set(2, false); 
    bs.print(std::cout); std::cout << std::endl; 
} 

Đầu ra trên ideone.

+0

Đã học được điều gì đó mới: các thành viên tĩnh tất nhiên phụ thuộc vào thông số mẫu. Không hoàn toàn nhận ra điều này trước đây. –

1

Có lẽ nếu bạn làm điều gì như thế này:

#include<vector> 
#include <iostream> 
template<int N> 
struct array 
{ 
    char bits : N; 

    int getNthbit(int bitnr) 
    { 
     // important to make sure bitnr is not larger than the size of the type of `bits` in number of `CHAR_BITS` 
     return bits & (1 << bitnr); 
    } 
}; 

//Specialize for N > 8 

int main() 
{ 
    std::cout << sizeof(array<8>); 
} 

Nếu bạn nhìn vào Live Example, bạn sẽ thấy khi N == 8 nó sẽ trả về 1 cho sizeof(array<8>).

Khi bạn đặt vào 32 nó trả 4.

Điều duy nhất bạn cần làm là chuyên template cho N> 8 để các thay đổi loại để phù hợp với số bit.

Tôi không có thiên tài mẫu, có thể ai đó quan tâm để viết một ví dụ?

+0

Vâng, một mảng char [number_of_bits% 8] về cơ bản là những gì tôi có trong tâm trí như cấu trúc dữ liệu. Nhưng tôi cần accessors làm bit chuyển và đã tự hỏi nếu điều này đã tồn tại. –

+0

@GabrielSchreiber Tôi chưa bao giờ thấy nó, nhưng tôi không thể tưởng tượng được việc viết các trình truy cập cho bit N là khó. –

+0

@TonyTheLion Tôi sợ việc triển khai này sẽ không hiệu quả đối với N> 8, và nó chắc chắn sẽ không hoạt động đối với N> 64. – anatolyg

3

Bạn có thể tự mình làm, nhưng không phải từ đầu. Triển khai bitset phải có một vài dòng giống như typedef unsigned long _WordT; (SGI) hoặc typedef _Uint32t _Ty; (MSVS). Bạn có thể cẩn thận thay thế loại và không gian tên và tạo vùng chứa của riêng bạn theo cách này. Tôi đã thay đổi kiểu để char và sizeof lợi nhuận 1 (VS2010 proof-of-concept trên pastebin)

2
template <int N> 
class BitSet { 
    enum { BPC = 8 }; // Bits per char, #ifdef as needed 
    char m_bits[ (N + (BPC-1))/BPC ]; 
public: 
void SetBit(int i) { m_bits[ i/BPC ] |= 1 << (i % BPC); } 
void ClearBit(int i) { m_bits[ i/BPC ] &= ~(1 << (i % BPC)); } 
int GetBit(int i) { return (m_bits[ i/BPC ] >> (i % BPC)) & 1; } 
}; 
Các vấn đề liên quan