具有类似C++std::equal_range的C#

本文关键字：range equal C++std | 更新日期: 2023-09-27 18:26:23

我一直在搜索，但没有真正找到答案。老实说，我认为在互联网上使用这个功能的信息确实很少。引用本身还不够清楚，我无法在C#中找到等价的引用。

我必须将一个C++类移植到C#。旧的C++类曾经使用过这个函数，我使用Where（）用LinQ的用法替换了它，Where由可枚举对象提供：

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++方法，或者我的比较代码中是否有一些逻辑错误。

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

编辑：

感谢您对C++函数的提示。

首先是文件

毕竟，据我所知，我返回一个列表的范围，其中包含与给定值相似的所有值。用户可以在我不完全确定使用了什么的情况下提供比较器：-将列表中的值与给定值进行比较？-以比较排序后的结果？

第2版：

我得出不同结果的原因在其他地方。所以考虑到复杂性标准，我接受了Matthews的回答。尽管考虑到结果，所有3个解决方案（Matthews、Renés和我的）都提供了相同的结果。因此，如果性能无关紧要，并且/或者希望代码更少，那么也许其他解决方案之一对您来说是可以的。

具有类似C++std::equal_range的C#

您可以通过二进制搜索来解决此问题。

这本质上是一个与equal_range（）相同的实现，因此具有~O（Log2（N）:的相同复杂性

（实现从这里窃取的下限和上限…）

using System;
using System.Collections.Generic;
namespace Demo
{
    class Program
    {
        static void Main()
        {
            var values = new List<string>{"1", "2", "3", "5", "5", "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, 0, values.Count);
            int upperBound = UpperBound(values, target, 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, 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)
                    right = mid;
                else
                    left = mid + 1;
            }
            return left;
        }
    }
}

就我对std::equal_range的理解而言，这个扩展方法应该是等价的：

public static class CppExtensions
{
    public static IEnumerable<T> EqualRange<T>(this IEnumerable<T> source, T val, IComparer<T> comparer)
    {
        return source.EqualRange(val, comparer.Compare);
    }
    public static IEnumerable<T> EqualRange<T>(this IEnumerable<T> source, T val, Func<T, T, int> comp)
    {
        return source.SkipWhile(s => comp(s, val) < 0).TakeWhile(s => comp(s, val) == 0);
    }
}

测试程序：

test[] list =
{
    new test {a = 1, text = "a"},
    new test {a = 2, text = "b"},
    new test {a = 3, text = "c"},
    new test {a = 3, text = "d"},
    new test {a = 4, text = "e"}
};
IEnumerable<test> result = list.EqualRange(new test {a = 3, text = string.Empty}, (t1, t2) => t1.a.CompareTo(t2.a));
Console.WriteLine(string.Join(" ", result.Select(r => r.text)));

从而输出CCD_ 2。

相关文章：