c# - C# 有类似于 C++ std::equal_range 的东西吗？

Question

我一直在寻找，并没有真正找到答案。老实说，我觉得网上关于这个功能的使用信息真的很少。引用本身不够清晰，我无法在 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++ 方法，或者我的比较代码中是否存在一些逻辑错误。

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

编辑:

感谢提示对 C++ 函数说些什么。

第一个here是文档

据我所知，我返回了一个列表范围，其中包含与给定值相似的所有值。用户可以提供一个比较器，我不能完全确定它的用途: - 将列表中的值与给定值进行比较？ - 比较排序结果？

编辑2:

我的不同结果的原因位于其他地方。因此，考虑到复杂性标准，我接受了 Matthews 的回答。尽管考虑到结果，所有 3 个解决方案(Matthews、Renés 和我的)都提供了相同的结果。因此，如果性能无关紧要和/或希望代码更少，也许其他解决方案之一适合您。

Answer 1

你可以用二分查找来解决这个问题。

这本质上是与 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", "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;
        }
    }
}