0

I would like to compare a vector with an array assuming that elements are in different order. I have got a struct like below (this struct hasn't got "operator==" and "operator<" -> so I can't use sort):

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

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

I am looking for some function from std like below "some_function_X" which can find element in specific way using lambda, or function which can compare only specific field like "lhs.index == rhs.index" -> by specific field in class without "operator==" and "operator>" etc.

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

Thanks.

user2104552
  • 87
  • 1
  • 2
  • 9

4 Answers4

3

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

Firstly, only operator< is required. Secondly, it doesn't have to be defined as a member function. The following free function works with std::less (which is what std::sort uses if you don't pass a functor for comparison).

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

Or, you can use a custom comparison functor instead of std::less.

Sorting the array and the vector and then comparing should have better asymptotic runtime complexity than trivially iterating one and checking if the element exists in the other using linear search.

Another idea would be to sort only one of them, iterate the unordered and test the existence in sorted container with binary search. That has same asymptotic complexity as sorting both.

If you can't modify either container, then you can make a copy for sorting. That costs some memory, but is still asymptotically faster than the trivial approach. std::partial_sort_copy can save you a few copies by sorting directly to the copy.

eerorika
  • 232,697
  • 12
  • 197
  • 326
  • I fully agree with you with sorting, but I can't modify the container. Making the new container doesn't make sense I think. – user2104552 May 21 '15 at 13:03
  • @user2104552, what container do you mean? You do not need to modify your `struct A` to use custom compare function. – Petr May 21 '15 at 13:05
  • @user2104552 If you can't modify either container and neither of them are sorted, then coping the container for sorting makes sense if asymptotic speed is more important than memory usage. If memory usage is more important than speed, then stick to the trivial approach of iterating unsorted container and searching linearly. – eerorika May 21 '15 at 13:08
1

look here : http://www.cplusplus.com/reference/algorithm/

find with lambda expression find if

function which can compare only specific field like "lhs.index == rhs.index" -> by specific field in class without "operator==" and "operator>" etc.

to check if your 2 containers contains same datas with a predicate : equal with a custom predicate

if you just want to check if your container container a specific value, have a look here : How to find if an item is present in a std::vector?

Community
  • 1
  • 1
X3liF
  • 1,054
  • 6
  • 10
  • Yes I want to check only if my container contain a specific value, but I can't use this http://stackoverflow.com/questions/571394/how-to-find-an-item-in-a-stdvector because the struct A has no define operators. – user2104552 May 21 '15 at 12:43
0

I'm not sure I fully understand what you want but I'll take a guess that you want to check whether two arrays (which have different container types) are equivalent, that is for each item in array A there is a corresponding item somewhere in array B for which some predicate returns true.

You want to do this on two arrays that are not only of different types, but also possibly in a different order.

This is one way to do it:

struct Foo
{
    Foo(int i) : _index { i } {}

    int index() const {
        return _index;
    }
private:
    int _index;
};

// params:
// first1, last1 bound the first array
// first2, last2 bound the second array
// pred is a predicate that checks for equivalents
// order is a predicate that performs weak ordering
template<class Iter1, class Iter2, class Pred, class Order>
bool checkIfTheSame(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2, Pred pred, Order order)
{
    const auto len1 = last1 - first1;
    const auto len2 = last2 - first2;
    if (len1 != len2)
        return false;

    using namespace std;
    using item1_type = typename std::iterator_traits<Iter1>::value_type;
    using item2_type = typename std::iterator_traits<Iter2>::value_type;

    std::vector<std::reference_wrapper<item1_type>> refs1 { first1, last1 };
    std::sort(begin(refs1), end(refs1), order);

    std::vector<std::reference_wrapper<item2_type>> refs2 { first2, last2 };
    std::sort(begin(refs2), end(refs2), order);

    for (size_t i = 0 ; i < len1 ; ++i) {
        if (!pred(refs1[i], refs2[i]))
            return false;
    }

    return true;
}

simple example:

using namespace std;

bool same_indexes(const Foo& f1, const Foo& f2) {
    return f1.index() == f2.index();
}

bool sort_indexes(const Foo& f1, const Foo& f2) {
    return f1.index() < f2.index();
}

int main(int argc, const char * argv[])
{
    vector<Foo> x { 1, 2, 3 };
    Foo y[] = { 3, 2, 1 };

    cout << checkIfTheSame(begin(x), end(x), begin(y), end(y), same_indexes, sort_indexes) << endl;

    return 0;
}
Richard Hodges
  • 68,278
  • 7
  • 90
  • 142
0

If you do not have any way to sort the array or the vector, but you are only able to know if two elements are equal, the only method is an exhaustive search.

Daniele
  • 821
  • 7
  • 18