返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C++如何实现BitMap数据结构
  • 566
分享到

C++如何实现BitMap数据结构

2024-04-02 19:04:59 566人浏览 八月长安
摘要

目录一、BitMap位图二、c++实现分治,分布式。BitMap(位图)及其升级版bloom filter是处理海量数据常用的方法,这里先介绍BitMap概念及其c++实现。 一、B

分治,分布式。BitMap(位图)及其升级版bloom filter是处理海量数据常用的方法,这里先介绍BitMap概念及其c++实现。

一、BitMap位图

数据结构描述了一个有限定义域内的稠密集合,其中的每一个元素最多出现一次并且没有其他任何数据与该元素相关联。

即使这些条件没有完全满足(例如,存在重复元素或额外的数据),也可以用有限定义域内的键作为一个表项更复杂的表格索引

所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。

由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。

例如假设我们要对0-7内的5个元素(4,7,2,5,3)排序(这里假设这些元素没有重复)。

那么我们就可以采用Bit-map的方法来达到排序的目的。

要表示8个数,我们就只需要8个Bit(1Bytes),首先我们开辟1Byte的空间,将这些空间的所有Bit位都置为0,

如下图:

遍历第一个元素4,则在第4为标1:

以此来推,遍历完所有后结构:

我们现在遍历一遍Bit区域,将该位是bit 1的位的编号输出(2,3,4,5,7),这样就达到了排序的目的。

二、C++实现

我们可以用一个unsigned int类型的数组或者向量来表示位图,假设我们定义vector<unsigned int> a,则 第i位可表示为a[i/32]的i%32位(其中,32*N+r = i,r为i%32,也就是i/32的余数)。

由于计算机对位的操作比乘除法更有效率,这里计算i/32可以用位移操作:i>>5;计算i%32可以用1&31

若是一个char数组str,则str的第i位为i/8(i>>3)地址块的第i%8(i&7)位.下面以char为例说明,int类比可知。

#include<iOStream>
#include<string>
#include<stdlib.h>
using namespace std;
class BitMap{
private:
        char *bitmap;
        int gsize;
public:
       BitMap(){
       gsize=(10000>>3)+1;//default 10000
       bitmap= new char[gsize];
       memset(bitmap,0,sizeof(bitmap));
                }
       BitMap(int n){
       gsize=(n>>3)+1;
       bitmap=new char[gsize];
       memset(bitmap,0,sizeof(bitmap));
                  }
       ~BitMap(){delete []bitmap;}
       int get(int x){
       int cur=x>>3;
       int red=x&7;
       if(cur>gsize)return -1;
       return (bitmap[cur]&=1>>red); 
                      }
       bool set(int x){
       int cur=x>>3;//获取元素位置,除8得到哪个元素,x/2^3得到那一个byte 
       int red=x&(7);//逻辑与,获取进准位置,x&7==x%8.该Byte里第几个 
       if(cur>gsize)return 0;
       bitmap[cur]|=1>>red;//赋值,1向右移动red位,|表示该位赋值1
       return 1; 
                       }
};

以上为个人经验,希望能给大家一个参考,也希望大家多多支持编程网。

--结束END--

本文标题: C++如何实现BitMap数据结构

本文链接: https://lsjlt.com/news/165019.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

