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++函数的内容。

首先，在这里是文档。

总之，据我所知，它返回一个列表范围，该范围包含所有类似于给定值的值。用户可以提供一个比较器，我不完全确定这是用于什么： -将列表中的值与给定值进行比较？ -为了比较排序结果？

编辑2：

我得到不同结果的原因是在其他地方。因此，考虑到复杂性标准，我接受了Matthew的答案。虽然考虑到结果，Matthews、Renés和我的三个解决方案都提供了相同的结果。因此，如果不需要性能和/或希望使用较少的代码，则可能其中一个解决方案对您来说是可以的。

- Onsokumaru

---

如果您能花些时间详细介绍一下equal_range的作用，对C#受众会很有帮助。 - Bathsheba

equal_range 的文档 - Borgleader

Answer 1

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

这本质上是equal_range()的相同实现，因此具有相同的复杂度~O(Log2(N))：

（lower和upper bound的实现从这里借鉴...）

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;
        }
    }
}

- Matthew Watson

---

不幸的是，这个解决方案提供了与我的解决方案相同的结果。我将进一步调查出了什么问题或者我的问题原因是否在其他地方，并更新我的初始帖子。 - Onsokumaru

@Onsokumaru 我相信这与C++实现是相同的。你能否发布一些示例代码，显示你的集合、目标值、期望结果和实际结果？ - Matthew Watson

就在你发表评论的那一刻，我正在思考如何“关闭”这个问题。你的代码与René和我的代码相同。所有三种解决方案都提供了相同的结果。最后，我发现我的代码在另一个地方有一个错误，这与equal_range无关。我正在考虑将此作为维基问题，因为所有3个解决方案似乎都是正确的等效解？ - Onsokumaru

@Onsokumaru 我认为 equal_range() 的一个重要标准是它具有 O(Log2(N)) 的复杂度。因此，尽管结果可能相同，但只有我的版本具有正确的复杂度。在大型集合上，你会真正注意到差异！ - Matthew Watson

Answer 2

就我所知，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)));

这将输出c d。

- René Vogt

---

（如果忽略复杂度要求） - Ben Voigt

@BenVoigt 我承认我没有关注复杂度（如果这种方法经常使用或用于大数据，那么肯定应该这样做）。OP没有明确要求它，而且我也不知道 std::equal_range 的复杂度。我认为我的代码很简单直接，聪明的人肯定会找到很多性能改进的方法。 - René Vogt

不幸的是，这个解决方案提供了与我的解决方案相同的结果。我将进一步调查出了什么问题或者我的问题原因是否在其他地方，并更新我的初始帖子。 - Onsokumaru