[데이터 구조] 중의 비트 맵 상세 설명
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.