Velocity Reviews > C++ > Best way of comparing two containers?

Best way of comparing two containers?

Dylan
Guest
Posts: n/a

 07-09-2004
I'd like to compare two containers. They should be considered
equivalent if both containers have the same number of elements with
the same values, no matter what order the values are in.

For instance the containers

A = [1, 2, 3]
B = [1, 2, 3]

are obviously equal, but so would be

A = [3, 2, 1]
B = [2, 1, 3]

as would

A = [2, 2, 5, 1]
B = [2, 1, 5, 2]

What's the best (quickest) way of comparing containers in this way?

Kai-Uwe Bux
Guest
Posts: n/a

 07-09-2004
Dylan wrote:

> I'd like to compare two containers. They should be considered
> equivalent if both containers have the same number of elements with
> the same values, no matter what order the values are in.
>
> For instance the containers
>
> A = [1, 2, 3]
> B = [1, 2, 3]
>
> are obviously equal, but so would be
>
> A = [3, 2, 1]
> B = [2, 1, 3]
>
> as would
>
> A = [2, 2, 5, 1]
> B = [2, 1, 5, 2]
>
> What's the best (quickest) way of comparing containers in this way?

I am not sure if this is optimal, but the obvious way should be worth
trying: copy into two new containers, sort them and check whether they
are equal. That would work in O(n*log(n)) time:

#include <vector>
#include <algorithm>

template < typename T, template <typename> class C >
bool sort_compare ( const C<T> & c_1, const C<T> & c_2 ) {
std::vector<T> v_1 ( c_1.begin(), c_1.end() );
std::vector<T> v_2 ( c_2.begin(), c_2.end() );
std::sort( v_1.begin(), v_1.end() );
std::sort( v_2.begin(), v_2.end() );
return( v_1 == v_2 );
}

#include <iostream>

int main ( void ) {
std::vector< int > c_1;
c_1.push_back( 1 );
c_1.push_back( 1 );
c_1.push_back( 3 );
std::vector< int > c_2;
c_2.push_back( 3 );
c_2.push_back( 1 );
c_2.push_back( 1 );
std::vector< int > c_3;
c_3.push_back( 3 );
c_3.push_back( 0 );
c_3.push_back( 1 );
std::cout << sort_compare( c_1, c_2 )
<< " "
<< sort_compare( c_2, c_3 )
<< "\n";
}

Do you suspect that there is a linear time method?

Best

Kai-Uwe Bux

E. Robert Tisdale
Guest
Posts: n/a

 07-09-2004
Dylan wrote:

> I'd like to compare two containers. They should be considered
> equivalent if both containers have the same number of elements with
> the same values, no matter what order the values are in.
>
> For instance the containers
>
> A = [1, 2, 3]
> B = [1, 2, 3]
>
> are obviously equal, but so would be
>
> A = [3, 2, 1]
> B = [2, 1, 3]
>
> as would
>
> A = [2, 2, 5, 1]
> B = [2, 1, 5, 2]
>
> What's the best (quickest) way of comparing containers in this way?

Is [3, 1, 1] equal to [3, 3, 1] for example?

What do you mean by "order"?
1 < 2 < . . . < INT_MAX?

Dylan
Guest
Posts: n/a

 07-09-2004
On Thu, 08 Jul 2004 21:08:11 -0400, Kai-Uwe Bux <(E-Mail Removed)>
wrote:

>Dylan wrote:
>
>> I'd like to compare two containers. They should be considered
>> equivalent if both containers have the same number of elements with
>> the same values, no matter what order the values are in.
>>
>> For instance the containers
>>
>> A = [1, 2, 3]
>> B = [1, 2, 3]
>>
>> are obviously equal, but so would be
>>
>> A = [3, 2, 1]
>> B = [2, 1, 3]
>>
>> as would
>>
>> A = [2, 2, 5, 1]
>> B = [2, 1, 5, 2]
>>
>> What's the best (quickest) way of comparing containers in this way?

>
>I am not sure if this is optimal, but the obvious way should be worth
>trying: copy into two new containers, sort them and check whether they
>are equal. That would work in O(n*log(n)) time:
>
>#include <vector>
>#include <algorithm>
>
>template < typename T, template <typename> class C >
>bool sort_compare ( const C<T> & c_1, const C<T> & c_2 ) {
> std::vector<T> v_1 ( c_1.begin(), c_1.end() );
> std::vector<T> v_2 ( c_2.begin(), c_2.end() );
> std::sort( v_1.begin(), v_1.end() );
> std::sort( v_2.begin(), v_2.end() );
> return( v_1 == v_2 );
>}
>
>#include <iostream>
>
>int main ( void ) {
> std::vector< int > c_1;
> c_1.push_back( 1 );
> c_1.push_back( 1 );
> c_1.push_back( 3 );
> std::vector< int > c_2;
> c_2.push_back( 3 );
> c_2.push_back( 1 );
> c_2.push_back( 1 );
> std::vector< int > c_3;
> c_3.push_back( 3 );
> c_3.push_back( 0 );
> c_3.push_back( 1 );
> std::cout << sort_compare( c_1, c_2 )
> << " "
> << sort_compare( c_2, c_3 )
> << "\n";
>}
>
>
>Do you suspect that there is a linear time method?
>
>
>Best
>
>Kai-Uwe Bux

Thanks for your answer, but the reason I stipulated that the elements
can be in any order is that, for the problem I'm working on, it's
unreasonable to assume there is a sorting criteria defined for the
element type (or that one can be defined using the type interface).

Andrey Tarasevich
Guest
Posts: n/a

 07-09-2004
