比较两个容器的最佳方法？ [英] Best way of comparing two containers?
问题描述
我想比较两个容器。如果两个容器具有相同数量的元素且
的值相同，则无论该值的顺序如何，它们都应被视为等价
。
A = [1,2,3]
B = [1,2,3]
显然是平等的，但也是如此。
A = [3,2,1]
B = [ 2，1,3]
和
A = [2,2,5,1]
B = [2,1,5,2]
以这种方式比较容器的最佳（最快）方法是什么？
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写道：
Dylan wrote:
我想比较两个容器。如果两个容器具有相同数量的元素具有相同的值，无论数值的顺序如何，它们都应被视为等效。
例如容器
A = [1,2,3]
B = [1,2,3]
显然是平等的，但也是如此。
A = [3,2,1]
B = [2,1,3]
A = [2,2,5] ，1]
B = [2,1,5,2]
以这种方式比较容器的最佳（最快）方法是什么？
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?
我不确定这是否是最佳的，但显而易见的方法应该值得尝试：复制到两个新的容器中，对它们进行排序并检查它们是否
是平等的。那将在O（n * log（n））时间内起作用：
#include< vector>
#include< algorithm>
模板< typename T，template< typename> 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";
}
您怀疑是否存在线性时间方法？
Best
Kai-Uwe Bux
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
2004年7月8日星期四21:08:11 -0400，Kai-Uwe Bux< jk **** **** @ gmx.net>
写道：
On Thu, 08 Jul 2004 21:08:11 -0400, Kai-Uwe Bux <jk********@gmx.net>
wrote:
Dylan写道：
Dylan wrote:
我会喜欢比较两个容器。如果两个容器具有相同数量的元素具有相同的值，无论数值的顺序如何，它们都应被视为等效。
例如容器
A = [1,2,3]
B = [1,2,3]
显然是平等的，但也是如此。
A = [3,2,1]
B = [2,1,3]
A = [2,2,5] ，1]
B = [2,1,5,2]
以这种方式比较容器的最佳（最快）方法是什么？
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?
我不确定这是否是最佳的，但显而易见的方法应该值得尝试：复制到两个新容器中，对它们进行排序并检查它们是否相等。那将在O（n * log（n））时间内起作用：
#include< vector>
#include< algorithm>
模板< typename T，template< typename> 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（））;
返回（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";
}
您怀疑是否存在线性时间法？
最佳
Uwe Bux
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写道：
...
感谢您的回答，但我规定的原因对于我正在研究的问题，元素
可以是任何顺序，假设有为
元素类型定义的排序标准，这是不合理的（或者可以使用类型界面定义一个）。
...
...
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
In that case you should specify what kind of criteria you _do_ have
defined. Boolean equality criteria only? Something else?
--
Best regards,
Andrey Tarasevich
这篇关于比较两个容器的最佳方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
