C#有类似C std :: equal_range的东西吗？

发布时间：2020-12-15 23:29:20 所属栏目：百科来源：网络整理

导读：我一直在寻找,并没有真正找到答案.说实话,我认为在互联网上使用这个功能确实有一些信息.对于我来说,引用本身不够清晰,无法在C#中找到等价物. 我必须将C类移植到C#.旧的C类在某一点上使用了这个函数,我使用了由可枚举对象提供的Where()替换了LinQ的用法： std

我一直在寻找,并没有真正找到答案.说实话,我认为在互联网上使用这个功能确实有一些信息.对于我来说,引用本身不够清晰,无法在C#中找到等价物.

我必须将C类移植到C#.旧的C类在某一点上使用了这个函数,我使用了由可枚举对象提供的Where()替换了LinQ的用法：

std::equal_range(it_begin,it_end,value,comparer)
//changes to
list.Where(/*some comparison using the same comparison logic and the value like C++ version*/)

不幸的是,我没有像原始代码那样得到相同的范围.所以我想知道我是否用正确的等价替换了C -Method,或者我的比较代码中是否有一些逻辑错误.

那么C#中std :: equal_range的正确等价是什么？我的解决方案是正确的还是完全不同的东西？

编辑：

感谢您提示向C函数说些什么.

第一个here是文档

毕竟,据我所知,我返回一个列表范围,其中包含与给定值类似的所有值.用户可以提供一个比较器,我不完全确定它的用途：
? – 将列表中的值与给定值进行比较？
? – 比较排序结果？

EDIT2：

我的不同结果的原因位于其他地方.所以考虑到复杂性标准,我接受了Matthews的回答.尽管考虑到结果,所有3种解决方案(Matthews,Renés和我的)都能提供相同的结果.因此,如果性能无关紧要和/或希望减少代码,可能其他一种解决方案对您来说也没问题.

解决方法

你可以用二进制搜索解决这个问题.

这实际上是与equal_range()相同的实现,因此具有相同的~O复杂度(Log2(N)：

(Implementation of lower and upper bound stolen from here…)

using System;
using System.Collections.Generic;

namespace Demo
{
    class Program
    {
        static void Main()
        {
            var values = new List<string>{"1","2","3","5","7","8","9"};

            test(values,"5");
            test(values,"-");
            test(values,"A");
            test(values,"4");
            test(values,"6");
        }

        public static void test<T>(IList<T> values,T target) where T: IComparable<T>
        {
            var range = EqualRange(values,target);
            Console.WriteLine($"Range for {target} is [{range.Item1},{range.Item2})");
        }

        public static Tuple<int,int> EqualRange<T>(IList<T> values,T target) where T : IComparable<T>
        {
            int lowerBound = LowerBound(values,target,values.Count);
            int upperBound = UpperBound(values,lowerBound,values.Count);

            return new Tuple<int,int>(lowerBound,upperBound);
        }

        public static int LowerBound<T>(IList<T> values,T target,int first,int last) where T: IComparable<T>
        {
            int left  = first;
            int right = last;

            while (left < right)
            {
                int mid = left + (right - left)/2;
                var middle = values[mid];

                if (middle.CompareTo(target) < 0)
                    left = mid + 1;
                else
                    right = mid;
            }

            return left;
        }

        public static int UpperBound<T>(IList<T> values,int last) where T : IComparable<T>
        {
            int left  = first;
            int right = last;

            while (left < right)
            {
                int mid = left + (right - left) / 2;
                var middle = values[mid];

                if (middle.CompareTo(target) > 0)
                    right = mid;
                else
                    left = mid + 1;
            }

            return left;
        }
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!