CODEWITHSUNDEEP
c++
Jannat Arora
Jannat Arora

Reputation: 2989

Finding a vector of struct within a set

I am trying to find vector of a struct within a set. In order to do so I wrote the following code:

#include <cstdlib>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

struct A{
    int a;
};

int main(int argc, char** argv) {

    std::set< std::vector<A> > aObj;
    A a1,a2,a3,a4,a5,a6;
    a1.a=5; a2.a=8; a3.a=10;
    a4.a=5; a5.a=8; a6.a=10;
    vector<A> vecA,vecB;
    vecA.push_back(a1); vecA.push_back(a2); vecA.push_back(a3);
    aObj.insert(vecA);
    set< vector<A> >::iterator it = aObj.find(vecB);
    if (it != myset.end()) {
        cout<<"\n Found vector B. \n";
    }    
    return 0;
}

However, the above code is giving me the following error:

/usr/include/c++/4.6/bits/stl_algobase.h:881:6: error: no match for ‘operator<’ in ‘* __first1 < * __first2’
/usr/include/c++/4.6/bits/stl_algobase.h:881:6: note: candidates are:
/usr/include/c++/4.6/bits/stl_pair.h:207:5: note: template<class _T1, class _T2> bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)
/usr/include/c++/4.6/bits/stl_iterator.h:291:5: note: template<class _Iterator> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)
/usr/include/c++/4.6/bits/stl_iterator.h:341:5: note: template<class _IteratorL, class _IteratorR> bool std::operator<(const std::reverse_iterator<_IteratorL>&, const std::reverse_iterator<_IteratorR>&)
/usr/include/c++/4.6/bits/basic_string.h:2510:5: note: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::basic_string<_CharT, _Traits, _Alloc>&, const std::basic_string<_CharT, _Traits, _Alloc>&)
/usr/include/c++/4.6/bits/basic_string.h:2522:5: note: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*)
/usr/include/c++/4.6/bits/basic_string.h:2534:5: note: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const _CharT*, const std::basic_string<_CharT, _Traits, _Alloc>&)

Upvotes: 1

Views: 68

Answers (2)

sehe
sehe

Reputation: 394054

The other answer explains it nicely. If A defines a weak total ordering (e.g. by implementing operator<) you'll be able to find the vectors.

Here's how to make the code more succinct:

Live On Coliru

#include <iostream>
#include <set>
#include <vector>

struct A {
    int a;
    bool operator<(A const &other) const { return a < other.a; }
};

int main() {
    std::set<std::vector<A> > myset{ 
        { { 4 }, { 7 }, { 9 } },
        { { 5 }, { 8 }, { 10 } },
        { { 6 }, { 9 }, { 11 } },
    };

    auto it = myset.find({ {1}, {2}, {3} });
    std::cout << "Found vector: " << std::boolalpha << (it != myset.end()) << "\n"; 

    it = myset.find({ {5}, {8}, {10} });
    std::cout << "Found vector: " << std::boolalpha << (it != myset.end()) << "\n"; 
}

Prints

Found vector: false
Found vector: true

This uses aggregate initialization for A and uniform initialization of the vector and set containers ({a,b,c} will use the std::initialializer_list<> constructor overloads)

Upvotes: 4

Kristian Duske
Kristian Duske

Reputation: 1779

As it is now, std::set::find is trying to compare the given vector with the vector in the set using std::less<std::vector<A>>, which is the default comparator for instances of std::set<std::vector<A>>. AFAIK, std::less will call bool operator<(const std::vector<A>& lhs, const std::vector<A>& rhs) const to compare the vectors, and this will in turn perform a lexicographical comparison of the vectors by using std::less<A>. std::less<A> will then try to call either bool A::operator<(const A& rhs) const (member function version) or bool operator<(const A& lhs, const A& rhs) const (free function version) to compare instances of A. This fails because neither of these functions exist.

You have two options:

1) You equip your struct A with a comparison operator (in this example, we do it as a member function) like so:

bool operator<(const A& rhs) const { return a < rhs.a; }

and rely on std::vector's implementation of operator<, which performs lexicographical comparison. Lexicographical comparison means that the vector elements are compared pairwise until a pair (x,y) of elements of the two vectors being compared is found where x < y or y < x. If no such pair exists, then both vectors are consider equal, unless they have different lengths, in which case the shorter vector is a prefix of the longer one, and is consider less.

2) You provide a comparator to your std::set that can compare the vectors, specifically, determine which of two vectors is less than the other. This is only useful if you don't want to use std::vector's lexicographical comparison and if you can define a weak total order on your vectors. If that is the case, then you can implement a comparator like so:

struct VecCmp {
    bool operator<(const std::vector<A>& lhs, const std::vector<A>& rhs) const {
        // determine whether lhs is less than rhs and return true if so, false otherwise
    }
};

You then configure your std::set to use this comparator like so:

std::set<std::vector<A>, VecCmp> myset(VecCmp());

Upvotes: 3

Related Questions