猜你喜欢
  • C++如何实现BitMap数据结构
    目录一、BitMap位图二、C++实现分治,分布式。BitMap(位图)及其升级版bloom filter是处理海量数据常用的方法,这里先介绍BitMap概念及其c++实现。 一、B...
    99+
    2024-04-02
  • Python: 实现bitmap数据结构
    http://my.oschina.net/goal/blog/200347  bitmap是很常用的数据结构,比如用于Bloom Filter中、用于无重复整数的排序等等。bitmap通常基于数组来实现,数组中每个元...
    99+
    2023-01-31
    数据结构 Python bitmap
  • [Python]数据结构--Bitmap
    ‘Festinatione facit vastum’ Bitmap简介 Bitmap的实现和使用 Bitmap简介 bitmap是很常用的数据结构,比如用于Bloom Filter中、用于无重复整数的排序等等。bit...
    99+
    2023-01-31
    数据结构 Python Bitmap
  • C++数据结构之AVL树如何实现
    这篇文章主要讲解了“C++数据结构之AVL树如何实现”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“C++数据结构之AVL树如何实现”吧!1.概念(1)二叉搜索树的缺点要手撕AVL树,我们首先...
    99+
    2023-07-02
  • C++如何实现数据结构的顺序表
    这篇文章给大家分享的是有关C++如何实现数据结构的顺序表的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。代码1.SeqList.h#ifndef SEQLIST_H#define SEQLIST...
    99+
    2023-06-25
  • C++数据结构之单链表如何实现
    这篇文章主要介绍了C++数据结构之单链表如何实现的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇C++数据结构之单链表如何实现文章都会有所收获,下面我们一起来看看吧。一、单链表的定义线性表的链式存储又称为单链表,...
    99+
    2023-06-30
  • C++数据结构之哈希表如何实现
    本篇内容主要讲解“C++数据结构之哈希表如何实现”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“C++数据结构之哈希表如何实现”吧!哈希表概念二叉搜索树具有对数时间的表现,但这样的表现建立在一个假...
    99+
    2023-07-05
  • go数据结构和算法BitMap原理及实现示例
    目录1. BitMap介绍如何判断数字在bit数组的位置设置数据到bit数组从bit数组中清除数据数字是否在bit数组中2. Go语言位运算左移右移使用&^和位移运算来给某一...
    99+
    2024-04-02
  • Golang如何实现数据结构Stack
    本文小编为大家详细介绍“Golang如何实现数据结构Stack”,内容详细,步骤清晰,细节处理妥当,希望这篇“Golang如何实现数据结构Stack”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。介绍Stack在计...
    99+
    2023-07-06
  • 数据库如何使用C++数据结构
    本篇文章为大家展示了数据库如何使用C++数据结构,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。在编写代码时,堆栈是最常用的C++数据结构,它的概念简单,编写也比较简单,现在举这么个例子,桌子上有堆成...
    99+
    2023-06-17
  • java如何实现队列数据结构
    小编给大家分享一下java如何实现队列数据结构,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!什么是队列结构一种线性结构,具有特殊的运算法则【只能在一端(队头)删除...
    99+
    2023-05-30
    java
  • C++数据结构之AVL树的实现
    目录1.概念(1)二叉搜索树的缺点(2)定义节点2.插入(1)拆分(2)找节点与插节点(3)更新平衡因子与旋转3.判断4.完整代码及测试代码完整代码测试代码1.概念 (1)二叉搜索树...
    99+
    2024-04-02
  • 如何进行数据结构C语言链表的实现
    这篇文章将为大家详细讲解有关如何进行数据结构C语言链表的实现,文章内容质量较高,因此小编分享给大家做个参考,希望大家阅读完这篇文章后对相关知识有一定的了解。前言需要用到的函数库#include<stdio.h>#include&...
    99+
    2023-06-22
  • 如何在 C++ 函数中实现线程安全的数据结构?
    如何在 c++++ 函数中实现线程安全的数据结构?使用互斥锁保护临界区(共享数据)。线程安全的动态数组示例:使用互斥锁保护 std::vector 中的数据。实战案例:线程安全的队列,使...
    99+
    2024-04-27
    c++ 线程安全 并发访问
  • javascript中如何实现队列数据结构
    这篇文章主要介绍javascript中如何实现队列数据结构,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!javascript是一种什么语言javascript是一种动态类型、弱类型的语言,基于对象和事件驱动并具有相对...
    99+
    2023-06-14
  • java如何实现队列queue数据结构
    这篇文章主要介绍java如何实现队列queue数据结构,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!概念队列是一种非原始(特殊)的线性表,是一种先进先出(FIFO)的数据结构。它只允许在表的前端(front)进行删除...
    99+
    2023-06-29
  • Java语言如何实现数据结构栈
    这篇文章主要介绍了Java语言如何实现数据结构栈,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。首先了解下栈的概念:栈是限定仅在表头进行插入和删除操作的线性表。有时又叫LIFO...
    99+
    2023-05-30
    java
  • redis底层数据结构如何实现的
    Redis 底层数据结构的实现 redis 是一种内存中的数据结构存储,它使用高效的数据结构来实现各种数据类型。这些底层数据结构包括: 1. 哈希表(Hash Table) 哈希表用于存...
    99+
    2024-06-12
    redis 键值对
  • C++数据结构之单链表的实现
    目录一、单链表的定义二、单链表的基本操作的实现1.初始化2.取值3.查找4.插入5.删除三、完整代码四、测试一下代码一、单链表的定义 线性表的链式存储又称为单链表,它是指通过一组任意...
    99+
    2024-04-02
  • C#数据结构与队列怎么实现
    这篇文章主要讲解了“C#数据结构与队列怎么实现”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“C#数据结构与队列怎么实现”吧!C#数据结构与算法之队列是一种特殊的线性表,它只允许在表的前端(f...
    99+
    2023-06-18
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作