C++语法中bitset位图介绍及模拟实现

这篇具有很好参考价值的文章主要介绍了C++语法中bitset位图介绍及模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、位图的引入

先来看下边一道面试题:

给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。

经过我们之前的学习,我们可能会有以下的思路:

  • 对这些数进行排序,再通过二分算法,查找这个数是否存在

  • 插入到unordered_set中,使用find函数查找是否存在

上述方法看起来还不错,二分查找算法时间复杂度为logN,而插入到unordered_set中时间复杂度为O(N),而查找时时间复杂度为O(1),但是都有一个问题就是要将空间不足,40亿个无符号整形,需要160亿字节的空间,大概就是16GB的空间,一般计算机的内促都是4G或者8G,所以空间不足,此时就有了位图的方法来解决:

数据是否在给定的整形数据中,结果是在或者不在,刚好是两种状态,那么可以使用一个二进制比特位来代表数据是否存在的信息,如果二进制比特位为1,代表存在,为0代表不存在。比如:

C++语法中bitset位图介绍及模拟实现,C语言教程,c++,java,面试

对于上图来说,有一个整形数组,我们可以使用直接定址法对数组的数据进行映射,但是与之前不同的是,此时只是使用一个比特位来代表一个整形数据,当这个数存在时,比特位置1,不存在时,比特位置0,此时就可以大大节省空间资源,无符号整数只有2的32次方个,所以最多开2的32次方个空间,一个空间为一个比特,所以最终只需要512MB的空间。但是我们不能按照位来空间,最少必须一个字节,所以我们就每次开一个字节的空间,也就是8个比特位,将8位当做一个整体来处理,对要保存的数据除8就是第几个字节,对保存的数据模8就是在这个字节中的第几个位置。

二、位图的概念

所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的。

那么位图还有哪些应用呢?

  • 快速查找某个数据是否在一个集合中

  • 排序 + 去重

  • 求两个集合的交集、并集等

  • 操作系统中磁盘块标记

位图模拟实现

一、构造函数

由于不能按位开空间,所以我们选择每次开一个字节的空间,由于有范围最大为N,一位关联一个数据,所以需要开N/8个字节的空间,但是有时可能不能整除,所以要开N/8+1个字节的空间。所以

直接在构造函数中开好空间:

bitset()
		{
			_bits.resize(N / 8 + 1,0);
		}

二、set,reset,test函数

set函数的作用是对位图中的某一位进行填充

i就表示是第几个字节,而j表示该位在该字节中的第几位,所以对1进行左移j位后与该字节按位或,按位或的作用时不论该位为0还是为1,都将该位变为1。

C++语法中bitset位图介绍及模拟实现,C语言教程,c++,java,面试

void set(size_t x)
		{
			int i = x / 8;
			int j = x % 8;
			_bits[i] |= (1 << j);
		}

reset的作用是将某一位清空

同样的将要清空的那一位置为0,进行按位与,不论原本该位是0还是1,都将该位置0

C++语法中bitset位图介绍及模拟实现,C语言教程,c++,java,面试

void reset(size_t x)
		{
			int i = x / 8;
			int j = x % 8;
			_bits[i] &= ~(1 << j);
		}

test的作用是检测位图中某一位是否存在

C++语法中bitset位图介绍及模拟实现,C语言教程,c++,java,面试

bool test(size_t x)
		{
			int i = x / 8;
			int j = x % 8;
			return _bits[i] & (1 << j);
		}

三、代码测试

void test_bit_set1()
	{
		bitset<100> bs1;
		bs1.set(8);
		bs1.set(9);
		bs1.set(20);
		cout << bs1.test(8) << endl;
		cout << bs1.test(9) << endl;
		cout << bs1.test(20) << endl;
		bs1.reset(8);
		bs1.reset(9);
		bs1.reset(20);
		cout << bs1.test(8) << endl;
		cout << bs1.test(9) << endl;
		cout << bs1.test(20) << endl;
	}

C++语法中bitset位图介绍及模拟实现,C语言教程,c++,java,面试文章来源地址https://www.toymoban.com/news/detail-645496.html

四、完整代码

namespace tmt
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			_bits.resize(N / 8 + 1,0);
		}
		void set(size_t x)
		{
			int i = x / 8;
			int j = x % 8;
			_bits[i] |= (1 << j);
		}
		void reset(size_t x)
		{
			int i = x / 8;
			int j = x % 8;
			_bits[i] &= ~(1 << j);
		}
		bool test(size_t x)
		{
			int i = x / 8;
			int j = x % 8;
			return _bits[i] & (1 << j);
		}
	private:
		vector<char> _bits;
	};
	void test_bit_set1()
	{
		bitset<100> bs1;
		bs1.set(8);
		bs1.set(9);
		bs1.set(20);
		cout << bs1.test(8) << endl;
		cout << bs1.test(9) << endl;
		cout << bs1.test(20) << endl;
		bs1.reset(8);
		bs1.reset(9);
		bs1.reset(20);
		cout << bs1.test(8) << endl;
		cout << bs1.test(9) << endl;
		cout << bs1.test(20) << endl;
	}

