故如虹,知恩;故如月,知明
排名
6
文章
6
粉丝
16
评论
8
{{item.articleTitle}}
{{item.blogName}} : {{item.content}}
ICP备案 :渝ICP备18016597号-1
网站信息:2018-2024TNBLOG.NET
技术交流:群号656732739
联系我们:contact@tnblog.net
欢迎加群交流技术

c#使用泛型实现一个自己的list

6087人阅读 2019/9/27 10:54 总访问:3839737 评论:0 收藏:0 手机
分类: .NET

实现一个自己list,实现微软自带list的常用功能,就是可以直接把list对象名换成自己的使用


例如:这里把MyList换成List效果一样

static void Main(string[] args)
{
    MyList<int> intlist = new MyList<int>();
    for (int i = 0; i < 8; i++)
    {
        intlist.Add(i);
    }
    //删除
    intlist.Remove(0);   
    Console.WriteLine("条数:" + intlist.Count);
    Console.WriteLine("容量:" + intlist.Capacity);
    //遍历
    for (int i = 0; i < intlist.Count; i++)
    {
      Console.WriteLine("item:" + intlist[i]);
    }
    //foreach遍历
    foreach (int item in intlist)
    {
      Console.WriteLine(item);
    }
}

效果

添加功能:

添加功能其实很简单,因为list里边是维护的一个数组,数组的长度是固定的,我们只需要在装满的时候进行扩容就行了,测试了一下微软自带list扩容规则是上一次的2倍,代码实现如下:

public void Add(T t)
{
    //当装不下的时候扩容
    int length = array.Length;
    if (index == length)
    {
        //创建一个新数组
        T[] temp = new T[length * 2];
        Array.Copy(array, temp, length);
        array = temp;
    }
    array[index] = t;
    index++;
}

这里扩容的代码放到index++下面也可以,不影响功能,只是如果放到下面index++之后,他装满会马上扩容,如果是放到上面刚好装满的情况不会扩容,要下一次来存储的时候发现存不下了才会扩容,这样效率会快一点,说的高大上一点就是延迟扩容,按需扩容


获取条数与容量:

这里我们就先弄成只读就好,外面无法修改,无法破坏我们的逻辑,这点在自己写框架什么的很非常重要哇。面向对象的三大特征的之一的封装

    //list条数
    public int Count
    {
        get
        {
            return index;
        }
    }
    //list容量
    public int Capacity
    {
        get
        {
            return array.Length;
        }
    }

删除功能:

因为list里边是维护的一个数组,删除功能也是对数组的一个操作

要做删除当然第一步就是找到需要删除元素的位置


  • 方法1:创建一个新的数组,然后把除了删除的元素复制到新数组去,也就是跳过需要删除的元素即可



方法1:分成删除前,删除后

//先把删除前面的装进来
for (int i = 0; i < index; i++)
{
    newArray[i] = array[i];
}
//然后把需要的跳过,把后面的数据装过来,这里循环长度使用实际存储来计算,不要使用数组的长度来,因为很有可能没有装满
for (int i = index; i < this.index - 1; i++)
{
    newArray[i] = array[i + 1];
}
array = newArray;


方法2:不用分删除前,删除后

public void Remove(T t)
{
    //需要删除的位置
    int poi = -1;
    for (int i = 0; i < Count; i++)
    {
        if (t.Equals(array[i]))
        {
            poi = i;
            break;
        }
    }
    if (poi == -1)
    {
        return;
    }
    //创建一个新数组
    T[] temp = new T[array.Length];
    for (int i = 0, j = 0; i < array.Length - 1; i++, j++)
    {
        //这个刚好是需要被删除
        /*可以这样理解,当i和poi没有相等的时候,i=j所以newArray[i] = array[j]就是直接相等,没有错位移动格子
         当i和poi相等的时候j就比i多1就相当于移动一格了。所以这个i和j是否相等就相当于方法1中分成的删除前和删除后的操作了
        */
        if (i == poi)
        {
            j++;
        }
        temp[i] = array[j];
    }
    array = temp;
    index--;
}
  • 方法3:其实没有必要创建一个新的数组,我们可以在当前这个数组上进行位置的改动,删除位置前不需要动后面的位置依次向前移动即可


 代码的话很简单一个Array.Copy即可搞定