Dylan wrote:
> ...
> Thanks for your answer, but the reason I stipulated that the elements
> can be in any order is that, for the problem I'm working on, it's
> unreasonable to assume there is a sorting criteria defined for the
> element type (or that one can be defined using the type interface).
> ...

In that case you should specify what kind of criteria you _do_ have
defined. Boolean equality criteria only? Something else?

--
Best regards,
Andrey Tarasevich

Dylan
Guest
Posts: n/a

 07-09-2004
On Thu, 08 Jul 2004 18:48:52 -0700, Andrey Tarasevich
<(E-Mail Removed)> wrote:

>Dylan wrote:
>> ...
>> Thanks for your answer, but the reason I stipulated that the elements
>> can be in any order is that, for the problem I'm working on, it's
>> unreasonable to assume there is a sorting criteria defined for the
>> element type (or that one can be defined using the type interface).
>> ...

>
>In that case you should specify what kind of criteria you _do_ have
>defined. Boolean equality criteria only? Something else?

Boolean equality criteria only (==)

Dylan
Guest
Posts: n/a

 07-09-2004
On Thu, 08 Jul 2004 18:16:33 -0700, "E. Robert Tisdale"
<(E-Mail Removed)> wrote:

>Dylan wrote:
>
>> I'd like to compare two containers. They should be considered
>> equivalent if both containers have the same number of elements with
>> the same values, no matter what order the values are in.
>>
>> For instance the containers
>>
>> A = [1, 2, 3]
>> B = [1, 2, 3]
>>
>> are obviously equal, but so would be
>>
>> A = [3, 2, 1]
>> B = [2, 1, 3]
>>
>> as would
>>
>> A = [2, 2, 5, 1]
>> B = [2, 1, 5, 2]
>>
>> What's the best (quickest) way of comparing containers in this way?

>

Is it?

>
>Is [3, 1, 1] equal to [3, 3, 1] for example?

no, see above

>What do you mean by "order"?
>1 < 2 < . . . < INT_MAX?

replace "order" with "position".

E. Robert Tisdale
Guest
Posts: n/a

 07-09-2004
Dylan wrote:

> E. Robert Tisdale wrote:
>
>>Dylan wrote:
>>
>>>I'd like to compare two containers. They should be considered
>>>equivalent if both containers have the same number of elements with
>>>the same values, no matter what order the values are in.
>>>
>>>For instance the containers
>>>
>>>A = [1, 2, 3]
>>>B = [1, 2, 3]
>>>
>>>are obviously equal, but so would be
>>>
>>>A = [3, 2, 1]
>>>B = [2, 1, 3]
>>>
>>>as would
>>>
>>>A = [2, 2, 5, 1]
>>>B = [2, 1, 5, 2]
>>>
>>>What's the best (quickest) way of comparing containers in this way?

>>

>
> Is it?

Yes.

>>Is [3, 1, 1] equal to [3, 3, 1] for example?

>
> no, see above

What above disqualifies this example?

>>What do you mean by "order"?
>>1 < 2 < . . . < INT_MAX?

>
> replace "order" with "position".

What *type* of container are you talking about?
Apparently, it's *not* a set.
Can you extract the set of elements from each container
and compare them for equality
to get the equivalence relationship that you want?

Kai-Uwe Bux
Guest
Posts: n/a

 07-09-2004
Dylan wrote:

> On Thu, 08 Jul 2004 18:48:52 -0700, Andrey Tarasevich
> <(E-Mail Removed)> wrote:
>
>>Dylan wrote:
>>> ...
>>> Thanks for your answer, but the reason I stipulated that the elements
>>> can be in any order is that, for the problem I'm working on, it's
>>> unreasonable to assume there is a sorting criteria defined for the
>>> element type (or that one can be defined using the type interface).
>>> ...

>>
>>In that case you should specify what kind of criteria you _do_ have
>>defined. Boolean equality criteria only? Something else?

>
>
> Boolean equality criteria only (==)

Hm,

in this case, I only see a quadratic way of doing it:

template < typename T, template <typename> class C >
bool nosort_compare ( const C<T> & c_1, const C<T> & c_2 ) {
std::vector<T> v_1 ( c_1.begin(), c_1.end() );
std::vector<T> v_2 ( c_2.begin(), c_2.end() );
if ( v_1.size() != v_2.size() ) {
return( false );
}
typename std::vector<T>::size_type i_1 = 0;
typename std::vector<T>::size_type i_2 = 0;
while ( i_1 < v_1.size() ) {
if ( v_1[i_1] == v_2[i_2] ) {
std::swap( v_2[i_1], v_2[i_2] );
++ i_1;
i_2 = i_1;
continue;
} else if ( i_2 == v_2.size() ) {
return( false );
} else {
++ i_2;
}
}
return( true );
}

Beware: as this code is not as transparent as the sorting method, it
may be deeply flawed.

Best

Kai-Uwe Bux

Markus Dehmann
Guest
Posts: n/a

 07-09-2004
On Fri, 09 Jul 2004 01:07:57 +0100, Dylan <(E-Mail Removed)> wrote:

> I'd like to compare two containers. They should be considered
> equivalent if both containers have the same number of elements with
> the same values, no matter what order the values are in.
>
> For instance the containers
>
> A = [1, 2, 3]
> B = [1, 2, 3]
>
> are obviously equal, but so would be
>
> A = [3, 2, 1]
> B = [2, 1, 3]
>
> as would
>
> A = [2, 2, 5, 1]
> B = [2, 1, 5, 2]
>
> What's the best (quickest) way of comparing containers in this way?

Isn't that a multiset?
http://mathworld.wolfram.com/Multiset.html

If so, use the STL multiset implementation
http://www.sgi.com/tech/stl/multiset.html

Markus