Comparing a vector with an array assuming the elements are in different order

Question

I would like to compare a vector with an array assuming that elements are in different order. I have got a struct like below:

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

The size of the vector and the array is the same:

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

The function to compare elements is:

bool isTheSame()
{
    return std::equal(l_v.begin(), l_v.end(), l_a,
                      [](const A& lhs, const A& rhs){
                         return lhs.index == rhs.index;
                      });
}

The problem is that my function will return false, because the elements are the same, but not in the same order. A solution is to sort the elements in the vector and array before "std::equal", but is there any better solution?

If the index range is small, you may use something similar to [counting sort](http://en.wikipedia.org/wiki/Counting_sort) to have a `O(N)` algorithm instead of `O(log N)`. — Jarod42, May 21 '15 at 07:26
no, you have to sort both arrays. once you do you can just use operator== on the vectors themselves. — Richard Hodges, May 21 '15 at 07:28
Sort the array? Or create an array for each element and count how many times you see one in the other set. — Mats Petersson, May 21 '15 at 07:39
If one of the arrays is already sorted, you can do better than sorting + comparing by simply searching all elements of the non-sorted array in the sorted array using binary search. That'll be O(log(n)*n) instead of O(log(n)*n + n) (and yes I know, it's both the same Big-O, but one the first is still faster). — stefan, May 21 '15 at 07:45

score 0 · Answer 1 · edited May 23 '17 at 12:05

Using sort would be the way to go. Sorting in general is a good idea. And as far as I know it would result in the best performance.

Note: I would recommend passing the vectors as arguments. Rather than using the member variables. After doing that this would be a typical function that would be very well suited to inline. Also you might also want to consider taking it out of the class and/or making it static.

Comparing a vector with an array assuming the elements are in different order

1 Answers1