c# 用BitArray来管理包含关系

BitArray是.net自带的引用类型，在名称空间Systems.Collections下面。输入BitArray可以看到它的摘要：“管理位值的压缩数组，该值表示为布尔值，其中 true 表示位是打开的 (1)，false 表示位是关闭的 (0)”。

定义一个BitArray：

BitArray bitArr = new BitArray(10);
bitArr[3] = true;
bitArr[8] = true;

历遍bitArr的成员，可以看到结果为{false,false,false,true,false,false,false,false,true,false}.

BitArray由于引用类型的本质，可以重新设置大小。在结果数量不定而且总数可能大于32的情况下，比较适合用BitArray来管理包含关系。这里是相对BitVector32来讲的，BitVector32是值类型，而且固定大小32位，它具有数据处理更快的优点。可以根据实际情况来选择。对于这两种类型更多的解释，可以去msdn上查资料。

包含的管理主要包括三个方面：新增，删除，包含判断。

首先自定一个类，含有BitArray的私有字段，同时有Length的属性。

public struct FlagsBitArray
{
    BitArray _array;
    public int Length { get { return _array.Length; } }

    //构造函数
    public FlagsBitArray(int length)
    {
        _array = new BitArray(length);
    }
    //构造函数
    public FlagsBitArray(int[] arr)
    {
        if (arr == null) _array = new BitArray(0);
        else
        {
            var length = arr.Max();
            _array = new BitArray(length);
            AddFlag(arr);
        }
    }
}

可以将新增和删除理解成修改BitArray的相应索引处的bool值，新增改为true，删除改为false。

void ModifyFlag(int[] arr, bool value)
{
    if (arr == null) return;
    var max = arr.Max();
    if (max > _array.Length - 1)//如果提交的数字超出当前索引范围
        _array.Length = max + 1;
    foreach (var x in arr)
    {
        if (x >= 0) _array[x] = value;
        else throw new ArgumentException("负值无效");
    }
}

//加法
public void AddFlag(params int[] newArr) { ModifyFlag(newArr, true); }

//移除
public void RemoveFlag(params int[] newArr) { ModifyFlag(newArr, false); }

判断是否包含更加简单，只需要判断相应索引处的值是否为true。

//判断有没有
public bool HasFlag(int which)
{
    //超出范围，返回false
    if (which < 0 || which > Length - 1) return false;
    return _array[which];
}

 调用代码：

var list = new int[] { 0, 1, 2, 3, 5, 8, 25, 30 };
var arr = new FlagsBitArray(list);
Console.WriteLine("包含25？" + arr.HasFlag(25));
Console.WriteLine("包含20？" + arr.HasFlag(20));
arr.AddFlag(10, 11, 12, 8, 32);
Console.WriteLine(arr.Length);

包含关系的管理，可以用很多方法。List集合、枚举的HasFlag、二进制与运算、BitVector32、BitArray等等。

list集合属于最基本的方法，它可以实现添加删除和包含判断，但是数据的存储和处理时内存的开销较大；

枚举的HasFlag和二进制与运算，以及BitVector32，它们的优点是数据的存储和内存开销较小。但都存在着Int位数限制的问题，枚举和二进制与运算可以通过long和BigInteger来处理，但总体不太灵活。在32位范围内，这三者都是比较有优势的。

BitArray在长度上面比较占优势，可以无限扩充，这样的优势势必会拖累它的运算速度和内存开销，但是，BitArray里面包含了一个Int数组，每32位使用一个新整数。也就是说它占用的空间也是根据所包含的数据长度来调节的，所以整体影响应该不大。

扩充类下面的一些其他函数： 

//还原包含的int集合
public List<int> GetIntList()
{
    List<int> res = new List<int>();
    for (int i = 0; i < _array.Length; i++)
        if (_array[i]) res.Add(i);
    return res;
}

//如果Length很大的时候，而且string需要存储到数据库时，可以考虑压缩算法。
public override string ToString()
{
    StringBuilder sb = new StringBuilder(this.Length) { Length = this.Length };
    for (int i = 0; i < this.Length; i++)
        sb[i] = this._array[i] ? '1' : '0';
    return sb.ToString();
}

//FlagsBitArray与String的转换
public static implicit operator string(FlagsBitArray bitArr)
{
    return bitArr.ToString();
}

//String与FlagsBitArray的隐式转换
public static implicit operator FlagsBitArray(string str)
{
    FlagsBitArray res = new FlagsBitArray(str.Length);
    for (int i = 0; i < str.Length; i++)
        res._array[i] = str[i] == '1';
    return res;
}

源代码

转载请注明出处：http://www.cnblogs.com/icyJ/