Sweet Snippet 系列之 有序列表

工作中常常遇到需要使用有序列表的情况,这篇文章简单讨论一下相关实现(以 C# 中的 List<T> 为例)

使用 List<T>.Sort

很朴素的一种想法,为了维持 List 有序,我们可以在 Add 操作之后进行 Sort 操作(Remove 操作后不需要重新 Sort):

list.Add(value);
list.Sort();

该方案的缺点是时间消耗比较大,每次 Add 操作之后都要执行费时的 Sort 操作

借助平台库中的 SortedList<Tkey, TValue> etc.

使用平台库内建的 SortedList<Tkey, TValue>,我们可以立即实现有序列表功能,这也应该是我们大部分情况下的选择,稍有缺陷的是,平台库中的 SortedList 需要指定 TKey 和 TValue,这在存储非映射类数据时(譬如存储单一的 int 数值)显得有些内存浪费~ (类似的还有 SortedDictionary<TKey, TValue>)

那 SortedSet<T> 怎么样?

比起内部使用数组实现的 List 而言,目前默认使用红黑树实现的 SortedSet 会有更多的内存消耗,而且也不提供索引形式的访问,不过在插入和删除操作上,他更有时间优势~

其实我们可以自己封装

基于 List 有序这个前提,每次进行 Add 时,我们可以使用插入排序来添加元素,这样我们便可以省去之后的 Sort 操作,而 List 本身提供的 BinarySearch(二分查找)功能正好可以帮助我们实现插入排序~

// simple sorted list implementation using insert sort
// maintainer hugoyu

using System.Collections.Generic;

namespace Util
{
    public class SortedList<T>
    {
        public SortedList(IComparer<T> comparer = null)
        {
            m_comparer = comparer;
        }

        public int Count
        {
            get
            {
                return m_elementList.Count;
            }
        }

        public T this[int index]
        {
            get
            {
                return m_elementList[index];
            }
        }

        public bool Contains(T item)
        {
            return m_elementList.BinarySearch(item, m_comparer) >= 0;
        }

        public void Add(T item)
        {
            var index = m_elementList.BinarySearch(item, m_comparer);
            if (index < 0)
            {
                m_elementList.Insert(~index, item);
            }
            else
            {
                m_elementList.Insert(index, item);
            }
        }

        public bool Remove(T item)
        {
            var index = m_elementList.BinarySearch(item, m_comparer);
            if (index >= 0)
            {
                m_elementList.RemoveAt(index);
                return true;
            }

            return false;
        }

        public void Clear()
        {
            m_elementList.Clear();
        }

        IComparer<T> m_comparer;
        List<T> m_elementList = new List<T>();
    }
}

完整的代码在这里(gist)


软件开发的核心就是权衡,下次如果你需要使用有序列表,会选择怎么实现呢?

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏XAI

百度人脸识别API Java调用

工具类下载http://pan.baidu.com/s/1jIuo0N8 小Demo查询。 1.官网文档必须看 http://ai.baidu.com/docs...

2.4K110
来自专栏二进制文集

Java 生产者消费者实现

chef 在 有 meal 的时候,会释放锁;在制作 meal 时,会获取 waitPerson 的锁,制作完 meal 后,唤醒所有的 waitPerson;

41740
来自专栏c#开发者

Winform 的一个多线程绑定DataGrid数据源的例子

我们都知道简单的运用多线程的方法有 1/ Thread thread=new Thread(new StartThread(this.method))     ...

31990
来自专栏草根专栏

使用两种方法让 ASP.NET Core 实现遵循 HATEOAS 结构的 RESTful API

HATEOAS(Hypermedia as the engine of application state)是 REST 架构风格中最复杂的约束,也是构建成熟 ...

596110
来自专栏.NET后端开发

ADO.NET入门教程(七) 谈谈Command对象高级应用

摘要 在上一篇文章《你必须知道的ADO.NET(六) 谈谈Command对象与数据检索》中,我详细讲解了Command对象的基础知识以及基本用法。作为ADO.N...

54090
来自专栏Kiba518

C#线程安全使用(四)

这是时隔多年第四篇,主要是因为身在东软受内网限制,好多文章就只好发到东软内部网站,懒的发到外面,现在一点点把在东软写的文章给转移出来。

9730
来自专栏大内老A

我的WCF之旅(7):面向服务架构(SOA)和面向对象编程(OOP)的结合——如何实现Service Contract的继承

当今的IT领域,SOA已经成为了一个非常时髦的词,对SOA风靡的程度已经让很多人对SOA,对面向服务产生误解。其中很大一部分人甚至认为面向服务将是面向对象的终结...

20150
来自专栏跟着阿笨一起玩NET

AutoResetEvent.WaitAll 等到人生三大事,然后大笑开心。

例子描述:人生都有追求幸福理想,下面就用三条线程得到房子,车子,妻子,等待全部得到后,显示人生圆满。

29420
来自专栏GIS讲堂

一个GISER 6.7的祝福

一年一度的高考今天开始了,回想10年前,那是我第一次高考;10年后,作为一个GISER,在此给大家献上一个GISER的祝福,祝愿各位考生:考神附体,考完报考GI...

15840
来自专栏技术博客

C# XML与Json之间的相互转换

对于这转换其实很简单,其中最重要的就是先要引用类库。可以到官网进行下载引用http://json.codeplex.com。

62530

扫码关注云+社区

领取腾讯云代金券