public void Remove(T t)
{
    //找到需要删除的位置
    var poi = FindIndex(t);
    //参数解释:源数组,源数组开始位置 , 目标数组,目标数组开始位置,循环赋值次数
    Array.Copy(array, poi + 1, array, poi, index - poi - 1);
    //数组长度减一,因为删除了长度会减少一
    index--;
}

开始可以不使用Array.Copy可以自己使用循环来写,好理解一点

//循环的长度是数组的实际存储数量而不是总数,如果没有存储满,就会移动很多次,这样会浪费效率
for (int i = index; i < this.index - 1; i++)
{
    array[i] = array[i + 1];
}


这里发现了一个有趣的问题,就是我们依次向前移动后,最后一个位置的数组是否存在的问题,

比如list集合里边存储有1,2,3,4我们把3删除掉,4就会向3的位置移动变成了:1,2,4 

但是以前那个4会不会存在,会不会集合里边变成了1,2,4,4

我们正常的遍历肯定是没有问题的:

但是就是想测试一下后面那个元素,我们就用for循环,长度就是要加一个1,因为其实用户已经删除了一个

果然像我们推理的那样,然后我们有理由怀疑list本身会不会也是这样的,测试一下你就知道其实当你传递下标和list长度相同的时候就会报索引超出了长度,所以其实对于删除来说后面元素是什么值对使用根本不会有影响。

我们在自己的list实现一个取值下标超出问题。

public T this[int _index]
{
    get
    {
        if (_index >= index)
        {
            throw new Exception("索引超出了长度");
        }
        return array[_index];
    }
    set
    {
        array[index] = value;
        index++;
    }
}

但是呢,虽然移动后的数组对正常使用没有问题,但是还是想知道一下微软本身list里边维护的数组是否对这样的情况进行处理。正常情况下我们无法访问list中维护的私有数组,但是我们可以通过反射来。

static void Main(string[] args)
{
    List<int> intlist = new List<int>();
    for (int i = 1; i < 5; i++)
    {
        intlist.Add(i);
    }
    intlist.Remove(3);
    //反射获取list中私有字段
    var result = intlist.GetType().GetFields(BindingFlags.NonPublic | BindingFlags.Instance);
    int[] findArray = null;
    foreach (var item in result)
    {
        //找到list中维护的数组,不要问我怎么找到的,遍历看名字就知道了
        if (item.Name == "_items")
        {
            findArray = (int[])item.GetValue(intlist);
        }
    }
    foreach (int item in findArray)
    {
        Console.WriteLine(item);
    }
    Console.ReadLine();
}

输出如下:

微软果然严谨这种问题都处理了,微软估计是赋予了这个泛型的默认值,ok跟着大佬的步伐我们也去这样处理一下

public void Remove(T t)
{
    var poi = FindIndex(t);
    Array.Copy(array, poi + 1, array, poi, index - poi - 1);
    //处理移动最后一个的元素为该类型的默认值
    array[index-1] = default(T);
    index--;
}

就是这样一句:

array[index-1] = default(T);


ok我们把list换成我们自己的mylist试试,因为我自己写的list,里边维护的数组叫array所以也要修改一下

ok搞定研究点这种问题还是有点意思



实现删除一个范围RemoveRange:

代码如下,其实只要把删除功能做好,这个还是比较简单的

/// <summary>
/// 从开始位置删除一个范围
/// </summary>
/// <param name="begin">开始位置</param>
/// <param name="length">长度</param>
public void RemoveRange(int begin, int length)
{
    //删除0个无意义
    if (length == 0)
        return;

    //循环次数应该等于Count - length,因为删除一个的时候是Count - 1,后面这个1就是删除长度,那删除Length个自然就是Count - length了
    for (int i = begin; i < Count - length; i++)
    {
        //删除需要跳格应该等于i+length,如果是删除一个就应该只是跳一格,也就是 array[i] = array[i + 1];
        array[i] = array[i + length];
    }

    //删除的长度要减去删除的长度,如果是删除一个就是index = index-1即可
    index = index - length;
}

批量删除功能RemoveAll:

当list集合中有重复的时候进行删除,其实也很简单,真正的核心是根据下标删除,这些删除只是调用核心的删除方法而已

public void RemoveAll(T t)
{
    for (int i = 0; i < Count; i++)
    {
        if (array[i].Equals(t))
        {
            RemoveAt(i);
        }
    }
}


资源下载地址:https://download.tnblog.net/resource/index/8965edcfbdd2437293fbc9d546b2c00c


欢迎加群讨论技术,群:677373950(满了,可以加,但通过不了),2群:656732739

评价