到了这里,关于C++语法中bitset位图介绍及模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】——string类的介绍及模拟实现

    C语言中,字符串是以’\\0’结尾的一些字符的集合,为了操作方便,C标准库中提供了一些str系列的库函数,但是这些库函数与字符串是分离开的,不太符合OOP的思想,而且底层空间需要用户自己管理,稍不留神可能还会越界访问。所以我们今天来学习C++标准库中的string类。

    2024年02月07日
    浏览(55)
  • [C++历练之路]vector的介绍以及底层模拟实现

    W...Y的主页 😊 代码仓库分享 💕 🍔前言: 我们学习了STL中的string以及其所有重要接口并进行了模拟实现,但是STL中包含的内容不止于此。学习了string之后继续学习STL中的vector,学习成本会大大降低,因为他们非现类似,现在就让我们进入vector的世界中吧! 目录 vector的介绍

    2024年02月04日
    浏览(42)
  • stack 、 queue的语法使用及底层实现以及deque的介绍【C++】

    stack是一种容器适配器,具有后进先出,只能从容器的一端进行元素的插入与提取操作 队列是一种容器适配器,具有先进先出,只能从容器的一端插入元素,另一端提取元素 stack和queue在STL中并没有将其划分在容器的行列,而是称为容器适配器 因为stack和queue对其他容器的接口

    2024年02月12日
    浏览(43)
  • 【C++】容器篇(三)—— stack的基本介绍及其模拟实现

    前言: 在之前的学习中我们已经了解了 vector 和 list ,今天我将带领学习的是关于STL库中的 stack的学习!!! 目录 (一)基本介绍 1、基本概念  2、容器适配器 (二)基本使用 (三)stack模拟实现 1、stack的使用 2、 模拟实现 (四)题目讲解 1、逆波兰表达式求值 (五)总

    2024年02月06日
    浏览(47)
  • 【C++】容器篇(四)—— queue的基本介绍以及模拟实现

    前言: 在上期博文中我带大家对stack进行深入的学习,本期我将带领学习的是关于 queue的基本知识,并且还将给大家介绍并实现  priority_queue。接下来,让我们正式本期的内容。 目录 (一)queue的基本介绍 (二)基本使用 (三)模拟实现 (四)priority_queue的基本介绍 (五)

    2024年02月08日
    浏览(45)
  • [C++]priority_queue的介绍及模拟实现

    目录 priority_queue的介绍及模拟实现::                                                         priority_queue的介绍                                                         priority_queue的定义方式                 

    2024年02月04日
    浏览(43)
  • C语言字串函数、内存函数介绍以及模拟实现

        目录 前言 本期内容介绍: 一、字符串函数 strlen介绍 strlen 模拟实现(三种方式) 方法一:计数器法  方法二:递归法(不创建临时变量法) 方法三:指针-指针 strcpy介绍 strcpy模拟实现 ​编辑strcmp介绍 strcmp模拟实现 strcat介绍 strcat模拟实现 strncpy介绍 strncpy模拟实现 s

    2024年02月14日
    浏览(39)
  • 【C++】list的介绍及使用 | 模拟实现list(万字详解)

    目录 一、list的介绍及使用 什么是list? list的基本操作 增删查改 获取list元素 不常见操作的使用说明 ​编辑 接合splice ​编辑 移除remove 去重unique 二、模拟实现list 大框架 构造函数 尾插push_back 迭代器__list_iterator list的迭代器要如何跑起来 iterator的构造函数 begin()与end() opera

    2024年02月06日
    浏览(48)
  • [C++] string类的介绍与构造的模拟实现,进来看吧,里面有空调

    C语言中,字符串是以’\\0’结尾的一些字符的集合,为了操作方便,C标准库中提供了一些str系列的库函数,但是这些库函数与字符串是分离开的,不太符合面向对象的思想,而且底层空间需要用户自己管理,稍不留神可能还会越界访问。 因此C++中,为了让我们更简单、方便

    2024年02月12日
    浏览(38)
  • 【C语言】字符函数和字符串函数(一)—>库函数的介绍与模拟实现

    目录 前言: 一、函数介绍: (一)求字符串长度 (1)strlen (二)长度不受限制的字符串函数 (2)strcpy (3)strcat (4)strcmp (三)长度受限制的字符串函数 (5)strncpy (6)strncat (7)strncmp (四)字符串查找 (8)strstr (9)strtok (五)错误信息报告 (10)strerror (六)

    2024年02月15日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包