STL set comparator of vectors

[data2792]

Hello!
I'm trying to make comparator of two vector for STL set. but Unfortunately this code doesn't work.

struct cmp{
	bool operator() (const vector<int> &v1,const vector<int> &v2) {
		for(int i=0;i<v1.size();i++){
			if(v1[i]<v2[i])
				return -1;
			if(v1[i]>v2[i])
				return 1;
		}
		return 0;
	}
};
int main(){
    set<vector<int>,cmp> seti; /* of course there are other functions in main       but this is not important */
    return o;
}

when I insert first vector for example {2,4,6} it works fine but if then I'm trying to insert {2,4,8} it doesn't work and the size of set is the same(1) and there is {2,4,6} vector;

I tried also such an implementation of comparison function:

struct cmp{
	bool operator() (const vector<int> &v1,const vector<int> &v2) {
		for(int i=0;i<v1.size();i++){
			if(v1[i]!v2[i])
                          return false;
		}
		return true;
	}
};

I just want to compare two vectors in such a way: if there exists two unequal
elements on the one index it must be added in the set if all of the parallel
numbers are equal it mustn't add to the set. Also I know that every time vectors
have the same size.

Could you help me?
thanks in advance :)

[Peter87]

Isn't the default comparator std::less<std::vector<int>> already what you want?
set<vector<int>> seti;

[data2792]

Thanks it works, I didn't expected that it could have it's own comparator. But What if I wanted to compare with another comparison. I think problem will still exist.

[aquaz]

The problem of your comparator was that you returned -1, 0. The documentation say you have to return true if v1 is before v2, false otherwise.

So you have to define when a vector is before an other. This code might work and is probably the one used by std::less<vector<T>>:

struct cmp{
	bool operator() (const vector<int> &v1,const vector<int> &v2) {
		for(int i=0;i<v1.size();i++){
			if(v1[i] < v2[i])
                          return true;
		}
		return false;
	}
};

Nevertheless, the description on how you want your comparator hints that you doesn't need a set but an unordered_set because you don't need the elements to be ordered.

[Peter87]

As already mentioned the thing to remember is that the comparator should return true if and only if the first argument should be ordered before the second argument. If the comparator returns false both when the arguments are passed as (v1, v2) and as (v2, v1) it considers v1 and v2 to be equal. This is similar to how < (less than) works with numbers. If !(a < b) && !(b < a) then a must be equal to b. It is very important that the comparator gives a strict order. You should not have that v1 before v2, v2 before v3 and v3 before v1. That is not a good order and will screw things up.

The code posted by aquaz will not work. If the vectors are v1={1, 2} and v2={2, 1} then the comparator will return true despite the order of the v1, v2. v1 should be before v2 and v2 should be before v1. That doesn't make sense. Another problem is that it only works when the size of the two vectors are the same.

This comparator should work better:

struct cmp {
	bool operator() (const vector<int> &v1,const vector<int> &v2) {
		if (v1.size() != v2.size())
			return v1.size() < v2.size();
		for(size_t i=0;i<v1.size();i++){
			if(v1[i] != v2[i]) {
				return v1[i] < v2[i];
			}
		}
		return false;
	}
};

Sometimes you care about the order of the elements in the set. Sometimes useful if you prefer a certain order when iterating over the elements in the set. The above comparator will order small vectors before large vectors. If they have the same size it will order them by the first element that that is not equal in the two vectors.

If you instead want to order them in some other order you can simply change the comparator to get the order you want. This comparator will order the vectors a bit different and I think this is how the default comparator orders them.

struct cmp {
	bool operator() (const vector<int> &v1,const vector<int> &v2) {
		size_t minSize = min(v1.size(), v2.size());
		for(size_t i=0;i<minSize;i++){
			if(v1[i] != v2[i]) {
				return v1[i] < v2[i];
			}
		}
		return v1.size() < v2.size();
	}
};

[vlad from moscow]

I would write the following way

struct cmp 
{
	bool operator() ( const vector<int> &v1, const vector<int> &v2 ) const 
	{
		typedef std::vector<int>::size_type size_type;

		size_type size = std::min( v1.size(), v2.size() );

		for ( size_type i = 0; i < size; i++ )
		{
			if ( v1[i] < v2[i] ) return ( true ); 
			else if ( v2[i] < v1[i] ) return ( false );
		}

		return ( ! ( v2.size()  < v1.size() ) );
	}
};

[Peter87]

@vlad
That comparator returns true if the vectors are equal.

[vlad from moscow]

@Peter87

@vlad
That comparator returns true if the vectors are equal

Well, then the last condition can be changed from

return ( ! ( v2.size() < v1.size() ) );
to

return ( v1.size() < v2.size() );

[data2792]

Thank you guys :)