Best way of comparing two containers?

Discussion in 'C++' started by Dylan, Jul 9, 2004.

  1. Dylan

    Dylan Guest

    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?
     
    Dylan, Jul 9, 2004
    #1
    1. Advertising

  2. Dylan

    Kai-Uwe Bux Guest

    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
     
    Kai-Uwe Bux, Jul 9, 2004
    #2
    1. Advertising

  3. 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?


    Your *equivalence relationship* is *ill-defined*.

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

    What do you mean by "order"?
    1 < 2 < . . . < INT_MAX?
     
    E. Robert Tisdale, Jul 9, 2004
    #3
  4. Dylan

    Dylan Guest

    On Thu, 08 Jul 2004 21:08:11 -0400, Kai-Uwe Bux <>
    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).
     
    Dylan, Jul 9, 2004
    #4
  5. 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
     
    Andrey Tarasevich, Jul 9, 2004
    #5
  6. Dylan

    Dylan Guest

    On Thu, 08 Jul 2004 18:48:52 -0700, Andrey Tarasevich
    <> 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, Jul 9, 2004
    #6
  7. Dylan

    Dylan Guest

    On Thu, 08 Jul 2004 18:16:33 -0700, "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?

    >
    >Your *equivalence relationship* is *ill-defined*.


    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".
     
    Dylan, Jul 9, 2004
    #7
  8. 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?

    >>
    >>Your *equivalence relationship* is *ill-defined*.

    >
    > 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?
     
    E. Robert Tisdale, Jul 9, 2004
    #8
  9. Dylan

    Kai-Uwe Bux Guest

    Dylan wrote:

    > On Thu, 08 Jul 2004 18:48:52 -0700, Andrey Tarasevich
    > <> 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
     
    Kai-Uwe Bux, Jul 9, 2004
    #9
  10. On Fri, 09 Jul 2004 01:07:57 +0100, 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?


    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
     
    Markus Dehmann, Jul 9, 2004
    #10
  11. Dylan wrote:
    >
    > On Thu, 08 Jul 2004 18:48:52 -0700, Andrey Tarasevich
    > <> 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 (==)


    Hmm. Would it be possible to make up some artificial 'less'
    relationship just for the purpose of sorting? It doesn't
    matter if that 'less' actually makes some sense in the
    assignment space.
    (Such a thing is almost always possible to do)


    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Jul 9, 2004
    #11
  12. 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 think you need to use std::set or std::multiset.






    Regards,

    Ioannis Vranos
     
    Ioannis Vranos, Jul 9, 2004
    #12
  13. Example:


    #include <iostream>
    #include <set>


    int main()
    {
    using namespace std;

    multiset<int>t1, t2;

    t1.insert(2);
    t1.insert(2);
    t1.insert(5);
    t1.insert(1);

    t2.insert(2);
    t2.insert(1);
    t2.insert(5);
    t2.insert(2);

    if(t1==t2)
    cout<<"\nEqual!\n";

    }






    Regards,

    Ioannis Vranos
     
    Ioannis Vranos, Jul 9, 2004
    #13
  14. Dylan

    Jeff Flinn Guest

    "Ioannis Vranos" <> wrote in message
    news:ccmhat$l13$...
    > Example:
    >
    >
    > #include <iostream>
    > #include <set>
    >
    >
    > int main()
    > {
    > using namespace std;
    >
    > multiset<int>t1, t2;
    >
    > t1.insert(2);
    > t1.insert(2);
    > t1.insert(5);
    > t1.insert(1);
    >
    > t2.insert(2);
    > t2.insert(1);
    > t2.insert(5);
    > t2.insert(2);
    >
    > if(t1==t2)
    > cout<<"\nEqual!\n";
    >
    > }


    Which works for int, but the OP said his T only implements operator==, and
    not any of the inequalities.

    Jeff F
     
    Jeff Flinn, Jul 9, 2004
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Anton
    Replies:
    1
    Views:
    369
    Peter van Merkerk
    Aug 6, 2003
  2. GenxLogic
    Replies:
    3
    Views:
    1,285
    andrewmcdonagh
    Dec 6, 2006
  3. Replies:
    7
    Views:
    554
    Pete Becker
    Jan 25, 2008
  4. Mark  Watson
    Replies:
    13
    Views:
    196
    James Edward Gray II
    Mar 7, 2006
  5. Sebastian Mach
    Replies:
    5
    Views:
    313
Loading...

Share This Page