[데이터 구조] 중의 비트 맵 상세 설명

1564 단어 데이터 구조
정의:
비트 맵 법 은 bitmap 의 줄 임 말이다.비트 맵 이란 모든 사람 이 특정한 상 태 를 저장 하고 대규모 데이터 에 적용 되 지만 데이터 상태 가 많은 경우 도 아니다.일반적으로 어떤 데이터 저장 이 존재 하지 않 는 지 판단 하 는 데 쓰 인 다.
장단 점:
(1) 가 독성 이 떨어진다.
(2) 비트 맵 에 저 장 된 요소 의 개 수 는 일반적인 방법 보다 많 지만 저 장 된 요소 의 크기 는 저장 공간의 크기 에 제한 을 받는다.비트 맵 저장 성질: 저 장 된 요소 의 개 수 는 요소 의 최대 값 과 같 습 니 다.예 를 들 어 1K 바이트 메모리 에는 8K 개의 값 크기 상한 선 이 8K 인 요 소 를 저장 할 수 있다.(원소 값 상한 선 은 8K 로 한계 가 큽 니 다!) 예 를 들 어 65535 의 수 를 저장 하려 면 65535 / 8 = 8K 바이트 의 메모리 가 필요 합 니 다.이 로 인해 비트 맵 법 은 unsigned int 형식의 수 에 전혀 적합 하지 않 습 니 다 (약 2 ^ 32 / 8 = 5 억 바이트 의 메모리 가 필요 합 니 다).
(3) 비트 맵 은 기호 유형 데이터 에 대한 저장 을 위해 기호 요 소 를 표시 하 는 두 자리 가 필요 하 다.이것 은 비트 맵 에 저장 할 수 있 는 요소 의 개 수 를 양보 하고 요소 의 크기 상한 선 을 반 으로 줄 일 것 입 니 다. 예 를 들 어 8K 바이트 메모리 공간 에 short 형식의 데 이 터 를 저장 하면 8K * 4 = 32K 개 만 저장 할 수 있 고 요소 값 의 크기 범 위 는 - 32K ~ 32K 이다.
인터페이스의 실현:
#include
using namespace std;
#include
class BitSet
{
public:
	BitSet(size_t range)
	{
		_a.resize(range >> 5 + 1, 0);
	}
	void Set(size_t num)
	{
		size_t index = num >> 5;
		size_t pos = num % 32;
		_a[index] |= (1 << pos);
	}

	void Reset(size_t num)
	{
		size_t index = num >> 5;
		size_t pos = num % 32;
		_a[index] = ~(1 << pos);
	}

	bool Test(size_t num)
	{
		size_t index = num >> 5;
		size_t pos = num % 32;
		return _a[index] & (1 << pos);
	}


protected:
	vector _a;
};


void Test()
{
	BitSet s1(-1);
	s1.Set(1);
	s1.Set(8);
	s1.Set(32);
}
int main()
{
	Test();
	system("pause");
	return 0;
}

좋은 웹페이지 즐겨찾기