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

Question

我一直在寻找并没有真正找到答案。说实话，我觉得网上关于这个功能的使用信息确实很少。该参考文献本身不够清晰，我无法在 C# 中找到等效的内容。

\n\n

我必须将 C++ 类移植到 C#。旧的 C++ 类曾一度使用此函数，我将其替换为使用Where() 的 LinQ 用法，该函数由可枚举对象提供：

\n\n

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

\n\n

不幸的是，我没有得到与原始代码相同的范围。所以我想知道我是否用正确的等效方法替换了 C++ 方法，或者我的比较代码中是否存在一些逻辑错误。

\n\n

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

\n\n

编辑：

\n\n

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

\n\n

首先这是文档

\n\n

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

\n\n

编辑2：

\n\n

我的不同结果的原因在于其他地方。因此，考虑到复杂性标准，我接受了马修斯的回答。尽管考虑到结果，所有 3 个解决方案（Matthews、Ren\xc3\xa9s 和我的）都提供了相同的结果。因此，如果性能并不重要和/或希望减少代码，也许其他解决方案之一适合您。

\n

Answer 1

您可以通过二分查找来解决这个问题。

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