检查向量的所有元素在C++中是否相等

Question

如果我有一个值向量并想要检查它们是否完全相同,那么在C++中有效地执行此操作的最佳方法是什么？如果我用R之类的其他语言进行编程,我的思维方式就是只返回容器的唯一元素,然后如果唯一元素的长度大于1,我知道元素不能相同.在C++中,这可以这样做:

//build an int vector
std::sort(myvector.begin(), myvector.end());
std::vector<int>::iterator it;
//Use unique algorithm to get the unique values.
it = std::unique(myvector.begin(), myvector.end());
positions.resize(std::distance(myvector.begin(),it));
if (myvector.size() > 1) {
    std::cout << "All elements are not the same!" << std::endl;
}

然而,阅读有关互联网和SO,我看到其他答案,如使用集合或find_if算法.那么最有效的方法是什么？为什么？我想我的不是最好的方法,因为它涉及排序每个元素然后调整向量的大小 - 但也许我错了.

谢谢,本.

Answer 1

你不需要使用std::sort.它可以以更简单的方式完成:

if ( std::adjacent_find( myvector.begin(), myvector.end(), std::not_equal_to<>() ) == myvector.end() )
{
    std::cout << "All elements are equal each other" << std::endl;
}

Answer 2

您可以使用 std::equal

版本1:

//assuming v has at least 1 element
if ( std::equal(v.begin() + 1, v.end(), v.begin()) )
{
    //all equal
}

这将比较每个元素与前一个元素.

版本2:

//assuming v has at least 1 element
int e = v[0]; //preferably "const auto& e" instead
bool all_equal = true;
for(std::size_t i = 1,s = v.size();i<s && all_equal;i++)
    all_equal = e == v[i];

编辑:

关于性能,在使用100m元素进行测试后,我发现Visual Studio 2015的version 1速度大约是其两倍version 2.这是因为当您使用ints,float等时,vs2015的最新编译器在c ++ std实现中使用sse指令.

如果您使用_mm_testc_si128,您将获得类似的性能std::equal

Answer 3

使用 std::all_of 和 C++11 lambda

if (all_of(values.begin(), values.end(), [&] (int i) {return i == values[0];})){
    //all are the same
}

Answer 4

给定矢量没有约束,无论方法如何,都必须至少迭代一次向量.所以只需选择第一个元素并检查所有其他元素是否相等.

Answer 5

虽然 的渐近复杂度std::unique是线性的，但操作的实际成本可能比您需要的要大得多，而且它是一种就地算法（它会随着数据进行修改）。

最快的方法是假设如果向量包含单个元素，则根据定义它是唯一的。如果向量包含更多元素，那么您只需要检查它们是否都完全等于第一个。为此，您只需要找到与第一个不同的第一个元素，从第二个开始搜索。如果存在这样的元素，则元素不是唯一的。

if (v.size() < 2) return true;
auto different = std::find_if(v.begin()+1, v.end(), 
                              [&v](auto const &x) { x != v[0]; });
return different == v.end();

那是使用 C++14 语法，在 C++11 工具链中，您可以在 lambda 中使用正确的类型。在 C++03 中，您可以使用std::not,std::bind1st/std::bind2nd和的组合来std::equal代替 lambda。

这种方法的成本是distance(start,different element)比较而不是复制。比较次数的预期和最坏情况线性成本（并且没有副本！）