c++ - 如何以有效的方式以特定方式将 vector 与数组进行比较？

Question

假设元素的顺序不同，我想将 vector 与数组进行比较。 我有一个如下所示的结构(这个结构没有“operator==”和“operator<”-> 所以我不能使用排序):

struct A
{
    int index;
    A(int p_i) : index(p_i) {}
};

vector 和数组的大小是一样的:

std::vector<A> l_v = {A(1), A(2), A(3)};
A l_a[3] = {A(3), A(1), A(2)};

我正在寻找来自 std 的一些函数，例如下面的“some_function_X”，它可以使用 lambda 以特定方式找到元素，或者只能比较特定字段的函数，如“lhs.index == rhs.index” -> 按特定字段在没有“operator==”和“operator>”等的类中

bool checkIfTheSame(const std::vector<A>& l_v, const A& l_a)
{
    for(usigned int i=0; i< 3; ++i)
    {
        if(!std::some_function_X(l_v.begin(), l_v.end(), l_a, 
                              [](const A& lhs, const A& rhs){
                                 return lhs.index == rhs.index;
                              })) return false;
    }
    return true;
}

谢谢。

Answer 1

this struct hasn't got "operator==" and "operator<" -> so I can't use sort

首先，只有operator<是必须的。其次，它不必定义为成员函数。以下免费功能适用于 std::less (如果您不传递用于比较的仿函数，则 std::sort 会使用它)。

bool operator<(const A& a, const A& b) {...}

或者，您可以使用自定义比较仿函数代替 std::less .

对数组和 vector 进行排序然后进行比较应该具有更好的渐近运行时复杂度，而不是简单地迭代一个并使用线性搜索检查元素是否存在于另一个中。

另一个想法是只对其中一个进行排序，迭代无序并使用二进制搜索测试排序容器中的存在性。这与对两者进行排序具有相同的渐近复杂性。

如果你不能修改任何一个容器，那么你可以制作一个拷贝进行排序。这会消耗一些内存，但仍然比普通方法渐进地快。 std::partial_sort_copy直接排序到文案可以省几份。